Scholarlink

<p>Network community detection has gained momentum in the last decade due to its wide range of applications. However, many fundamental questions still remain to be addressed. First, there are only a limited number of algorithms designed for weighted networks. Scalability is another factor that limits the applicability of many algorithms to networks with only a few thousand nodes. Accuracy is also a major concern. Moreover, many algorithms detect only disjoint communities, and very few are capable of identifying <i>connected communities</i>—a crucial feature of any meaningful community structure. To address all of these issues, in this article, we propose a graph traversal-based overlapping community detection algorithm for weighted networks. The algorithm, called NPCA-BFS, employs the concept of <i>neighbourhood proximity</i> within the <i>breadth-first search</i> framework to discover community structure. Its time complexity is <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal {O}(nk^3)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <msup> <mi>k</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>n</i> is the number of nodes and <i>k</i> is the maximum degree of the input network. We evaluate the performance of the proposed method against twelve widely used community detection algorithms on both artificial and large-scale real-world networks. The results show that NPCA-BFS performs excellently in terms of overall quality and stability, outperforming most of the baseline algorithms. In terms of speed, NPCA-BFS falls among the top four out of the 13 algorithms studied in this paper.</p>

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

Neighbourhood proximity-based clustering algorithm using breadth-first search technique for weighted graphs

  • 期刊论文

  • 发表日期：

    2026年3月30日

查看全文
  • Anjali Kumari,
  • Abhinav Kumar,
  • Pawan Kumar

摘要

Network community detection has gained momentum in the last decade due to its wide range of applications. However, many fundamental questions still remain to be addressed. First, there are only a limited number of algorithms designed for weighted networks. Scalability is another factor that limits the applicability of many algorithms to networks with only a few thousand nodes. Accuracy is also a major concern. Moreover, many algorithms detect only disjoint communities, and very few are capable of identifying connected communities—a crucial feature of any meaningful community structure. To address all of these issues, in this article, we propose a graph traversal-based overlapping community detection algorithm for weighted networks. The algorithm, called NPCA-BFS, employs the concept of neighbourhood proximity within the breadth-first search framework to discover community structure. Its time complexity is \(\mathcal {O}(nk^3)\) O ( n k 3 ) , where n is the number of nodes and k is the maximum degree of the input network. We evaluate the performance of the proposed method against twelve widely used community detection algorithms on both artificial and large-scale real-world networks. The results show that NPCA-BFS performs excellently in terms of overall quality and stability, outperforming most of the baseline algorithms. In terms of speed, NPCA-BFS falls among the top four out of the 13 algorithms studied in this paper.