Понимание обнаружения сообщества Infomap

Question

Мне нужно понятное описание алгоритма обнаружения сообщества Infomap. Я читал газеты, но мне было не ясно. Мои вопросы:

1. Как в принципе работает алгоритм?
2. При чем тут случайные прогулки?
3. Что такое уравнение карты и в чем (очевидно) разница с оптимизацией модульности? (Был пример, приведенный в статье на рис. 3, но я этого не понял)
4. На их домашней странице даны 2 улучшения. Первый - это движения подмодуля, а второй - движения с одним узлом. Почему они используются и почему объединенные модули не разделяются?

Домашняя страница: http://www.mapequation.org/code.html

Документ: http://www.mapequation.org/assets/publications/EurPhysJ2010Rosvall.pdf

Answer 1

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

Давайте распакуем, что это значит. Центральный объект - это случайный бродяга, исследующий сеть с вероятностью того, что бродяга переходит между двумя узлами, заданными его марковской матрицей переходов. На данный момент мы эффективно закодировали нашу сеть с индивидуальным кодовым словом для каждого узла. Однако в большинстве реальных сетей мы знаем, что существуют области сети, такие, что как только случайный бродяга входит в регион, он имеет тенденцию оставаться там в течение длительного времени, и перемещения между регионами относительно редки. Это позволяет нам комбинаторно объединять кодовые слова в коды Хаффмана: мы можем использовать код префикса для каждой области, а затем использовать уникальное кодовое слово для каждого узла в модуле, но мы можем повторно использовать эти кодовые слова уровня узла для каждого модуля. Эту же интуицию можно собрать, глядя на названия улиц; было бы сумасшествием иметь уникальное название улицы для каждой улицы в США, вместо этого мы используем штаты и города, а затем указываем название улицы, что позволяет нам повторно использовать названия улиц между городами (сколько там главных улиц?).

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

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

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