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

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

Разработан американским математиком Мишель Гирван (Michelle Girvan) и британским физиком Марком Ньюменом (англ. Mark Newman).

Степень посредничества рёбер и структура сообщества

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

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

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

Шаги алгоритма

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

Шаг 4 бывает устроен несколько иначе. Иногда алгоритм завершают после первого падения модулярности (то есть модулярность не увеличилась), иногда в точке достижения её максимума или в одной из точек локального минимума.

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

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

Литература

• Girvan M., Newman M. E. J. Community structure in social and biological networks // Proc. Natl. Acad. Sci. USA. — 2002. — Т. 99.
• Newman M.E.J. Modularity and community structure in networks / Ed. by Brian Skyrms.. — The National Academy of Sciences of the USA, 2006.