Иерархическая кластеризация сетей

Иерархическая кластеризация - это один из методов поиска структур сообщества в сети. Этот метод разбивает сеть на иерархию групп в соответствии с заданной весовой функцией. Затем данные могут быть представлены в виде древовидной структуры, известной как дендрограмма. Иерархическая кластеризация может быть агломеративной или разделяющей в зависимости от того, проходит ли алгоритм по алгоритму, добавляя ссылки или удаляя ссылки из сети соответственно. Одним из методов разделения является алгоритм Гирвана – Ньюмана.

• 1 Алгоритм
• 2 Веса
• 3 См. Также
• 4 Ссылки

В иерархической алгоритм кластеризации, weight $W\; ij\; \{\backslash \; displaystyle\; W\_\; \{ij\}\}$сначала назначается каждой паре вершин $(i,\; j)\; \{\backslash \; displaystyle\; (i,\; j)\}$в сети. Вес, который может варьироваться в зависимости от реализации (см. Раздел ниже), предназначен для обозначения того, насколько тесно связаны вершины. Затем, начиная с отключения всех узлов в сети, начните объединять узлы в пары в порядке уменьшения веса между парами (в случае разделения начните с исходной сети и удалите ссылки в порядке уменьшения веса). По мере добавления ссылок начинают формироваться связанные подмножества. Они представляют собой структуры сообщества сети.

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

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

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

Граница центральность промежуточности успешно использовалась в качестве веса в алгоритме Гирвана – Ньюмана. Этот метод аналогичен алгоритму иерархической иерархической кластеризации, за исключением того, что веса пересчитываются на каждом шаге.

Изменение модульности сети с добавлением узла также успешно использовалось в качестве веса. Этот метод обеспечивает менее затратную в вычислительном отношении альтернативу алгоритму Гирвана-Ньюмана, давая аналогичные результаты.

• Топология сети
• Числовая таксономия
• Древовидная структура

1. ^ Гирван, М. ; Ньюман, М. Э. Дж. (11.06.2002). «Структура сообщества в социальных и биологических сетях». Труды Национальной академии наук. Труды Национальной академии наук. 99 (12): 7821–7826. arXiv : cond-mat / 0112110. DOI : 10.1073 / pnas.122653799. ISSN 0027-8424.
2. ^Ньюман, М. Э. Дж. (18 июня 2004 г.). «Быстрый алгоритм определения структуры сообщества в сети». Physical Review E. Американское физическое общество (APS). 69 (6): 066133. arXiv : cond-mat / 0309508. DOI : 10.1103 / Physreve.69.066133. ISSN 1539-3755.