Иерархическая кластеризация сетей - Hierarchical clustering of networks

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

Алгоритм

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

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

Вес

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

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

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

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

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

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

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

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