Структура сообщества

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

Свойства

Рис. 1: Эскиз небольшой сети , отображающей структуру сообщества с тремя группами узлов с плотными внутренними связями и более редкими связями между группами.

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

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

Некоторые сети могут не иметь значимой структуры сообщества. Многие базовые сетевые модели, например, такие как случайный граф и модель Барабаши-Альберта , не отображают структуру сообщества.

Важность

Структуры сообществ довольно распространены в реальных сетях. Социальные сети включают группы сообществ (фактически, происхождение этого термина), основанные на общем местонахождении, интересах, роде деятельности и т. д.

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

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

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

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

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

Алгоритмы поиска сообществ

Поиск сообществ в произвольной сети может оказаться сложной вычислительной задачей. Количество сообществ в сети, если таковые имеются, обычно неизвестно, и сообщества часто имеют неодинаковый размер и/или плотность. Однако, несмотря на эти трудности, было разработано несколько методов поиска сообществ, которые применяются с разной степенью успеха.

Метод минимального разреза

Одним из старейших алгоритмов разделения сетей на части является метод минимального разреза (и такие варианты, как пропорциональный разрез и нормализованный разрез). Этот метод находит применение, например, при балансировке нагрузки при параллельных вычислениях , чтобы минимизировать обмен данными между процессорными узлами.

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

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

Еще одним методом поиска структур сообществ в сетях является иерархическая кластеризация . В этом методе определяется мера сходства, количественно определяющая некоторый (обычно топологический) тип сходства между парами узлов. Обычно используемые меры включают косинусное сходство , индекс Жаккара и расстояние Хэмминга между строками матрицы смежности . Затем сходные узлы группируются в сообщества в соответствии с этой мерой. Существует несколько распространенных схем выполнения группировки, две из самых простых — это кластеризация с одной связью , в которой две группы считаются отдельными сообществами тогда и только тогда, когда все пары узлов в разных группах имеют сходство ниже заданного порога, и полная кластеризация со связями. , при котором все узлы внутри каждой группы имеют сходство, превышающее пороговое значение. Важным шагом является определение порога остановки агломеративной кластеризации, указывающего на структуру сообщества, близкую к оптимальной. Общая стратегия состоит в построении одной или нескольких метрик, отслеживающих глобальные свойства сети, которые достигают пика на данном этапе кластеризации. Интересным подходом в этом направлении является использование различных мер сходства или несходства, объединенных посредством выпуклые суммы ,. Другое приближение - это вычисление величины, контролирующей плотность ребер внутри кластеров по отношению к плотности между кластерами, например, плотность разделения, которая была предложена, когда метрика сходства определяется между ребрами (что позволяет определять перекрывающиеся сообщества). , и расширяется, когда между узлами определяется сходство, что позволяет рассматривать альтернативные определения сообществ, таких как гильдии (т. е. группы узлов, имеющие одинаковое количество связей по отношению к одним и тем же соседям, но не обязательно связанные сами по себе). Эти методы могут быть расширены для рассмотрения многомерных сетей, например, когда мы имеем дело с сетями, имеющими узлы с разными типами связей.

Алгоритм

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

Алгоритм Гирвана-Ньюмана возвращает результаты приемлемого качества и популярен, поскольку реализован в ряде стандартных пакетов программного обеспечения. Но он также выполняется медленно, занимая время O( m ² n ) в сети из n вершин и m ребер, что делает его непрактичным для сетей с числом узлов более нескольких тысяч.

Максимизация модульности

Несмотря на известные недостатки, одним из наиболее широко используемых методов обнаружения сообществ является максимизация модульности. Модульность — это функция выгоды, которая измеряет качество конкретного разделения сети на сообщества. Метод максимизации модульности обнаруживает сообщества путем поиска в возможных разделах сети одного или нескольких сообществ с особенно высокой модульностью. Поскольку исчерпывающий поиск по всем возможным разделам обычно невозможен, практические алгоритмы основаны на методах приближенной оптимизации, таких как жадные алгоритмы, имитация отжига или спектральная оптимизация, при этом разные подходы предлагают разные балансы между скоростью и точностью. Популярным подходом к максимизации модульности является метод Лувена , который итеративно оптимизирует местные сообщества до тех пор, пока глобальную модульность больше нельзя будет улучшить, учитывая возмущения в текущем состоянии сообщества. Алгоритм, использующий схему RenEEL, которая является примером парадигмы экстремального ансамблевого обучения (EEL), в настоящее время является лучшим алгоритмом максимизации модульности.

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

Статистический

Методы, основанные на статистических выводах, пытаются подогнать генеративную модель к сетевым данным , которая кодирует структуру сообщества. Общим преимуществом этого подхода по сравнению с альтернативами является его более принципиальный характер и способность решать вопросы, имеющие статистическую значимость . Большинство методов в литературе основаны на стохастической блочной модели. а также варианты, включая смешанное членство, степень-коррекция, и иерархические структуры. Выбор модели может осуществляться с использованием принципиальных подходов, таких как минимальная длина описания. (или, что то же самое, выбор байесовской модели ) и тест отношения правдоподобия . В настоящее время существует множество алгоритмов для эффективного вывода стохастических блочных моделей, включая распространение убеждений. и агломерационный Монте-Карло .

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

Кликовые методы

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

