In graph clustering tasks, distance measures are fundamental for assessing the closeness between nodes and group them accordingly. In this paper, we exploit the effective resistance as distance measure to organize nodes in communities. In the context of electric circuit analysis, the effective resistance is used to define the resistance between two points of an electric network. In graph theory, this is also known as the resistance distance between two vertices of a connected graph whose square root is an Euclidean distance. In this work, we first weight the input graph using this distance measure. Then, since most of the networks we deal with are characterized by very high edge densities, we investigate how to sparsify the network through a weight tresholding procedure. This pre-processing phase has the goal of removing a proper percentage of edges without significantly altering the underlying community structure. This is done analyzing the minimum absolute spectral similarity index between the original network graph G and its sparsifier \(G'\) . We finally run on the sparse graph an genetic algorithm of community detection aiming at finding highly modular structures. The results of the experiments carried on different types of graphs demonstrate how the proposed method is able to outperform other benchmark contestant methods.

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

Effective Resistance Based Community Detection in Complex Networks

  • Annalisa Socievole,
  • Clara Pizzuti

摘要

In graph clustering tasks, distance measures are fundamental for assessing the closeness between nodes and group them accordingly. In this paper, we exploit the effective resistance as distance measure to organize nodes in communities. In the context of electric circuit analysis, the effective resistance is used to define the resistance between two points of an electric network. In graph theory, this is also known as the resistance distance between two vertices of a connected graph whose square root is an Euclidean distance. In this work, we first weight the input graph using this distance measure. Then, since most of the networks we deal with are characterized by very high edge densities, we investigate how to sparsify the network through a weight tresholding procedure. This pre-processing phase has the goal of removing a proper percentage of edges without significantly altering the underlying community structure. This is done analyzing the minimum absolute spectral similarity index between the original network graph G and its sparsifier \(G'\) . We finally run on the sparse graph an genetic algorithm of community detection aiming at finding highly modular structures. The results of the experiments carried on different types of graphs demonstrate how the proposed method is able to outperform other benchmark contestant methods.