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

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

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

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

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

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

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

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

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

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

Смотрите также

• Близость
• Иерархическая кластеризация
• Модульность

Рекомендации

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