Effective Resistance-Based Graph Sparsification and Community Detection

Community detection is a key task in network analysis, providing insight into the structural organization of complex systems.

Effective resistance, a graph-theoretic metric derived from electrical network theory, has emerged as a powerful tool for evaluating connectivity and influence within networks.

This paper proposes an effective resistance-based community detection algorithm that calculates the similarity between nodes using effective resistance values and produces a weighted graph.

The sparse graph used in the algorithm is generated after computing the minimum spanning tree (MST) of the weighted graph and adopting a threshold sparsification strategy on non-MST edges.

A maximum modularity approach is adopted using the Clauset-Newman-Moore algorithm on the resultant sparse graph.

This algorithm is evaluated for both synthetic and real-world networks, demonstrating its effectiveness compared to popular existing methods.

The result shows that the effective resistance-based approach accurately captures the structures of the community while maintaining computational efficiency.