Scholarlink

Abstract <p>Over the past decades a great deal of experience has been accumulated in applying various approaches to solving the problem of finding communities in graphs. The Girvan–Newman algorithm, based on calculating the betweenness centrality of edges, is widely known and demonstrates good results on relatively small graphs. In this paper, we propose a new algorithm based on calculating the attendance centrality. The algorithm combines the ideas of irreversible random walks on a graph, constructing minimum spanning trees, and ranking vertices by centrality. The algorithm has some similarities with the Girvan–Newman algorithm, but some of its features have significantly increased the efficiency of the algorithm. The paper describes the proposed algorithm, analyzes the comparability of the betweenness and attendance values, and considers the results of the algorithm on SBM graphs.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Community Detection in Networks by Geodetic Sets

  • 期刊论文

  • 发表日期：

    2025年6月1日

查看全文
  • A. K. Ilyushchenko,
  • O. V. Ivanov

摘要

Abstract

Over the past decades a great deal of experience has been accumulated in applying various approaches to solving the problem of finding communities in graphs. The Girvan–Newman algorithm, based on calculating the betweenness centrality of edges, is widely known and demonstrates good results on relatively small graphs. In this paper, we propose a new algorithm based on calculating the attendance centrality. The algorithm combines the ideas of irreversible random walks on a graph, constructing minimum spanning trees, and ranking vertices by centrality. The algorithm has some similarities with the Girvan–Newman algorithm, but some of its features have significantly increased the efficiency of the algorithm. The paper describes the proposed algorithm, analyzes the comparability of the betweenness and attendance values, and considers the results of the algorithm on SBM graphs.