Эталон Ланчикинетти – Фортунато – Радикки

Ланчикинетти-Фортунато-Радикки Тест — это алгоритм, который генерирует эталонные сети (искусственные сети, напоминающие сети реального мира). Они имеют заранее известные сообщества и используются для сравнения различных методов обнаружения сообществ. ^{[ 1 ]} Преимущество эталонного теста перед другими методами заключается в том, что он учитывает неоднородность в распределении узлов степеней и размеров сообществ. ^{[ 2 ]}

Алгоритм

Степени узлов и размеры сообществ распределяются по степенному закону с разными показателями степени. Тест предполагает, что и степень, и размер сообщества имеют степенное распределение с разными показателями: $\gamma$ и $\beta$ , соответственно. $N$ количество узлов и средняя степень $\langle k\rangle$ . Есть параметр смешивания $\mu$ , который представляет собой среднюю долю соседних узлов узла, которые не принадлежат ни к одному сообществу, к которому принадлежит эталонный узел. Этот параметр управляет долей ребер между сообществами. ^{[ 2 ]} Таким образом, он отражает количество шума в сети. В крайних случаях, когда $\mu =0$ все ссылки находятся внутри ссылок сообщества, если $\mu =1$ все связи находятся между узлами, принадлежащими разным сообществам. ^{[ 3 ]}

Можно создать эталонную сеть, выполнив следующие шаги.

Шаг 1. Создайте сеть с узлами, подчиняющимися степенному закону распределения с показателем степени. $\gamma$ и выбираем экстремумы распределения $k_{\min }$ и $k_{\max }$ получить желаемую среднюю степень $\langle k\rangle$ .

Шаг 2: $(1-\mu )$ доля ссылок каждого узла приходится на узлы одного и того же сообщества, а доля $\mu$ с другими узлами.

Шаг 3. Определите размеры сообщества на основе степенного распределения с показателем степени. $\beta$ . Сумма всех размеров должна быть равна $N$ . Минимальный и максимальный размеры сообщества $s_{\min }$ и $s_{\max }$ должен удовлетворять определению сообщества, чтобы каждый неизолированный узел входил хотя бы в одно сообщество:

s_{\min }>k_{\min }

s_{\max }>k_{\max }

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

Шаг 5. Реализуйте перемонтирование узлов, сохраняя те же уровни узлов, но затрагивая только долю внутренних и внешних ссылок, так, чтобы количество ссылок за пределами сообщества для каждого узла было примерно равно параметру смешивания. $\mu$ . ^{[ 2 ]}

Тестирование

Рассмотрим разделение на сообщества, которые не перекрываются. Сообщества случайно выбранных узлов на каждой итерации следуют $p(C)$ распределение, которое представляет вероятность того, что случайно выбранный узел принадлежит сообществу $C$ . Рассмотрим раздел той же сети, который был предсказан каким-то алгоритмом поиска сообщества и имеет $p(C_{2})$ распределение. Тестовый раздел имеет $p(C_{1})$ распределение. Совместное распространение $p(C_{1},C_{2})$ . Сходство этих двух разделов фиксируется нормализованной взаимной информацией .

I_{n}={\frac {\sum _{C_{1},C_{2}}p(C_{1},C_{2})\log _{2}{\frac {p(C_{1},C_{2})}{p(C_{1})p(C_{2})}}}{{\frac {1}{2}}H(\{p(C_{1})\})+{\frac {1}{2}}H(\{p(C_{2})\})}}

Если $I_{n}=1$ тест и обнаруженные разделы идентичны, и если $I_{n}=0$ тогда они независимы друг от друга. ^{[ 4 ]}

Ссылки

^ Хуа-Вэй Шен (2013). «Структура сообщества сложных сетей». Springer Science & Business Media. 11–12.
^ Перейти обратно: ^а ^б ^с А. Ланчикинетти, С. Фортунато и Ф. Радикки. (2008) Контрольные графики для тестирования алгоритмов обнаружения сообществ. Физический обзор E, 78. arXiv : 0805.4770
^ Тван ван Лаарховен и Елена Маркиори (2013). «Обнаружение сетевого сообщества с помощью классификаторов ребер, обученных на графах LFR». https://www.cs.ru.nl/~elenam/paper-learning-community.pdf. Архивировано 3 ноября 2018 г. в Wayback Machine.
^ Барабаси, А.-Л. (2014). «Сетевая наука». Глава 9: Сообщества.

[1] Хуа-Вэй Шен (2013). «Структура сообщества сложных сетей». Springer Science & Business Media. 11–12.

[original-2] Перейти обратно: ^а ^б ^с А. Ланчикинетти, С. Фортунато и Ф. Радикки. (2008) Контрольные графики для тестирования алгоритмов обнаружения сообществ. Физический обзор E, 78. arXiv : 0805.4770

[3] Тван ван Лаарховен и Елена Маркиори (2013). «Обнаружение сетевого сообщества с помощью классификаторов ребер, обученных на графах LFR». https://www.cs.ru.nl/~elenam/paper-learning-community.pdf. Архивировано 3 ноября 2018 г. в Wayback Machine.

[4] Барабаси, А.-Л. (2014). «Сетевая наука». Глава 9: Сообщества.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]