В чем разница между алгоритмами определения сообществ в igraph?

У меня есть список из около 100 объектов igraph, у типичного объекта около 700 вершин и 3500 ребер.

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

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

Вот краткое описание алгоритмов обнаружения сообществ, которые в настоящее время реализованы в igraph:

• edge.betweenness.communityпредставляет собой процесс иерархической декомпозиции, при котором ребра удаляются в порядке убывания их оценок промежуточности ребер (т. е. количества кратчайших путей, которые проходят через данное ребро). Это мотивировано тем фактом, что ребра, соединяющие разные группы, с большей вероятностью будут содержаться в нескольких кратчайших путях просто потому, что во многих случаях они являются единственным вариантом перехода от одной группы к другой. Этот метод дает хорошие результаты, но он очень медленный из-за вычислительной сложности вычислений промежуточности границ, а также из-за того, что оценки промежуточности необходимо пересчитывать после каждого удаления ребер. Ваши графы с ~ 700 вершинами и ~ 3500 ребрами находятся около верхнего предела размера графов, которые можно анализировать с помощью этого подхода. Еще один недостаток в том, чтоedge.betweenness.communityстроит полную дендрограмму и не дает вам никаких указаний относительно того, где разрезать дендрограмму для получения окончательных групп, поэтому вам придется использовать другие меры, чтобы решить это (например, оценка модульности разделов на каждом уровне дендрограмма).

• fastgreedy.communityэто еще один иерархический подход, но он идет снизу вверх, а не сверху вниз. Он пытается жадно оптимизировать функцию качества, называемую модульностью. Первоначально каждая вершина принадлежит отдельному сообществу, и сообщества объединяются итеративно, так что каждое слияние является локально оптимальным (т.е. дает наибольшее увеличение текущего значения модульности). Алгоритм останавливается, когда невозможно больше увеличить модульность, поэтому он дает вам группировку, а также дендрограмму. Это быстрый метод, который обычно используют в первом приближении, поскольку у него нет параметров для настройки. Однако известно, что он страдает пределом разрешения, то есть сообщества ниже заданного порога размера (в зависимости от количества узлов и ребер, если я правильно помню) всегда будут объединены с соседними сообществами.

• walktrap.community- подход, основанный на случайных блужданиях. Общая идея заключается в том, что если вы выполняете случайные обходы по графу, то они с большей вероятностью останутся в пределах одного сообщества, потому что есть только несколько ребер, которые выходят за пределы данного сообщества. Walktrap выполняет короткие случайные блуждания из 3-4-5 шагов (в зависимости от одного из своих параметров) и использует результаты этих случайных блужданий для объединения отдельных сообществ по восходящей схеме, например fastgreedy.community. Опять же, вы можете использовать показатель модульности, чтобы выбрать, где вырезать дендрограмму. Это немного медленнее, чем быстрый жадный подход, но также немного точнее (согласно оригинальной публикации).

• spinglass.communityэто подход из статистической физики, основанный на так называемой модели Поттса. В этой модели каждая частица (то есть вершина) может находиться в одном из c спиновых состояний, а взаимодействия между частицами (то есть ребрами графа) определяют, какие пары вершин предпочли бы оставаться в одном и том же спиновом состоянии, а какие. предпочитают иметь разные спиновые состояния. Затем модель моделируется для заданного количества шагов, и спиновые состояния частиц в конечном итоге определяют сообщества. Последствия следующие: 1) В конечном итоге не будет больше, чем c сообществ, хотя вы можете установить c до 200, что, вероятно, будет достаточно для ваших целей. 2) Может быть меньше cсообществ в конце концов, так как некоторые из спиновых состояний могут стать пустыми. 3) Не гарантируется, что узлы в полностью удаленных (или отключенных) частях сети имеют разные спиновые состояния. Скорее всего, это проблема только для несвязанных графов, поэтому я бы не стал беспокоиться об этом. Этот метод не особенно быстрый и не детерминированный (из-за самого моделирования), но имеет настраиваемый параметр разрешения, который определяет размеры кластера. Вариант метода spinglass также может учитывать отрицательные ссылки (т. Е. Ссылки, конечные точки которых предпочитают находиться в разных сообществах).

• leading.eigenvector.community- это иерархический подход сверху вниз, который снова оптимизирует функцию модульности. На каждом шаге график разбивается на две части таким образом, что само разделение приводит к значительному увеличению модульности. Разделение определяется путем оценки ведущего собственного вектора так называемой матрицы модульности, а также существует условие остановки, которое предотвращает дальнейшее разделение тесно связанных групп. Из-за задействованных вычислений собственных векторов это может не работать на вырожденных графах, где решатель собственных векторов ARPACK нестабилен. На невырожденных графах он, вероятно, даст более высокий балл модульности, чем быстрый жадный метод, хотя он немного медленнее.

• label.propagation.communityэто простой подход, в котором каждому узлу присваивается одна из k меток. Затем метод повторяется итеративно и повторно назначает метки узлам таким образом, что каждый узел синхронно принимает наиболее частую метку своих соседей. Метод останавливается, когда метка каждого узла является одной из наиболее частых меток в его окрестности. Это очень быстро, но дает разные результаты в зависимости от начальной конфигурации (которая определяется случайным образом), поэтому следует запускать метод большое количество раз (скажем, 1000 раз для графика), а затем создавать согласованную маркировку, которая может быть утомительно.

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

В любом случае, я бы, вероятно, выбрал fastgreedy.communityили walktrap.communityв качестве первого приближения, а затем оценил бы другие методы, когда выяснится, что эти два по какой-то причине не подходят для конкретной проблемы.

Краткое описание различных алгоритмов обнаружения сообщества можно найти здесь: http://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/

Примечательно, что алгоритм InfoMAP - недавний новичок, который может быть полезен (он также поддерживает ориентированные графы).