A Classification for Community Discovery Methods in Complex Networks

Abstract

In the last few years many real-world networks have been found to show a so-called community structure organization. Much effort has been devoted in the literature to develop methods and algorithms that can efficiently highlight this hidden structure of the network, traditionally by partitioning the graph. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition it then extracts the communities that are able to reflect only some of the features of real communities. The aim of this survey is to provide a manual for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery based on their own definition of community. Given a desired definition of community and the features of a problem (size of network, direction of edges, multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on.

Published in the Statistical Analysis and Data Mining journal, Special Issue: Networks. Volume 4, Issue 5, pages 512-546, October 2011

References in corpus (47)

• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Functional cartography of complex metabolic networks
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• The Dynamics of Viral Marketing
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in complex networks using Extremal Optimization
• Community structure in directed networks
• The performance of modularity maximization in practical contexts
• Finding overlapping communities in networks by label propagation
• Modularity and community detection in bipartite networks
• Detect overlapping and hierarchical community structure in networks
• Line Graphs, Link Partitions and Overlapping Communities
• Mixture models and exploratory analysis in networks
• Community detection in networks with positive and negative links
• Finding Communities in Linear Time: A Physics Approach
• Phase transition in the detection of modules in sparse networks
• An efficient and principled method for detecting communities in networks
• Extending the definition of modularity to directed graphs with overlapping communities
• Optimization with Extremal Dynamics
• Modularity-Maximizing Network Communities via Mathematical Programming
• Size reduction of complex networks preserving modularity
• A Bayesian Approach to Network Modularity
• A Method to Find Community Structures Based on Information Centrality
• A Local Method for Detecting Communities
• Analysis of community structure in networks of correlated data
• Community Detection as an Inference Problem
• An Information-Theoretic Approach to Network Modularity
• Unveiling community structures in weighted networks

Cited by in corpus (26)

• Community detection in networks: A user guide
• Clustering and Community Detection in Directed Networks: A Survey
• Community Discovery in Dynamic Networks: a Survey
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Community detection in node-attributed social networks: a survey
• The many facets of community detection in complex networks
• Estimating the number of communities in a network
• A Large-Scale Community Structure Analysis In Facebook
• Centrality in Modular Networks
• A planetary nervous system for social mining and collective awareness
• Community structure: A comparative evaluation of community detection methods
• Deep Community Detection
• Forensic Analysis of Phone Call Networks
• Different approaches to community detection
• Community evolution in retweet networks
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• Efficiently Clustering Very Large Attributed Graphs
• Center-Periphery Structure in Communities: Extracellular Vesicles
• Walking Through Twitter: Sampling a Language-Based Follow Network of Influential Twitter Accounts
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Community structure revealed by phase locking
• Modularity in Multilayer Networks using Redundancy-based Resolution and Projection-based Inter-Layer Coupling
• Network Community Detection on Metric Space
• AOC; Assembling Overlapping Communities
• Topological aspects of the multi-language phases of the Naming Game on community-based networks
• Extraction of Multi-layered Social Networks from Activity Data