Обнаружение сообществ — Кластеризация графов в сетях
- Автор метода
- Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
- Год
- 2002–2019 (algorithm family)
- Тип
- Graph-partitioning / clustering algorithm family
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Обнаружение сообществ — это семейство алгоритмов разбиения графов, которые обнаруживают плотно связанные подгруппы — сообщества — внутри сети.
Впервые формализованная с помощью меры модульности Гирваном и Ньюманом (2002), эта область быстро развивалась благодаря методу Лувейна (Блондель и др., 2008), уточнению Лейдена (Трааг и др., 2019) и информационно-теоретическому подходу Infomap. Все варианты отвечают на один и тот же вопрос: какие узлы кластеризуются между собой плотнее, чем с остальной частью сети?
Интуиция метода
Представьте себе большую социальную сеть, где одни люди в основном общаются со своим ближайшим кругом, лишь изредка выходя за его пределы. Обнаружение сообществ автоматически находит эти круги, без необходимости предварительной разметки. Алгоритм перегруппировывает узлы так, чтобы внутренние связи были плотными, а межгрупповые — разреженными, максимизируя показатель качества, называемый модульностью (или, в Infomap, минимизируя длину описания случайного блуждания по сети). Результатом является разбиение: каждый узел принадлежит ровно одному сообществу, и сеть можно визуализировать как набор связных кластеров.
История
Изучение структуры сообществ в сетях было поставлено на количественную основу Гирваном и Ньюманом (2002), которые ввели понятие центральности по посредственности как инструмента для иерархического разделения сети. Ньюман и Гирван (2004) затем формализовали меру модульности Q, которая стала стандартным критерием качества. Блондель и др. (2008) опубликовали метод Лувейна — двухфазную жадную оптимизацию, которая сделала высококачественное обнаружение сообществ практичным для сетей с миллионами узлов. Трааг, Вальтман и ван Эйк (2019) выявили структурный недостаток в Лувейне — то, что он может производить внутренне несвязные сообщества — и разработали алгоритм Лейдена для его исправления, гарантируя хорошо связанные разбиения. Параллельно Россвалл и Бергстром (2008) разработали Infomap, который переформулирует обнаружение сообществ как задачу сжатия: найти разбиение, которое минимизирует длину описания случайного блуждания по сети.
Когда применять
Обнаружение сообществ целесообразно, когда у вас есть сеть (минимум ~20 узлов) и вы хотите обнаружить скрытую групповую структуру без предварительного определения групп. Оно подходит для исследовательских, описательных целей и целей классификации на бинарных или непрерывных данных с весами ребер, включая поперечные и продольные сетевые данные. Оно не требует атрибутов узлов или нормальных распределений. Метод особенно хорошо подходит, когда количество сообществ неизвестно. Если сеть слишком мала (менее 20 узлов), предпочтительны описательные сетевые статистики. Результаты чувствительны к определениям весов ребер и плотности сети, поэтому эти выборы заслуживают тщательного обдумывания.
Ограничения и замечания
- Оптимизация модульности подвержена локальным оптимумам; результаты могут различаться при разных запусках и должны сообщаться как лучший из нескольких запусков.
- Предел разрешения означает, что очень маленькие сообщества в больших сетях могут быть объединены, маскируя мелкозернистую структуру.
- Результаты чувствительны к способу определения весов ребер; различные схемы взвешивания могут давать существенно разные разбиения.
- Сложность Гирвана-Ньюмана составляет O(m²n), что делает его непрактичным для больших сетей; для масштабирования следует предпочесть Лувейн или Лейден.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Не требует предварительного указания количества сообществ — размер разбиения определяется данными.
- Масштабируется до больших сетей: Лувейн и Лейден работают почти за линейное время, что делает их практичными для сетей с миллионами узлов.
- Лейден гарантирует хорошо связанные, внутренне сплоченные сообщества, исправляя недостаток несвязных сообществ в Лувейне.
- Применимо как к невзвешенным, так и к взвешенным сетям без предположений о распределении данных.
Применение
- Идентификация исследовательских кластеров в сетях цитирования и соавторства для картирования научных областей.
- Обнаружение функциональных модулей в сетях белок-белковых взаимодействий в биологии.
- Поиск сообществ пользователей в сетях социальных медиа и коммуникаций для анализа поведения.
- Сегментация клиентских сетей в бизнесе и маркетинге для выявления сплоченных групп клиентов.
- Обнаружение структурных блоков в сетях инфраструктуры, транспорта или цепочек поставок.
Как это работает
Как это работает
Входными данными является граф, узлы которого представляют сущности (люди, веб-страницы, белки, цитаты), а ребра — отношения между ними. Ребра могут быть направленными или ненаправленными и могут иметь веса. Структура смежности — какие узлы связаны и насколько сильно — является единственным входным параметром, необходимым алгоритмам. Метки узлов, классы или внешние атрибуты не требуются, хотя их можно использовать для последующей проверки результатов.
Каждый алгоритм начинается с начального назначения узлов сообществам. В Лувейне и Лейдене каждый узел изначально является своим собственным синглтон-сообществом. Гирван-Ньюман начинает с полной сети и итеративно удаляет ребро с наибольшей центральностью по посредственности, постепенно выявляя структуру сообществ. Infomap начинает со случайного блуждания по сети и кодирует его, используя двухуровневую карту для минимизации длины кода.
Основной этап поиска разбиения, которое максимизирует модульность Q (Лувейн, Лейден) или минимизирует длину кода карты (Infomap). Лувейн жадно перемещает отдельные узлы между сообществами для улучшения Q, затем агрегирует сообщества в супер-узлы и повторяет — двухфазный процесс, который хорошо масштабируется, но может приводить к несвязным сообществам. Лейден уточняет Лувейн, гарантируя, что каждое сообщество внутренне связано, используя локальный шаг перемещения и уточнения перед агрегацией. Гирван-Ньюман итеративно удаляет ребра и записывает дендрограмму разбиений; выбирается разбиение, максимизирующее Q при любом разрезе дендрограммы. Количество сообществ возникает из самого алгоритма; его не нужно указывать заранее.
Качество конечного разбиения суммируется показателем модульности Q, который варьируется от −0.5 до 1. Значения выше ~0.3–0.5 обычно считаются показателем значимой структуры сообществ. Поскольку оптимизация модульности может застревать в локальных оптимумах, стандартной практикой является многократный запуск алгоритма и выбор наилучшего результата. Разбиение также проверяется визуально и перекрестно валидируется с любыми доступными атрибутами узлов или истинными метками, чтобы подтвердить его содержательную значимость.
Частые ошибки
- Запуск алгоритма один раз и рассмотрение единственного результата как истинного положения вещей — всегда запускайте несколько раз и сообщайте о лучшей модульности или используйте ансамблевые методы.
- Игнорирование предела разрешения: в больших разреженных сетях небольшие, но реальные сообщества могут быть поглощены более крупными без предупреждения.
- Применение алгоритмов на основе модульности к сетям с менее чем 20 узлами — структура сообществ не может быть надежно идентифицирована в таком масштабе.
- Смешивание высокого показателя модульности с подтвержденной реальной структурой сообществ; модульность является мерой качества разбиения, а не инференциальным тестом на статистическую значимость сообществ.
Часто задаваемые вопросы
Какой алгоритм выбрать — Лувейн, Лейден, Гирван-Ньюман или Infomap?
Лувейн — это быстрая, широко используемая базовая линия для больших сетей. Лейден — предпочтительный выбор, когда важна корректность, поскольку он гарантирует внутренне связанные сообщества и обычно достигает более высокой модульности. Гирван-Ньюман производит дендрограмму, полезную для иерархического исследования, но слишком медленный для больших сетей. Infomap хорошо подходит для направленных или потоковых сетей, где путь, проходимый случайным блуждающим объектом, имеет значение.
Нужно ли указывать количество сообществ заранее?
Нет. Лувейн, Лейден и Infomap автоматически определяют количество сообществ по структуре сети. Гирван-Ньюман производит полную дендрограмму, из которой можно получить любое количество сообществ; обычно выбирается разбиение, максимизирующее Q.
Как узнать, являются ли найденные сообщества осмысленными?
Показатель модульности Q предоставляет внутреннюю меру качества данных; значения выше примерно 0.3–0.5 указывают на нетривиальную структуру сообществ. Помимо этого, сообщества следует проверять на соответствие знаниям в предметной области, атрибутам узлов или внешним меткам. Высокий Q сам по себе не доказывает социологической или биологической значимости.
Что происходит, если результаты различаются при разных запусках?
Оптимизация модульности является эвристикой, и разные запуски могут давать немного разные разбиения, особенно в Лувейне. Запускайте алгоритм несколько раз (минимум 10–100 запусков на больших сетях) и сообщайте о разбиении с наивысшим Q. Лейден более стабилен, чем Лувейн, поскольку его шаг уточнения более тщательный, но повторные запуски остаются хорошей практикой.
Похожие методы
Источники
Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.
Открыть ссылку DOIСкопировано.Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.
Открыть ссылку на публикациюСкопировано.