Алгоритм Лувена, распространение меток, компоненты графа, количество треугольников и коэффициент локальной кластеризации
После изучения основ графовых баз данных, алгоритмов поиска пути и центральности с реализацией Neo4j пришло время перейти к обнаружению сообщества в графах, которое очень полезно в реальном мире, будь то рекомендация друзей в приложениях социальных сетей, обнаружение мошенничества и т. д.
Вы должны пройти предыдущие 3 части для лучшего понимания
Алгоритмы поиска пути в графах
Прежде чем начать, мы должны начать с понимания компонентов графа.
Компоненты графика
Компонент графа — это подграф в графе, такой, что все узлы в подграфе
Иметь путь к другому узлу в подграфе (это требует некоторых пояснений, которые мы обсудим позже в посте).
Не удается достичь узлов других подграфов в графе
Таким образом, может случиться так, что в графе «G» у нас может быть несколько компонентов, где любой узел из компонента «A» не может достичь ни одного узла в других компонентах. Существует 2 типа компонентов графа в зависимости от пути, рассматриваемого между узлами подграфа для объявления
- Слабосвязанные компоненты (WCC):когда направление ребер между узлами игнорируется при рассмотрении пути между двумя узлами, он образует слабосвязный компонент. Итак, если у нас есть A → B, мы рассматриваем это как A — B (двунаправленный) и затем ищем пути, если они доступны.
- Сильно связанные компоненты (SCC): когда рассматривается направление между ребрами, заданными узлами для формирования компонента, это называется сильно связанным компонентом.
Сбивает с толку? Давайте разберемся на примере. Предположим, что это сеть социальных сетей, в которой каждый узел
Теперь, если мы хотим выяснить
- Слабые компоненты: (Майкл, Бриджит, Элис, Чарльз), (Марк, Дуглас)
У нас есть 2 WCC на приведенном выше графике, поскольку существует по крайней мере один путь (независимо от направления ребра), ведущий от одного узла к другому. Итак, если вы хотите связаться с Чарльзом и Майклом, мы можем
Чарльз — Алиса — Майкл (не забудьте игнорировать направление края)
Но не существует пути от любого узла Компонента (Марка, Дугласа) к другому компоненту, поэтому граф имеет 2 слабосвязанных компонента.
2. Компонент с сильными связями
(Майкл, Бриджит, Элис), (Чарльз), (Марк, Дуглас)
Почему Charles отсутствует в компоненте, частью которого он был в случае с WCC?
В случае SCC каждый узел компонента должен быть доступен другому узлу (с учетом направления ребра). Поскольку у Чарльза нет исходящего ребра, вы не можете переместить ни одно ребро из Чарльза в любой узел, поэтому оно не учитывается. В оставшихся двух компонентах каждый узел доступен всем другим узлам (также после рассмотрения направлений ребер).
Давайте запросим наш старый набор данных авиакомпаний, чтобы определить слабосвязанные компоненты. Перед этим нам нужно загрузить набор данных из CSV в какую-нибудь БД и сформировать проекцию, как мы это делали в моих прошлых блогах (все пояснения по шифровальным запросам можно найти здесь)
Набор данных
Загрузка данных из CSV
CALL apoc.load.csv("flight_network_spicejet.csv")
YIELD list as item
MERGE(n:city{name:item[0],lat:toInteger(item[3]),long:toInteger(item[4])})
MERGE (m:city{name:item[1]})
MERGE (n)-[:flight{distance:toInteger(item[2])}]->(m)
Создание проекции
CALL gds.graph.project("airline",{city:{properties:["lat","long"]}},{flight:{properties:"distance",orientation:'UNDIRECTED'}})
в результате чего
Я уже подробно обсуждал вышеупомянутые запросы в моих последних блогах и, следовательно, на этот раз пропускаю какие-либо объяснения.
Давайте определим компоненты слабой связи в нашем графе
CALL gds.wcc.write('airline', { writeProperty: 'community' }) YIELD nodePropertiesWritten, componentCount;
Этот запрос поможет нам записать сообщество, обнаруженное для каждого узла в графе, как свойство «сообщество» для узла. Вы помните разницу между Write и Stream? пора пересмотреть, если нет
В нашем графе мы получили только одно сообщество, следовательно, весь граф представляет собой одну слабосвязную компоненту. Обратите внимание на вывод ниже
Как мы видим на видео выше
- Обнаружен только 1 слабый компонент. следовательно, все узлы принадлежат только одному сообществу
- Для каждого узла «сообщество» = 0 было добавлено новое свойство, отображающее идентификатор слабого компонента. Если бы у нас было обнаружено несколько сообществ, это свойство сообщества принимало бы значения от 0 до n.
- Точно так же мы можем обнаружить сильно связанные компоненты, заменив gds.wcc.write на gds.scc write в приведенном выше запросе.
Найдите версию видеоблога для WCC и SCC ниже:
Алгоритм распространения меток
Одной из важных полезных функций обнаружения сообщества является частично контролируемое обучение и аннотация данных, где мы можем назначать метки немаркированным данным, используя небольшой набор данных с метками в качестве эталона. Тем не менее, он отлично работает, когда метки также не предоставляются.
Алгоритм примерно такой
- Назначьте каждому узлу уникальное сообщество, чтобы общее количество сообществ было равно общему количеству узлов.
- Для каждого узла, используя голосование по большинству, назначьте метку на основе меток его соседей. В случае, если у нас есть несколько претендентов (ни одна метка не является общей или 2 или более меток с одинаковой частотой у соседей), у нас может быть альтернативное правило, такое как 1) расстояние от узла 2) случайное назначение и т. д.
Что такое голосование большинством голосов?
Текущему узлу не будут присвоены ничего, кроме соседей с самой распространенной меткой. Можно считать чем-то похожим на линии K-ближайших соседей.
- Мы запускаем один и тот же процесс для нескольких итераций, где за одну итерацию мы просматриваем все узлы и обновляем их метки на основе голосования большинства.
После n итераций узлы с одинаковыми метками объединяются из одного и того же сообщества.
В случае частично контролируемого обучения вместо того, чтобы использовать для каждого узла уникальную метку, мы можем использовать метки из набора данных и продолжить весь процесс, как указано выше.
Давайте запустим итерацию для распространения меток для маркировки данных на приведенном ниже графике.
Предполагая, что у нас есть метки для A, B и C, и мы хотим пометить E и D. Теперь для E
- У нас есть 2 ребра к A и C соответственно, поэтому большинством голосов мы назначим ей «красную» группу.
- Для D у нас есть тай-брейк, поскольку у него есть ребра с A и B, которые принадлежат к разным группам. Скажем, мы следуем Random в качестве политики разрешения конфликтов, D назначается «зеленой» группой после итерации.
давайте запустим распространение меток в нашей сети авиакомпаний. Мы будем рассматривать все узлы в разных сообществах и запускать распространение меток с использованием весов (расстояние между узлами, которое у нас уже есть).
CALL gds.labelPropagation.stream('airline')
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name
Я не публиковал результаты, как и в случае с WCC, здесь также каждая нода назначается одному сообществу.
Алгоритм Лувена
Как подробно обсуждалось в моем последнем посте, мы не будем углубляться в его объяснение, но обязательно посмотрим, как его использовать с Neo4j. Вы можете найти версию видеоблога ниже.
CALL gds.louvain.write('airline', { writeProperty: 'community' })
YIELD communityCount, modularity, modularities
давайте посмотрим, сколько сообществ мы получаем, используя Лувен
╞════════════════════╪═════════════╡ │"Belgaum" │8 │ ├────────────────────┼─────────────┤ │"Bengaluru" │8 │ ├────────────────────┼─────────────┤ │"Calicut" │8 │ ├────────────────────┼─────────────┤ │"Chennai" │8 │ ├────────────────────┼─────────────┤ │"Coimbatore" │8 │ ├────────────────────┼─────────────┤ │"Gwalior" │8 │ ├────────────────────┼─────────────┤ │"Hubli" │8 │ ├────────────────────┼─────────────┤ │"Hyderabad" │8 │ ├────────────────────┼─────────────┤ │"Kochi" │8 │ ├────────────────────┼─────────────┤ │"Madurai" │8 │ ├────────────────────┼─────────────┤ │"Mangalore" │8 │ ├────────────────────┼─────────────┤ │"Tirupati" │8 │ ├────────────────────┼─────────────┤ │"Vijayawada" │8 │ ├────────────────────┼─────────────┤ │"Visakhapatnam" │8 │ ├────────────────────┼─────────────┤ │"Pondicherry" │8 │ ├────────────────────┼─────────────┤ │"Port Blair" │8 │ ├────────────────────┼─────────────┤ │"Rajahmundry" │8 │ ├────────────────────┼─────────────┤ │"Thiruvananthapuram"│8 │ ├────────────────────┼─────────────┤ │"Tuticorin" │8 │ ├────────────────────┼─────────────┤ │"Bagdogra" │15 │ ├────────────────────┼─────────────┤ │"Dibrugarh" │15 │ ├────────────────────┼─────────────┤ │"Guwahati" │15 │ ├────────────────────┼─────────────┤ │"Kanpur" │15 │ ├────────────────────┼─────────────┤ │"Kolkata" │15 │ ├────────────────────┼─────────────┤ │"Patna" │15 │ ├────────────────────┼─────────────┤ │"Varanasi" │15 │ ├────────────────────┼─────────────┤ │"Lilabari" │15 │ ├────────────────────┼─────────────┤ │"Silchar" │15 │ ├────────────────────┼─────────────┤ │"Ahmedabad" │34 │ ├────────────────────┼─────────────┤ │"Amritsar" │34 │ ├────────────────────┼─────────────┤ │"Bhopal" │34 │ ├────────────────────┼─────────────┤ │"Goa" │34 │ ├────────────────────┼─────────────┤ │"Jaipur" │34 │ ├────────────────────┼─────────────┤ │"Jodhpur" │34 │ ├────────────────────┼─────────────┤ │"Surat" │34 │ ├────────────────────┼─────────────┤ │"Udaipur" │34 │ ├────────────────────┼─────────────┤ │"Pune" │34 │ ├────────────────────┼─────────────┤ │"Aurangabad" │39 │ ├────────────────────┼─────────────┤ │"Darbhanga" │39 │ ├────────────────────┼─────────────┤ │"Dehradun" │39 │ ├────────────────────┼─────────────┤ │"Delhi" │39 │ ├────────────────────┼─────────────┤ │"Jabalpur" │39 │ ├────────────────────┼─────────────┤ │"Jammu" │39 │ ├────────────────────┼─────────────┤ │"Kandla" │39 │ ├────────────────────┼─────────────┤ │"Leh" │39 │ ├────────────────────┼─────────────┤ │"Mumbai" │39 │ ├────────────────────┼─────────────┤ │"Srinagar" │39 │ ├────────────────────┼─────────────┤ │"Rajkot" │39 │ ├────────────────────┼─────────────┤ │"Porbandar" │39 │ └────────────────────┴─────────────┘
Так как neo4j не поддерживает визуализацию на основе свойств, мы пропускаем это.
Количество треугольников и коэффициент локальной кластеризации
Как следует из названия, количество треугольников — это не что иное, как сообщество из 3 узлов, которые образуют треугольник в графе, то есть имеют ребро друг над другом независимо от направления.
Давайте посмотрим количество треугольников для каждого узла в нашей сети авиакомпаний.
Запрос
CALL gds.triangleCount.stream('airline')
YIELD nodeId, triangleCount
RETURN gds.util.asNode(nodeId).name AS name, triangleCount
ORDER BY triangleCount DESC
Выход
│"name" │"triangleCount"│ ╞════════════════════╪═══════════════╡ │"Delhi" │157 │ ├────────────────────┼───────────────┤ │"Mumbai" │146 │ ├────────────────────┼───────────────┤ │"Bengaluru" │142 │ ├────────────────────┼───────────────┤ │"Hyderabad" │128 │ ├────────────────────┼───────────────┤ │"Chennai" │122 │ ├────────────────────┼───────────────┤ │"Ahmedabad" │105 │ ├────────────────────┼───────────────┤ │"Kolkata" │97 │ ├────────────────────┼───────────────┤ │"Jaipur" │80 │ ├────────────────────┼───────────────┤ │"Patna" │73 │ ├────────────────────┼───────────────┤ │"Guwahati" │55 │ ├────────────────────┼───────────────┤ │"Varanasi" │52 │ ├────────────────────┼───────────────┤ │"Pune" │43 │ ├────────────────────┼───────────────┤ │"Surat" │40 │ ├────────────────────┼───────────────┤ │"Bagdogra" │28 │ ├────────────────────┼───────────────┤ │"Bhopal" │25 │ ├────────────────────┼───────────────┤ │"Kochi" │25 │ ├────────────────────┼───────────────┤ │"Udaipur" │24 │ ├────────────────────┼───────────────┤ │"Goa" │21 │ ├────────────────────┼───────────────┤ │"Visakhapatnam" │20 │ ├────────────────────┼───────────────┤ │"Amritsar" │17 │ ├────────────────────┼───────────────┤ │"Dehradun" │16 │ ├────────────────────┼───────────────┤ │"Coimbatore" │15 │ ├────────────────────┼───────────────┤ │"Jabalpur" │15 │ ├────────────────────┼───────────────┤ │"Kanpur" │15 │ ├────────────────────┼───────────────┤ │"Mangalore" │14 │ ├────────────────────┼───────────────┤ │"Aurangabad" │10 │ ├────────────────────┼───────────────┤ │"Madurai" │10 │ ├────────────────────┼───────────────┤ │"Srinagar" │10 │ ├────────────────────┼───────────────┤ │"Thiruvananthapuram"│10 │ ├────────────────────┼───────────────┤ │"Vijayawada" │8 │ ├────────────────────┼───────────────┤ │"Jammu" │7 │ ├────────────────────┼───────────────┤ │"Calicut" │6 │ ├────────────────────┼───────────────┤ │"Darbhanga" │6 │ ├────────────────────┼───────────────┤ │"Hubli" │6 │ ├────────────────────┼───────────────┤ │"Port Blair" │6 │ ├────────────────────┼───────────────┤ │"Jodhpur" │5 │ ├────────────────────┼───────────────┤ │"Tirupati" │4 │ ├────────────────────┼───────────────┤ │"Belgaum" │3 │ ├────────────────────┼───────────────┤ │"Gwalior" │3 │ ├────────────────────┼───────────────┤ │"Leh" │3 │ ├────────────────────┼───────────────┤ │"Rajahmundry" │3 │ ├────────────────────┼───────────────┤ │"Tuticorin" │3 │ ├────────────────────┼───────────────┤ │"Dibrugarh" │1 │ ├────────────────────┼───────────────┤ │"Kandla" │1 │ ├────────────────────┼───────────────┤ │"Pondicherry" │1 │ ├────────────────────┼───────────────┤ │"Rajkot" │1 │ ├────────────────────┼───────────────┤ │"Lilabari" │1 │ ├────────────────────┼───────────────┤ │"Silchar" │1 │ ├────────────────────┼───────────────┤ │"Porbandar" │0 │ └────────────────────┴───────────────┘
Столичные города являются частью многочисленных треугольников, отражающих их важность в сети авиакомпаний, в то время как Порбандар не является частью единого треугольника.
Расширяя количество треугольников, коэффициент локальной кластеризации определяет, насколько хорошо связаны соседние узлы узла с использованием счетчика треугольников по формуле
Локальный коэффициент кластеризации (n) = 2xT (узел) / d (n) (d (n) -1)
Где
- T () дает общую частоту треугольников, частью которых является узел n в сети.
- d() - степень узла n
Давайте посмотрим на быстрый пример
Здесь количество треугольников для узла 3 = 1 (как часть 2 треугольников, 4–3–5) и коэффициент локальной кластеризации = 2 * 1/3 * 2 = 0,33.
Степень (3) = 3
Давайте посмотрим, какие узлы имеют самый высокий коэффициент кластеризации в нашей сети.
CALL gds.localClusteringCoefficient.stream('airline')
YIELD nodeId, localClusteringCoefficient
RETURN gds.util.asNode(nodeId).name AS name, localClusteringCoefficient
ORDER BY localClusteringCoefficient DESC
Выход
════════════════════╤════════════════════════════╕ │"name" │"localClusteringCoefficient"│ ╞════════════════════╪════════════════════════════╡ │"Aurangabad" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Bagdogra" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Belgaum" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Calicut" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Coimbatore" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Darbhanga" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Dibrugarh" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Hubli" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Jabalpur" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Kandla" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Kanpur" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Leh" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Madurai" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Pondicherry" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Port Blair" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Rajahmundry" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Thiruvananthapuram"│1.0 │ ├────────────────────┼────────────────────────────┤ │"Tuticorin" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Rajkot" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Lilabari" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Silchar" │1.0 │ ├────────────────────┼────────────────────────────┤ │"Mangalore" │0.9333333333333333 │ ├────────────────────┼────────────────────────────┤ │"Bhopal" │0.8928571428571429 │ ├────────────────────┼────────────────────────────┤ │"Udaipur" │0.8571428571428571 │ ├────────────────────┼────────────────────────────┤ │"Jodhpur" │0.8333333333333334 │ ├────────────────────┼────────────────────────────┤ │"Amritsar" │0.8095238095238095 │ ├────────────────────┼────────────────────────────┤ │"Vijayawada" │0.8 │ ├────────────────────┼────────────────────────────┤ │"Varanasi" │0.7878787878787878 │ ├────────────────────┼────────────────────────────┤ │"Dehradun" │0.7619047619047619 │ ├────────────────────┼────────────────────────────┤ │"Goa" │0.75 │ ├────────────────────┼────────────────────────────┤ │"Surat" │0.7272727272727273 │ ├────────────────────┼────────────────────────────┤ │"Visakhapatnam" │0.7142857142857143 │ ├────────────────────┼────────────────────────────┤ │"Patna" │0.6952380952380952 │ ├────────────────────┼────────────────────────────┤ │"Kochi" │0.6944444444444444 │ ├────────────────────┼────────────────────────────┤ │"Jaipur" │0.6666666666666666 │ ├────────────────────┼────────────────────────────┤ │"Tirupati" │0.6666666666666666 │ ├────────────────────┼────────────────────────────┤ │"Srinagar" │0.6666666666666666 │ ├────────────────────┼────────────────────────────┤ │"Pune" │0.6515151515151515 │ ├────────────────────┼────────────────────────────┤ │"Guwahati" │0.6043956043956044 │ ├────────────────────┼────────────────────────────┤ │"Gwalior" │0.5 │ ├────────────────────┼────────────────────────────┤ │"Jammu" │0.4666666666666667 │ ├────────────────────┼────────────────────────────┤ │"Ahmedabad" │0.45454545454545453 │ ├────────────────────┼────────────────────────────┤ │"Kolkata" │0.383399209486166 │ ├────────────────────┼────────────────────────────┤ │"Chennai" │0.3475783475783476 │ ├────────────────────┼────────────────────────────┤ │"Hyderabad" │0.2752688172043011 │ ├────────────────────┼────────────────────────────┤ │"Delhi" │0.2638655462184874 │ ├────────────────────┼────────────────────────────┤ │"Bengaluru" │0.2531194295900178 │ ├────────────────────┼────────────────────────────┤ │"Mumbai" │0.23174603174603176 │ ├────────────────────┼────────────────────────────┤ │"Porbandar" │0.0 │ └────────────────────┴────────────────────────────┘
Результаты действительно интересные, есть несколько моментов, на которые стоит обратить внимание.
- Некоторые города уровня 2 имеют коэффициент. Это может указывать на 2 вещи
- У них действительно не так много соседей
- Их соседи действительно хорошо связаны
Мегаполисы можно найти в нижней части списка, возможно, из-за того, что у них много соседей, которые в основном являются городами уровня 2 и, следовательно, не так хорошо связаны, как они.
С этим, это обертка!
Больше блогов
- Графическая аналитика (6 частей)
- Алгоритмы НЛП (9 частей)
- Начнем с временных рядов (8 частей)
- Основы обучения с подкреплением (6 частей)
- Создание портфолио с помощью Streamlit
- Генеративное моделирование (7 частей)
- Трансформеры в НЛП(4 части)
- Уменьшение размеров (3 части)
- Обнаружение объектов с помощью YOLO (3 части)
- Tensorflow для начинающих (концепции + примеры) (4 части)
- Статистика для начинающих (4 части)
