A Method to Find Community Structures Based on Information Centrality

Abstract

Community structures are an important feature of many social, biological and technological networks. Here we study a variation on the method for detecting such communities proposed by Girvan and Newman and based on the idea of using centrality measures to define the community boundaries (M. Girvan and M. E. J. Newman, Community structure in social and biological networks Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002)). We develop an algorithm of hierarchical clustering that consists in finding and removing iteratively the edge with the highest information centrality. We test the algorithm on computer generated and real-world networks whose community structure is already known or has been studied by means of other methods. We show that our algorithm, although it runs to completion in a time O(n^4), is very effective especially when the communities are very mixed and hardly detectable by the other methods.

13 pages, 13 figures. Final version accepted for publication in Physical Review E

References in corpus (15)

• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Fast algorithm for detecting community structure in networks
• Efficient Behavior of Small-World Networks
• Cooperative Game Theory Approaches for Network Partitioning
• Evolution of networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Economic Small-World Behavior in Weighted Networks
• Finding Communities in Linear Time: A Physics Approach
• Vulnerability and Protection of Critical Infrastructures
• Subnetwork hierarchies of biochemical pathways
• Distance, dissimilarity index, and network community structure
• Network Landscape from a Brownian Particle's Perspective
• Finding Communities of Related Genes

Cited by in corpus (32)

• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Comparing community structure identification
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A Classification for Community Discovery Methods in Complex Networks
• A Novel Measure of Edge Centrality in Social Networks
• Mixing local and global information for community detection in large networks
• Improved community structure detection using a modified fine tuning strategy
• Availability-aware Service Placement Policy in Fog Computing Based on Graph Partitions
• Computing communities in large networks using random walks (long version)
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Enhancing community detection using a network weighting strategy
• Computing communities in large networks using random walks
• A functional clustering algorithm for the analysis of dynamic network data
• Coexistence of opposite opinions in a network with communities
• Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
• Random field Ising model and community structure in complex networks
• Detecting communities of triangles in complex networks using spectral optimization
• Limitation of multi-resolution methods in community detection
• Process Flow Diagram of an Ammonia Plant as a Complex Network
• Topological Centrality and Its Applications
• Effect of size heterogeneity on community identification in complex networks
• Eigenvector localization as a tool to study small communities in online social networks
• Soft triaxial rotor in the vicinity of $\gamma =\pi /6$ and its extensions
• Nodal domain partition and the number of communities in networks
• Network Community Detection on Metric Space
• Communities recognition in the Chesapeake Bay ecosystem by dynamical clustering algorithms based on different oscillators systems
• Structural importance and evolution: an application to financial transaction networks
• The Atlas for the Aspiring Network Scientist
• An Efficient Quadratic Penalty Method for a Class of Graph Clustering Problems
• Structure and Dynamic of Global Population Migration Network
• Ground state energy of $q$-state Potts model: the minimum modularity