Метод кликовой перколяции
Метод кликовой перколяции [1] популярный подход к анализу перекрывающейся структуры сообщества сетей — . Термин «сетевое сообщество» (также называемый модулем, кластером или сплоченной группой). не имеет общепринятого однозначного определения и обычно определяется как группа узлов, которые более тесно связаны друг с другом, чем с другими узлами в сети. Существует множество альтернативных методов обнаружения сообществ в сетях. [2] например, алгоритм Гирвана-Ньюмана , иерархическая кластеризация и модульности максимизация .
Определения
[ редактировать ]Метод кликовой перколяции (CPM)
[ редактировать ]Метод перколяции клик строит сообщества из k -клик , которые соответствуют полным (полностью связным) подграфам из k узлов. (Например, k -клика при k = 3 эквивалентна треугольнику). Две k -клики считаются смежными, если они имеют общее k - 1 узел. Сообщество определяется как максимальное объединение k -клик, до которых можно добраться друг от друга через ряд соседних k -клик. Такие сообщества лучше всего интерпретировать с помощью шаблона k -клики (объекта, изоморфного полному графу из k узлов). Такой шаблон можно поместить в любую k -клику в графе и перенести на соседнюю k -клику, переместив один из ее узлов и оставив фиксированными другие k - 1 узлов. Таким образом, сообщества k -клики сети — это все те подграфы, которые можно полностью изучить, накатив в них шаблон k -клики, но нельзя покинуть по этому шаблону.
Это определение допускает перекрытие между сообществами естественным образом, как показано на рис. 1, где показаны четыре сообщества k -клики при k = 4. Сообщества имеют цветовую кодировку, а перекрытие между ними подчеркнуто красным. Приведенное выше определение также является локальным: если определенный подграф соответствует критериям, позволяющим считать его сообществом, то он останется сообществом, независимым от того, что происходит с другой частью сети далеко. Напротив, при поиске сообществ путем оптимизации по глобальной величине изменение в сети может также изменить форму сообществ в невозмущенных регионах. Более того, было показано, что глобальные методы могут страдать от проблемы ограничения разрешения. [3] где размер наименьшего сообщества, которое можно извлечь, зависит от размера системы. Такое определение местного сообщества, как здесь, автоматически обходит эту проблему.
Поскольку даже небольшие сети могут содержать огромное количество k -клик, реализация этого подхода основана на обнаружении всех максимальных клик, а не отдельных k -клик. [1] клики графа Это неизбежно требует нахождения максимальной , что является NP-трудной задачей. (Подчеркнем читателю, что найти максимальную клику гораздо сложнее, чем найти одну максимальную клику.) Это означает, что, хотя сети с несколькими миллионами узлов уже успешно анализировались с помощью этого подхода, [4] в худшем случае сложность времени выполнения экспоненциально зависит от количества узлов.
-
Рис.1. Иллюстрация сообществ k -клики при k = 4.
Метод направленной кликовой перколяции (CPMd)
[ редактировать ]В сети с направленными связями направленная k -клика представляет собой полный подграф с k узлами, удовлетворяющими следующему условию. узлов K можно упорядочить так, чтобы между произвольной парой из них существовала направленная связь, указывающая от узла с более высоким рангом к узлу с меньшим рангом. Метод направленной перколяции клик определяет направленные сетевые сообщества как перколяционные кластеры направленных k -клик.
Метод взвешенной кликовой перколяции (CPMw)
[ редактировать ]В сети с взвешенными ссылками взвешенная k -клика представляет собой полный подграф с k узлами, в котором среднее геометрическое весов k ( k - 1)/2 ссылок внутри k -клики больше выбранного порогового значения I . Метод взвешенной перколяции клик определяет взвешенные сетевые сообщества как перколяционные кластеры взвешенных k -клик. Обратите внимание, что среднее геометрическое весов ссылок внутри подграфа называется интенсивностью этого подграфа. [5]
Обобщения графа клики
[ редактировать ]Методы перколяции кликов можно обобщить, регистрируя различную степень перекрытия между различными k -кликами. Затем это определяет новый тип графа, граф клики . [6] где каждая k -клика в исходном графе представлена вершиной в новом графе клик. Ребра в графе клик используются для записи силы перекрытия клик в исходном графе. Затем к этому графу клик можно применить любой метод обнаружения сообщества , чтобы идентифицировать кластеры в исходном графе через структуру k -клики.
Например, в простом графе мы можем определить перекрытие между двумя k -кликами как количество вершин, общих для обеих k -клик. В этом случае метод перколяции клик эквивалентен пороговому определению этого графа клик, отбрасывая все ребра с весом меньше (k-1), а оставшиеся связные компоненты образуют сообщества клик, найденные в CPM. Для k=2 клики являются ребрами исходного графа, а граф клик в этом случае является линейным графом исходной сети.
На практике использование количества общих вершин в качестве меры силы перекрытия клик может дать плохие результаты, поскольку в исходном графе клики, имеющие намного больше k вершин, будут доминировать в графе клик. Проблема возникает потому, что если вершина находится в n различных k -кликах, она будет вносить вклад в n(n-1)/2 ребра в таком графе клик. Простое решение состоит в том, чтобы позволить каждой вершине, общей для двух перекрывающихся k клик, вносить вес, равный 1/n, при измерении силы перекрытия двух k -клик.
В общем, точка зрения графа кликов — полезный способ найти обобщения стандартных методов перколяции клик, чтобы обойти любые возникающие проблемы. Он даже показывает, как описывать расширения этих методов на основе других мотивов , подграфов, отличных от k -клик. В этом случае граф клики лучше всего рассматривать как частный пример гиперграфа .
Перколяционный переход в CPM
[ редактировать ]Модель Эрдеша-Реньи показывает серию интересных переходов, когда вероятность p соединения двух узлов увеличивается. Для каждого k можно найти определенную пороговую вероятность p c, выше которой k -клики организуются в гигантское сообщество. [7] [8] [9] (Размер гигантского сообщества сравним с размером системы, иными словами, гигантское сообщество занимает конечную часть системы даже в термодинамическом пределе.) Этот переход аналогичен перколяционному переходу в статистической физике . Аналогичное явление можно наблюдать и во многих реальных сетях: если k велико, то в качестве сообществ принимаются только наиболее плотно связанные части, поэтому они обычно остаются небольшими и рассредоточенными. При уменьшении k число и размер сообществ начинают расти. Однако в большинстве случаев может быть достигнуто критическое значение k , ниже которого возникает гигантское сообщество, размывающее детали структуры сообщества за счет слияния (и делая невидимыми) множество более мелких сообществ.
Приложения
[ редактировать ]Метод кликовой перколяции использовался для обнаружения сообществ в результате исследований метастазов рака. [10] [11] через различные социальные сети [4] [12] [13] [14] [15] документировать кластеризацию [16] и экономичные сети. [17]
Алгоритмы и программное обеспечение
[ редактировать ]Существует несколько реализаций перколяции кликов. Метод перколяции кликов был впервые реализован и популяризирован программой CFinder [1] (бесплатной программой для некоммерческого использования) для обнаружения и визуализации перекрывающихся сообществ в сетях. Программа обеспечивает настраиваемую визуализацию и позволяет легко перемещаться по найденным сообществам. Пакет также содержит версию программы для командной строки, которая подходит для написания сценариев.
Более быстрая реализация ( доступная под лицензией GPL) была реализована другой группой. [18] Другой пример, который также очень быстр в определенных контекстах, — это алгоритм SCP. [19]
Параллельные алгоритмы
[ редактировать ]Параллельная версия метода перколяции кликов была разработана и разработана С. Майнарди и др. . [20] Используя современные многоядерные/многопроцессорные вычислительные архитектуры, этот метод позволяет извлекать сообщества k -клик из очень больших сетей, таких как Интернет. [21] Авторы выпустили исходный код метода под лицензией GPL и сделали его бесплатным для сообщества.
См. также
[ редактировать ]- Социальная сеть
- Структура сообщества
- Обзорные статьи Сообщества в сетях
- Фортунато, Санто (2010). «Обнаружение сообществ в графиках». Отчеты по физике . 486 (3–5): 75–174. arXiv : 0906.0612 . Бибкод : 2010PhR...486...75F . дои : 10.1016/j.physrep.2009.11.002 . S2CID 10211629 .
- Библиография ссылок на структуру сообщества
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Палла, Гергели (2005). «Раскрытие перекрывающейся структуры сообщества сложных сетей в природе и обществе». Природа . 435 (7043): 814–818. arXiv : физика/0506133 . Бибкод : 2005Natur.435..814P . дои : 10.1038/nature03607 . ПМИД 15944704 . S2CID 3250746 .
- ^ Фортунато, Санто (2010). «Обнаружение сообществ в графиках». Отчеты по физике . 486 (3–5): 75–174. arXiv : 0906.0612 . Бибкод : 2010PhR...486...75F . дои : 10.1016/j.physrep.2009.11.002 . S2CID 10211629 .
- ^ Фортунато, С. (2007). «Предел разрешения при обнаружении сообщества» . Труды Национальной академии наук . 104 (1): 36–41. arXiv : физика/0607100 . Бибкод : 2007PNAS..104...36F . дои : 10.1073/pnas.0605965104 . ПМЦ 1765466 . ПМИД 17190818 .
- ^ Перейти обратно: а б Палла, Гергели (2007). «Количественная оценка эволюции социальных групп». Природа . 446 (7136): 664–667. arXiv : 0704.0744 . Бибкод : 2007Natur.446..664P . дои : 10.1038/nature05670 . ПМИД 17410175 . S2CID 4420074 .
- ^ Оннела, Юкка-Пекка; Сарамяки, Яри; Кертеш, Янош; Каски, Киммо (2005). «Интенсивность и связность мотивов во взвешенных сложных сетях». Физический обзор E . 71 (6): 065103. arXiv : cond-mat/0408629 . Бибкод : 2005PhRvE..71f5103O . дои : 10.1103/PhysRevE.71.065103 . ПМИД 16089800 . S2CID 14259722 .
- ^ Эванс, ТС (2010). «Графы клик и перекрывающиеся сообщества». Журнал статистической механики: теория и эксперимент . 2010 (12): P12037. arXiv : 1009.0638 . Бибкод : 2010JSMTE..12..037E . дои : 10.1088/1742-5468/2010/12/P12037 . S2CID 2783670 .
- ^ Дереньи, Имре; Палла, Грегори; Вичек, Тамаш (2005). «Проникновение клик в случайных сетях». Письма о физических отзывах . 94 (16): 160202. arXiv : cond-mat/0504551 . Бибкод : 2005PhRvL..94p0202D . doi : 10.1103/PhysRevLett.94.160202 . ПМИД 15904198 . S2CID 15452087 .
- ^ Палла, Грегори; Дереньи, Имре; Вичек, Тамаш (2006). «Критическая точка перколяции k-клики в графе Эрдеша – Реньи». Журнал статистической физики . 128 (1–2): 219–227. arXiv : cond-mat/0610298 . Бибкод : 2007JSP...128..219P . дои : 10.1007/s10955-006-9184-x . S2CID 14499453 .
- ^ Ли, Мин; Дэн, Юджин; Ван, Бин-Хонг (2015). «Просачивание клик в случайных графах». Физический обзор E . 92 (4): 042116. arXiv : 1508.01878 . Бибкод : 2015PhRvE..92d2116L . дои : 10.1103/PhysRevE.92.042116 . ПМИД 26565177 . S2CID 7298260 .
- ^ Йонссон, ПФ (2006). «Глобальные топологические особенности раковых белков в интерактоме человека» . Биоинформатика . 22 (18): 2291–2297. doi : 10.1093/биоинформатика/btl390 . ПМЦ 1865486 . ПМИД 16844706 .
- ^ Йонссон, ПФ; Каванна, Т; Зича, Д; Бейтс, Пенсильвания (2006). «Кластерный анализ сетей, созданных посредством гомологии: автоматическая идентификация важных белковых сообществ, участвующих в метастазировании рака» . БМК Биоинформатика . 7 :2. дои : 10.1186/1471-2105-7-2 . ПМЦ 1363365 . ПМИД 16398927 .
- ^ Гонсалес, Марта С.; Линд, Педро Г.; Херрманн, Ганс Дж. (2006). «Система мобильных агентов для моделирования социальных сетей». Письма о физических отзывах . 96 (8): 088702. arXiv : физика/0602091 . Бибкод : 2006PhRvL..96h8702G . doi : 10.1103/PhysRevLett.96.088702 . ПМИД 16606237 . S2CID 17587824 .
- ^ Кумпула, Юсси М.; Оннела, Юкка-Пекка; Сарамяки, Яри; Каски, Киммо; Кертеш, Янош (2007). «Появление сообществ во взвешенных сетях». Письма о физических отзывах . 99 (22): 228701. arXiv : 0708.0925 . Бибкод : 2007PhRvL..99v8701K . doi : 10.1103/PhysRevLett.99.228701 . ПМИД 18233339 . S2CID 11806575 .
- ^ Тойвонен, Риитта; Оннела, Юкка-Пекка; Сарамяки, Яри; Хювёнен, Йёркки; Каски, Киммо (2006). «Модель для социальных сетей». Физика А: Статистическая механика и ее приложения . 371 (2): 851–860. arXiv : физика/0601114 . Бибкод : 2006PhyA..371..851T . дои : 10.1016/j.physa.2006.03.050 . S2CID 13919003 .
- ^ Гонсалес, MC; Херрманн, HJ; Кертеш, Дж.; Вичек, Т. (2007). «Структура сообщества и этнические предпочтения в сетях школьной дружбы». Физика А: Статистическая механика и ее приложения . 379 (1): 307–316. arXiv : физика/0611268 . Бибкод : 2007PhyA..379..307G . дои : 10.1016/j.physa.2007.01.002 . S2CID 18069092 .
- ^ Гао, Вэй; Вонг, Кам-Фай (2006). «Естественная кластеризация документов путем перколяции кликов в случайных графах». Информационно-поисковая технология . Конспекты лекций по информатике. Том. 4182. стр. 119–131. дои : 10.1007/11880592_10 . ISBN 978-3-540-45780-0 .
- ^ Хеймо, Тапио; Сарамяки, Яри; Оннела, Юкка-Пекка; Каски, Киммо (2007). «Спектральные и сетевые методы анализа корреляционных матриц доходности акций». Физика А: Статистическая механика и ее приложения . 383 (1): 147–151. arXiv : физика/0703061 . Бибкод : 2007PhyA..383..147H . дои : 10.1016/j.physa.2007.04.124 . S2CID 41788246 .
- ^ Рид, Ф.; МакДейд, А.; Херли, Н.; Вичек, Тамаш (2012). «Перколяционные вычисления в сложных сетях». Международная конференция IEEE/ACM, 2012 г., посвященная достижениям в области анализа и анализа социальных сетей . стр. 274–281. arXiv : 1205.0038 . дои : 10.1109/ASONAM.2012.54 . ISBN 978-1-4673-2497-7 . S2CID 14088073 .
- ^ Кумпула, Юсси М.; Кивеля, Микко; Каски, Киммо; Сарамяки, Яри (2008). «Последовательный алгоритм быстрой перколяции клик». Физический обзор E . 78 (2): 026109. arXiv : 0805.1449 . Бибкод : 2008PhRvE..78b6109K . дои : 10.1103/PhysRevE.78.026109 . ПМИД 18850899 . S2CID 15531110 .
- ^ Грегори, Энрико; Ленцини, Лучано; Майнарди, Симона (2013). «Обнаружение параллельного сообщества k -клики в крупномасштабных сетях» (PDF) . Транзакции IEEE в параллельных и распределенных системах . 24 (8): 1651–1660. дои : 10.1109/TPDS.2012.229 . S2CID 14740818 .
- ^ Грегори, Энрико; Ленцини, Лучано; Орсини, Кьяра (2011). «Сообщества K-клики в Интернете. Топологический граф уровня AS». 2011 31-я Международная конференция по распределенным вычислительным системам . стр. 134–139. дои : 10.1109/ICDCSW.2011.17 . ISBN 978-1-4577-0384-3 . S2CID 9921893 .