Один из подходов — найти « максимальные клики ». То есть найти клики, которые не являются подграфами какой-либо другой клики. Классическим алгоритмом их поиска является алгоритм Брона-Кербоша . Их перекрытие можно использовать для определения сообществ несколькими способами. Самый простой — рассматривать только максимальные клики, размер которых превышает минимальный размер (количество узлов). Объединение этих клик затем определяет подграф, компоненты которого (несвязные части) затем определяют сообщества. Такие подходы часто реализуются в программном обеспечении для анализа социальных сетей, таком как UCInet.

Альтернативный подход — использовать клики фиксированного размера. $k$. Их перекрытие можно использовать для определения типа $k$-регулярный гиперграф или структура, являющаяся обобщением линейного графа (случай, когда $k=2$), известный как « граф клики ». Графы клик имеют вершины, которые представляют клики в исходном графе, а ребра графа клик фиксируют перекрытие клик в исходном графе. Применение любого из предыдущих методов обнаружения сообществ (которые присваивают каждый узел сообществу) к графу клик затем присваивает каждую клику сообществу. Затем это можно использовать для определения членства узлов в кликах в сообществе. Опять же, поскольку узел может состоять в нескольких кликах, он может быть членом нескольких сообществ.Например, метод кликовой перколяции определяет сообщества как перколяционные кластеры $k$-клики . Для этого этонаходит все $k$-клики в сети, то есть все полные подграфы $k$-узлы.Затем он определяет два $k$-клики будут соседними, если они разделяют $k-1$ узлы, то есть это используется для определения ребер в графе клик. Сообщество тогда определяется как максимальное объединение $k$-клики, в которых мы можем достичь любого $k$-клика от любого другого $k$-клика через серию $k$-кликовые примыкания. То есть сообщества — это всего лишь связные компоненты графа клик. Поскольку узел может принадлежать нескольким различным $k$-кликовые перколяционные кластеры, в то же время сообщества могут перекрываться друг с другом.

Обнаружение сообществ в пространствах скрытых функций

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

Тестирование методов поиска алгоритмов сообществ

Оценка алгоритмов, позволяющих определить, какие из них лучше определяют структуру сообщества, все еще остается открытым вопросом. Он должен быть основан на анализе сетей известной структуры. Типичным примером является тест «четырех групп», в котором сеть делится на четыре группы одинакового размера (обычно по 32 узла в каждой), а вероятности соединения внутри и между группами варьируются для создания более или менее сложных структур для обнаружения. алгоритм. Такие контрольные графики являются частным случаем модели с установленными l-разделами. Кондона . и Карпа , или, в более общем смысле, « стохастических блочных моделей », общего класса моделей случайных сетей, содержащих структуру сообщества Были предложены другие, более гибкие тесты, которые позволяют варьировать размеры групп и нетривиальные распределения степеней, такие как тест LFR. который является расширением теста четырех групп, который включает гетерогенное распределение степени узла и размера сообщества, что делает его более серьезным испытанием методов обнаружения сообществ.

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

Обнаруживаемость

В последние годы различными группами был получен довольно неожиданный результат, который показывает, что в проблеме обнаружения сообществ существует фазовый переход, показывающий, что по мере того, как плотность связей внутри сообществ и между сообществами становится все более одинаковой или обе становятся меньшими (эквивалентно (когда структура сообщества становится слишком слабой или сеть становится слишком разреженной), сообщества внезапно становятся незаметными. В каком-то смысле сами сообщества все еще существуют, поскольку наличие и отсутствие ребер по-прежнему коррелирует с членством в сообществе их конечных точек; но становится теоретически невозможным пометить узлы лучше, чем случайно, или даже отличить граф от графа, созданного с помощью нулевой модели, такой как модель Эрдеша-Реньи, без структуры сообщества. Этот переход не зависит от типа алгоритма, используемого для обнаружения сообществ, а это означает, что существует фундаментальное ограничение на нашу способность обнаруживать сообщества в сетях даже при оптимальном байесовском выводе (т. е. независимо от наших вычислительных ресурсов).

Рассмотрим стохастическую блочную модель с общим количеством $n$ узлы, $q=2$ группы одинакового размера, и пусть $p_{\text{in}}$ и $p_{\text{out}}$ — вероятности соединения внутри и между группами соответственно. Если $p_{\text{in}}>p_{\text{out}}$, сеть будет иметь структуру сообщества, поскольку плотность связей внутри групп будет больше, чем плотность связей между группами. В редком случае $p_{\text{in}}$ и $p_{\text{out}}$ масштабировать как $O(1/n)$ так что средняя степень постоянна:

$p_{\text{in}}=c_{\text{in}}/n$ и $p_{\text{out}}=c_{\text{out}}/n$

Тогда обнаружение сообществ становится невозможным, когда:

$c_{\text{in}}-c_{\text{out}}={\sqrt {2(c_{\text{in}}+c_{\text{out}})}}$

См. также

• Комплексная сеть
• Иерархия
• Теория сетей
• Теория перколяции

Внешние ссылки

• Обнаружение сообществ на графиках – введение
• Существуют ли реализации алгоритмов обнаружения сообществ на графах? – Переполнение стека
• Каковы различия между алгоритмами обнаружения сообществ в igraph? – Переполнение стека