?
Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection
arxiv.org
,
2025.
Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, что последнее вычисление выполняется путем псевдоинвертирования матрицы Лапласа графа. При этом наш подход является альтернативой подходу, основанному на геометрическом потоке Олливье-Риччи для обнаружения сообществ на графах, значительно превосходя его по времени вычислений. В предлагаемом нами методе итерации потока Фостера-Риччи, которые выделяют области сети с различной кривизной, сопровождаются эвристикой разделения с помощью модели гауссовой смеси (GMM). Это позволяет классифицировать ребра на «сильные» (внутрисообщественные) и «слабые» (межсообщественные) группы, после чего происходит систематическое отсечение первых для изоляции сообществ. Мы провели сравнительный анализ нашего алгоритма на синтетических сетях, сгенерированных на основе стохастической блочной модели (SBM), оценивая производительность с помощью скорректированного индекса ARI. Наши результаты показывают, что предложенная структура надежно восстанавливает структуру сообществ, созданных на основе SBM, подтверждая, что поток Риччи-Фостера с кластеризацией GMM является принципиально эффективным и вычислительно действенным новым инструментом для анализа сетей, протестированным в сравнении с альтернативным потоком Риччи-Оливье в сочетании со спектральной кластеризацией.
Язык:
русский