Тест Lancichinetti – Fortunato – Radicchi - Lancichinetti–Fortunato–Radicchi benchmark

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

Алгоритм

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

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

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

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

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

${\displaystyle s_{\min }>k_{\min }}$

${\displaystyle s_{\max }>k_{\max }}$

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

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

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

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

${\displaystyle 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})\})}}}$

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

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

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