On community structure in complex networks: challenges and opportunities
arXiv:1908.04901 · doi:10.1007/s41109-019-0238-9
Abstract
Community structure is one of the most relevant features encountered in numerous real-world applications of networked systems. Despite the tremendous effort of scientists working on this subject over the past few decades to characterize, model, and analyze communities, more investigations are needed to better understand the impact of community structure and its dynamics on networked systems. Here, we first focus on generative models of communities in complex networks and their role in developing strong foundation for community detection algorithms. We discuss modularity and the use of modularity maximization as the basis for community detection. Then, we overview the Stochastic Block Model, its different variants, and inference of community structures from such models. Next, we focus on time evolving networks, where existing nodes and links can disappear and/or new nodes and links may be introduced. The extraction of communities under such circumstances poses an interesting and non-trivial problem that has gained considerable interest over the last decade. We briefly discuss considerable advances made in this field recently. Finally, we focus on immunization strategies essential for targeting the influential spreaders of epidemics in modular networks. Their main goal is to select and immunize a small proportion of individuals from the whole network to control the diffusion process. Various strategies have emerged over the years suggesting different ways to immunize nodes in networks with overlapping and non-overlapping community structure. We first discuss stochastic strategies that require little or no information about the network topology at the expense of their performance. Then, we introduce deterministic strategies that have proven to be very efficient in controlling the epidemic outbreaks, but require complete knowledge of the network.
41 pages, 2 figures
References in corpus (59)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Modularity and community structure in networks
- Finding community structure in very large networks
- Finding community structure in networks using the eigenvectors of matrices
- 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
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Detecting the overlapping and hierarchical community structure of complex networks
- Quantifying social group evolution
- Vital nodes identification in complex networks
- Statistical physics of vaccination
- Consensus clustering in complex networks
- Mapping change in large networks
- Saving Human Lives: What Complexity Science and Information Systems can Contribute
- Limits of modularity maximization in community detection
- The ground truth about metadata and community detection in networks
- Community Discovery in Dynamic Networks: a Survey
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Community Detection via Maximization of Modularity and Its Variants
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Maximizing Modularity is hard
- GED: the method for group evolution discovery in social networks
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- Evaluating Overfit and Underfit in Models of Network Community Structure
- Network reconstruction and community detection from dynamics
- Modeling sequences and temporal networks with dynamic community structures
- Significant Scales in Community Structure
- Estimating the number of communities in a network
- Entropy of stochastic blockmodel ensembles
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Global efficiency of local immunization on complex networks
- Centrality Measures for Networks with Community Structure
- Immunization of networks with community structure
- Centrality in Modular Networks
- Efficient method for estimating the number of communities in a network
- Benchmark model to assess community structure in evolving networks
- Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
- Weighted percolation on directed networks
- Towards realistic artificial benchmark for community detection algorithms evaluation
- Detecting global bridges in networks
- Immunization Strategies Based on the Overlapping Nodes in Networks with Community Structure
- Predicting Community Evolution in Social Networks
- Online detection of temporal communities in evolving networks by estrangement confinement
- Null models for network data
- Different Approaches to Community Evolution Prediction in Blogosphere
- Adaptive Modularity Maximization via Edge Weighting Scheme
- An Empirical Study of the Relation Between Community Structure and Transitivity
- Community-based Immunization Strategies for Epidemic Control
- Tracking and Predicting Evolution of Social Communities
- Extension of Modularity Density for Overlapping Community Structure
- Asymptotic resolution bounds of generalized modularity and multi-scale community detection
- Regularized Stochastic Block Model for robust community detection in complex networks
- Community Detection with Metadata in a Network of Biographies of Western Art Painters
- Community detection for interaction networks
Cited by in corpus (19)
- A Review of Stochastic Block Models and Extensions for Graph Clustering
- Measuring Node Contribution to Community Structure with Modularity Vitality
- Comparative evaluation of community-aware centrality measures
- A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
- Interplay Between Hierarchy and Centrality in Complex Networks
- The inherent community structure of hyperbolic networks
- Lexical Sorting Centrality to Distinguish Spreading Abilities of Nodes in Complex Networks under the Susceptible-Infectious-Recovered (SIR) Model
- Map Equation Centrality: Community-aware Centrality based on the Map Equation
- Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
- Detection of Rumors and Their Sources in Social Networks: A Comprehensive Survey
- Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
- Maximally modular structure of growing hyperbolic networks
- Investigating Centrality Measures in Social Networks with Community Structure
- Greedy routing optimisation in hyperbolic networks
- Vulnerable Connectivity Caused by Local Communities in Spatial Networks
- Community detection in hypergraphs through hyperedge percolation
- On the Impact of Communities on Semi-supervised Classification Using Graph Neural Networks
- Modelling and Predicting Online Vaccination Views using Bow-tie Decomposition
- Overcoming Tight Constraints in Soft Happy Colouring