Алгоритм фильтрации неравномерности взвешенной сети - Disparity filter algorithm of weighted network

Фильтр диспаратности^[1] представляет собой алгоритм сокращения сети для извлечения основной структуры неориентированных взвешенная сеть. Многие сети реального мира, такие как сети цитирования, пищевой сети сети аэропортов отображают статистическое распределение узлов с тяжелыми хвостами ' масса и сила. Фильтр диспаратности может значительно уменьшить сеть, не разрушая многомасштабный характер сети. Алгоритм разработан М. Анхелесом Серрано, Марианом Богуна и Алессандро Веспиньяни.

Обзор других алгоритмов сокращения сети и их ограничений

kразложение ядра

k-core-декомпозиция - это алгоритм, который сводит граф к максимальный связный подграф вершин не ниже степени k. Этот алгоритм может применяться только к невзвешенным графам.

Минимальное остовное дерево

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

Глобальный порог веса

Взвешенный граф можно легко свести к подграфу, в котором вес любого из ребер больше заданного порога ш_c. Этот метод был применен для изучения сопротивления пищевых сетей.^[2] и функциональные сети, которые соединяют коррелированные участки человеческого мозга.^[3] Недостаток этого метода в том, что он не учитывает узлы с малой прочностью. В реальных сетях и сила, и распределение веса в целом следуют распределениям с тяжелыми хвостами, которые охватывают несколько степеней величины. Применение простого отсечения по весу удалит всю информацию ниже порогового значения.

Алгоритм фильтра диспаратности

В нулевая модель нормализованного распределения веса

В сетевая наука, сила обозначена как s_я узла я определяется как s_я = Σ_jш_ij, куда ш_ij это масса связи между я и j.

Чтобы применить алгоритм фильтрации диспаратности, не пропуская узлы с низкой силой, нормализованный вес п_ij определяется как п_ij = ш_ij/s_я. В нулевой модели нормализованные веса определенного узла со степенью k генерируется так: k - 1 контакт случайным образом назначается между интервалом 0 и 1. Затем интервал делится на k подынтервалы. Длина подынтервала представляет собой нормализованный вес каждой ссылки в нулевой модели.

Последовательно и на основе нулевой модели мы можем вывести, что нормализованное распределение веса узла со степенью k следует ${\displaystyle \rho (x)\,dx=(k-1)(1-x)^{k-2}\,dx}$.^[1]

Фильтр диспаратности

Алгоритм фильтра диспаратности основан на p-значение^[4] тест статистической значимости^[5] нулевой модели: для данного нормализованного веса п_ij, p-значение α_ij из п_ij на основе нулевой модели дается ${\displaystyle \alpha _{ij}=1-(k-1)\int _{0}^{p_{ij}}(1-x)^{k-2}\,dx}$ что сводится к ${\displaystyle \alpha _{ij}=(1-p_{ij})^{k-1}}$. Значение α_ij вероятность того, что нормализованный вес будет больше или равен п_ij в рамках данной нулевой модели. Установив уровень значимости α (от 0 до 1) для любого звена с нормализованным весом п_ij, если α_ij больше чем α, он будет отфильтрован. Изменяя α, мы можем постепенно удалять нерелевантные ссылки, таким образом эффективно извлекая структуру магистрали взвешенной сети.^[1]

Обобщения

Pólya Filter

Было показано, что алгоритм фильтра диспаратности является частным случаем фильтра Полиа.^[6] (построенный на знаменитой комбинаторной схеме, известной как Pólya Urn ). Фильтр Pólya может адаптировать процедуру фильтрации к собственной неоднородности сети, используя процедуру максимального правдоподобия для установки своего свободного параметра. ${\displaystyle a}$, которые представляют собой силу самоусиливающегося механизма, управляющего основной схемой урны. Учитывая уровень значимости ${\displaystyle \alpha }$, фильтр Pólya, как было показано, создает гораздо более разреженные магистрали, чем фильтр диспаратности, и все же может удерживать наиболее заметные^[7] ссылки системы.

Смотрите также

• kразложение ядра
• Минимальное остовное дерево

внешняя ссылка

• Реализация алгоритма фильтра диспаратности на Python
• Реализация алгоритма фильтра диспаратности в R

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

1. Серрано, М. Ангелес; Богуна, Мариан; Веспиньяни, Алессандро (2009), "Извлечение многомасштабной основы сложных взвешенных сетей", Труды Национальной академии наук, 106 (16): 6483–6488, arXiv:0904.2389, Bibcode:2009ПНАС..106.6483С, Дои:10.1073 / pnas.0808904106, ЧВК  2672499, PMID  19357301.
2. Эгуилуз, Виктор М; Кьялво, Данте Р; Чекки, Гильермо А; Балики, Марван; Апкариан, Ваня (2005), «Безмасштабные функциональные сети мозга», Письма с физическими проверками, 94 (1): 018102, arXiv:cond-mat / 0309092, Bibcode:2005PhRvL..94a8102E, Дои:10.1103 / PhysRevLett.94.018102, PMID  15698136.
3. Аллезина, Стефано; Бодини, Антонио; Бондавалли, Кристина (2006), «Вторичные вымирания в экологических сетях: выявлены узкие места», Экологическое моделирование, 194 (1): 150–161, Дои:10.1016 / j.ecolmodel.2005.10.016.
4. Гудман, С. Н. (1999). «К доказательной медицинской статистике. 1: Ошибка значения P». Анналы внутренней медицины. 130 (12): 995–1004. Дои:10.7326/0003-4819-130-12-199906150-00008. PMID  10383371.
5. Р. А. Фишер (1925).Статистические методы для научных работников, Эдинбург: Оливер и Бойд, 1925, стр. 43.
6. Маркаччоли, Риккардо; Ливан, Джакомо (14 февраля 2019 г.). «Подход Pólya urn к фильтрации информации в сложных сетях». Nature Communications. 10 (1): 1–10. Дои:10.1038 / s41467-019-08667-3. ISSN  2041-1723. PMID  30765706.
7. Грейди, Дэниел; Тиманн, Кристиан; Брокманн, Дирк (29 мая 2012 г.). «Надежная классификация основных звеньев в сложных сетях». Nature Communications. 3 (1): 1–10. Дои:10.1038 / ncomms1847. ISSN  2041-1723.