Алгоритм Гирвана – Ньюмана

Алгоритм Гирвана-Ньюмана (названный в честь Мишель Гирван и Марка Ньюмана ) — это иерархический метод, используемый для обнаружения сообществ в сложных системах . ^{[ 1 ]}

Грань между и структура сообщества

Алгоритм Гирвана-Ньюмана обнаруживает сообщества путем постепенного удаления ребер из исходной сети. Связными компонентами оставшейся сети являются сообщества. Вместо того, чтобы пытаться построить меру, которая сообщит нам, какие ребра являются наиболее важными для сообществ, алгоритм Гирвана-Ньюмана фокусируется на ребрах, которые, скорее всего, находятся «между» сообществами.

Межвершинность является индикатором наличия центральных узлов в сетях. Для любого узла $i$ , промежуточность вершин определяется как доля кратчайших путей между парами узлов, проходящих через нее. Это актуально для моделей, в которых сеть модулирует перемещение товаров между известными начальной и конечной точками, исходя из предположения, что такая передача ищет кратчайший доступный маршрут.

Алгоритм Гирвана-Ньюмана расширяет это определение на случай ребер, определяя «между ребрами» ребра как количество кратчайших путей между парами узлов, которые проходят вдоль него. Если между парой узлов существует более одного кратчайшего пути, каждому пути присваивается одинаковый вес, так что общий вес всех путей равен единице. Если сеть содержит сообщества или группы, которые лишь слабо связаны несколькими межгрупповыми ребрами, то все кратчайшие пути между различными сообществами должны проходить по одному из этих немногих ребер. Таким образом, ребра, соединяющие сообщества, будут иметь высокую степень межреберья (по крайней мере, одно из них). Удалив эти края, группы отделяются друг от друга, и таким образом раскрывается основная структура сообщества сети.

Шаги алгоритма для обнаружения сообществ кратко изложены ниже.

Сначала вычисляется расстояние между всеми существующими ребрами в сети.
Края с наибольшей промежуточностью удаляются.
Расстояние между всеми ребрами, затронутыми удалением, пересчитывается.
Шаги 2 и 3 повторяются до тех пор, пока не останется ребер.

Тот факт, что пересчитываются только те промежутки, на которые влияет удаление, может сократить время моделирования процесса на компьютерах. Однако центральность посредничества необходимо пересчитывать на каждом шаге, иначе возникнут серьезные ошибки. Причина в том, что сеть адаптируется к новым условиям, возникающим после удаления ребра. Например, если два сообщества соединены более чем одним ребром, то нет гарантии, что все эти ребра будут иметь высокую степень промежутка. По методу мы знаем, что хотя бы один из них будет, но больше ничего неизвестно. Путем пересчета связей после удаления каждого ребра гарантируется, что хотя бы одно из оставшихся ребер между двумя сообществами всегда будет иметь высокое значение.

Конечным результатом алгоритма Гирвана-Ньюмана является дендрограмма . При работе алгоритма Гирвана-Ньюмана дендрограмма строится сверху вниз (т. е. сеть разделяется на различные сообщества с последовательным удалением связей). Листья дендрограммы представляют собой отдельные узлы.

См. также

Ссылки

^ Гирван М. и Ньюман МЭД, Структура сообщества в социальных и биологических сетях , Proc. Натл. акад. наук. США 99 , 7821–7826 (2002)

[newman-1] Гирван М. и Ньюман МЭД, Структура сообщества в социальных и биологических сетях , Proc. Натл. акад. наук. США 99 , 7821–7826 (2002)

[ 1 ]