Community detection by resistance distance: automation and benchmark testing

Abstract

Heterogeneity characterises real-world networks, where nodes show a broad range of different topological features. However, nodes also tend to organise into communities -- subsets of nodes that are sparsely inter-connected but are densely intra-connected (more than the network's average connectivity). This means that nodes belonging to the same community are close to each other by some distance measure, such as the resistance distance, which is the effective distance between any pair of nodes considering all possible paths. In this work, we present automation (i.e., unsupervised) and missing accuracy tests for a recently proposed semi-supervised community detection algorithm based on the resistance distance. The accuracy testing involves quantifying our algorithm's performance in terms of recovering known synthetic communities from benchmark networks, where we present results for Girvan-Newman and Lancichinetti-Fortunato-Radicchi networks. Our findings show that our algorithm falls into the class of accurate performers.

arXiv comment9 pages (without references), 4 figures. To be published in the 10th International Conference on Complex Networks and their Applications proceedings

References in corpus (23)

• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• The performance of modularity maximization in practical contexts
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Modularity clustering is force-directed layout
• Scaling theory of transport in complex networks
• Anomalous Transport in Complex Networks
• Exploring the solution landscape enables more reliable network community detection
• Unveiling community structures in weighted networks
• Resiliently evolving supply-demand networks
• Structure and function in flow networks
• Finding the Resistance Distance and Eigenvector Centrality from the Network's Eigenvalues