Conference proceeding
Finding Hierarchical Communities in Complex Networks Using Influence-Guided Label Propagation
2015 IEEE INTERNATIONAL CONFERENCE ON DATA MINING WORKSHOP (ICDMW), pp.547-556
11/01/2015
DOI: 10.1109/ICDMW.2015.58
Abstract
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.
Details
- Title: Subtitle
- Finding Hierarchical Communities in Complex Networks Using Influence-Guided Label Propagation
- Creators
- Wenjun Wang - University of IowaW. Nick Street - University of Iowa
- Contributors
- P Cui (Editor)J Dy (Editor)C Aggarwal (Editor)Z H Zhou (Editor)A Tuzhilin (Editor)H Xiong (Editor)Xindong Wu (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- 2015 IEEE INTERNATIONAL CONFERENCE ON DATA MINING WORKSHOP (ICDMW), pp.547-556
- Publisher
- IEEE
- DOI
- 10.1109/ICDMW.2015.58
- eISSN
- 2375-9259
- Number of pages
- 10
- Language
- English
- Date published
- 11/01/2015
- Academic Unit
- Nursing; Business Analytics; Computer Science; Bus Admin College
- Record Identifier
- 9984380406602771
Metrics
9 Record Views