Scholarlink

<p>In community detection tasks, accurately measuring the distance between nodes is fundamental for correctly grouping the nodes according to their similarity. This work proposes a community detection method exploiting the <i>effective resistance</i>, a measure derived from the field of electrical circuits that has been shown to be a good distance metric for uncovering communities. In the pre-processing phase, the method weights the input graph <i>G</i> with the effective resistance between each couple of nodes. Then, to turn this distance into a similarity value reflecting the closeness between each couple of nodes, different kernel functions for the effective resistance are tested. Finally, since many of the networks we deal with are not sparse, <i>G</i> is reduced to a smaller graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G'\)</EquationSource> </InlineEquation> by cutting a percentage of less important edges through a <i>weight thresholding</i> sparsification procedure. The amount of edge cuts is chosen evaluating the spectral similarity between <i>G</i> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(G'\)</EquationSource> </InlineEquation>. In such a way, we are able to work with fewer edges gaining in computational time and storage resources. At the end of the pre-processing phase, we run on the sparsified graph <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(G'\)</EquationSource> </InlineEquation> a community detection method based on Genetic Algorithms maximizing the weighted modularity as objective function. Experimenting on both real-world and synthetic networks, we demonstrate the effectiveness of such approach when compared to other benchmarks.</p>

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

Effective resistance and kernel-based graph sparsification for community detection in complex networks

  • 期刊论文

  • 发表日期：

    2026年2月18日

查看全文
  • Annalisa Socievole,
  • Clara Pizzuti

摘要

In community detection tasks, accurately measuring the distance between nodes is fundamental for correctly grouping the nodes according to their similarity. This work proposes a community detection method exploiting the effective resistance, a measure derived from the field of electrical circuits that has been shown to be a good distance metric for uncovering communities. In the pre-processing phase, the method weights the input graph G with the effective resistance between each couple of nodes. Then, to turn this distance into a similarity value reflecting the closeness between each couple of nodes, different kernel functions for the effective resistance are tested. Finally, since many of the networks we deal with are not sparse, G is reduced to a smaller graph \(G'\) by cutting a percentage of less important edges through a weight thresholding sparsification procedure. The amount of edge cuts is chosen evaluating the spectral similarity between G and \(G'\) . In such a way, we are able to work with fewer edges gaining in computational time and storage resources. At the end of the pre-processing phase, we run on the sparsified graph \(G'\) a community detection method based on Genetic Algorithms maximizing the weighted modularity as objective function. Experimenting on both real-world and synthetic networks, we demonstrate the effectiveness of such approach when compared to other benchmarks.