Finding Hierarchical Communities in Complex Networks Using Influence-Guided Label Propagation

摘要

Communities play fundamental organizational and functional roles in various complex network systems. Community detection is an important challenge in network analysis. We approach community detection based on a Shared-Influence-Neighbor (SIN) similarity metric that measures the closeness of a pair of nodes in terms of their mutual influence and the common set of nodes they both influence. In this paper, we present two novel influence-guided label propagation (IGLP) algorithms. One is called IGLP-Weighted-Ensemble (IGLP-WE), in which each node adopts the label of the majority of its neighbors, weighted by the SIN similarity. This simple weighting scheme effectively resolves the significant stability issue in conventional label propagation algorithms. The other is called IGLP-Direct-Passing (IGLP-DP), in which the label is propagated directly from one node to its most similar neighbor step by step. This new label propagation method produces a deterministic partition and requires no convergent iterations. For both IGLP-WE and IGLP-DP, we regard the resultant partitioning as the initial configuration of the community structure. We then perform agglomerative hierarchical clustering to uncover the hierarchical communities at different scales using a new cluster-proximity measure. Extensive tests on a set of real-life networks and synthetic benchmarks demonstrate superior performance of our algorithms in terms of both quality and efficiency in undirected/directed and unweighted/weighted networks. Both IGLP-WE and IGLP-DP manifest promising scalability for large-scale networks.