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

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список смежности  / матрица Список заболеваемости  / матрица Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Близость Близость PageRank Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия /СЭР
Списки Категории
Темы Программного обеспечения Сетевые ученые Категория: Теория сетей Категория: Теория графов

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

Алгоритм

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

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

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

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

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

${ displaystyle s _ { min}> к _ { min}}$

${ displaystyle s _ { max}> к _ { 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]

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