Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics

Abstract

Background: Network communities help the functional organization and evolution of complex networks. However, the development of a method, which is both fast and accurate, provides modular overlaps and partitions of a heterogeneous network, has proven to be rather difficult. Methodology/Principal Findings: Here we introduce the novel concept of ModuLand, an integrative method family determining overlapping network modules as hills of an influence function-based, centrality-type community landscape, and including several widely used modularization methods as special cases. As various adaptations of the method family, we developed several algorithms, which provide an efficient analysis of weighted and directed networks, and (1) determine pervasively overlapping modules with high resolution; (2) uncover a detailed hierarchical network structure allowing an efficient, zoom-in analysis of large networks; (3) allow the determination of key network nodes and (4) help to predict network dynamics. Conclusions/Significance: The concept opens a wide range of possibilities to develop new approaches and applications including network routing, classification, comparison and prediction.

25 pages with 6 figures and a Glossary + Supporting Information containing pseudo-codes of all algorithms used, 14 Figures, 5 Tables (with 18 module definitions, 129 different modularization methods, 13 module comparision methods) and 396 references. All algorithms can be downloaded from this web-site: http://www.linkgroup.hu/modules.php

References in corpus (117)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• 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 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
• Detecting the overlapping and hierarchical community structure of complex networks
• Quantifying social group evolution
• Community structure in directed networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The performance of modularity maximization in practical contexts
• CFinder: Locating cliques and overlapping modules in biological networks
• An information-theoretic framework for resolving community structure in complex networks
• Modularity and community detection in bipartite networks
• New Model of Internet Topology Using k-shell Decomposition
• Communicability in complex networks
• Detect overlapping and hierarchical community structure in networks
• Line Graphs, Link Partitions and Overlapping Communities
• Mixture models and exploratory analysis in networks
• Extracting the hierarchical organization of complex systems
• Community detection in networks with positive and negative links
• Classes of complex networks defined by role-to-role connectivity profiles
• Detecting network communities by propagating labels under constraints
• Robustness of community structure in networks
• Modularity-Maximizing Network Communities via Mathematical Programming
• Size reduction of complex networks preserving modularity
• A Bayesian Approach to Network Modularity
• Towards real-time community detection in large networks
• Community Detection in Complex Networks Using Genetic Algorithms
• Analysis of community structure in networks of correlated data
• Characterizing the community structure of complex networks
• Weighted network modules
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• A sequential algorithm for fast clique percolation
• Evaluating Local Community Methods in Networks
• Identifying network communities with a high resolution
• Limited resolution in complex network community detection with Potts model approach
• Community extraction for social networks
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Identifying "communities" within energy landscapes
• A system of mobile agents to model social networks
• The Large Scale Curvature of Networks
• Revisiting Date and Party Hubs: Novel Approaches to Role Assignment in Protein Interaction Networks
• Line Graphs of Weighted Networks for Overlapping Communities
• Communicability Betweenness in Complex Networks
• Creative elements: network-based predictions of active centres in proteins, cellular and social networks
• Motif-based communities in complex networks
• Bi-clique Communities
• Some protein interaction data do not exhibit power law statistics
• Statistical significance of communities in networks
• Role models for complex networks
• Lobby index in networks
• When are networks truly modular?
• Adaptive Affinity Propagation Clustering
• Empirical Comparison of Algorithms for Network Community Detection
• Modularity measure of networks with overlapping communities
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Stress-induced rearrangements of cellular networks: consequences for protection and drug design
• Chaperones as integrators of cellular networks: Changes of cellular integrity in stress and diseases
• Communicability Graph and Community Structures in Complex Networks
• (Un)detectable cluster structure in sparse networks
• Self-assembly, modularity and physical complexity
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• Impact of community structure on information transfer
• Uncovering the community structure associated with the diffusion dynamics of networks
• Covariance, correlation matrix and the multi-scale community structure of networks
• Multi-scale Modularity in Complex Networks
• Unveiling community structures in weighted networks
• Detecting communities of triangles in complex networks using spectral optimization
• Inversion method for content-based networks
• Community Detection in Complex Networks by Dynamical Simplex Evolution
• Communities and beyond: mesoscopic analysis of a large social network with complementary methods
• Bridge Bounding: A Local Approach for Efficient Community Discovery in Complex Networks
• Optimal map of the modular structure of complex networks
• Unsupervised and semi-supervised clustering by message passing: Soft-constraint affinity propagation
• Impact of hierarchical modular structure on ranking of individual nodes in directed networks
• Thermodynamics of Community Structure
• Clustering with Spectral Norm and the k-means Algorithm
• Structure of Heterogeneous Networks
• Combinatorial approach to Modularity
• Population stratification using a statistical model on hypergraphs
• Belief propagation for graph partitioning
• Effect of size heterogeneity on community identification in complex networks
• Spectral methods and cluster structure in correlation-based networks
• Graph animals, subgraph sampling and motif search in large networks
• Natural clustering: the modularity approach
• Centrality Metric for Dynamic Networks
• Centrality properties of directed module members in social networks
• Spectrum, Intensity and Coherence in Weighted Networks of a Financial Market
• Partition of Networks into Basins of Attraction
• Quality functions in community detection
• A dual assortative measure of community structure
• Consistent Community Identification in Complex Networks
• What Is There Between Any Two Nodes in a Complex Network?
• Search for overlapped communities by parallel genetic algorithms
• Hub-Based Community Finding
• The accuracy of roughness exponent measurement methods
• Identification of community structure in networks with convex optimization
• Bayesian approach to clustering real value, categorical and network data: solution via variational methods
• Communities in networks - a continuous approach
• Parameterized Centrality for Network Analysis
• An exact algorithm for graph partitioning
• Detecting Neuronal Communities from Beginning of Activation Patterns
• A New Clustering Algorithm Based Upon Flocking On Complex Network
• Opinion Dynamics with Decaying Confidence: Application to Community Detection in Graphs
• Symmetry consideration in identifying network structures
• Communities in Neuronal Complex Networks Revealed by Activation Patterns
• A Novel Clustering Algorithm Based on a Modified Model of Random Walk

Cited by in corpus (36)

• Finding statistically significant communities in networks
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Detecting modules in quantitative bipartite networks: the QuaBiMo algorithm
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Structure and dynamics of core-periphery networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Analyzing complex functional brain networks: fusing statistics and network science to understand the brain
• ModuLand plug-in for Cytoscape: determination of hierarchical layers of overlapping network modules and community centrality
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Map equation for link community
• Cancer stem cells display extremely large evolvability: alternating plastic and rigid networks as a potential mechanism
• Finding and testing network communities by lumped Markov chains
• Heat shock partially dissociates the overlapping modules of the yeast protein-protein interaction network: a systems level model of adaptation
• Detecting Important Nodes to Community Structure Using the Spectrum of the Graph
• Community structure and the evolution of interdisciplinarity in Slovenia's scientific collaboration network
• Followers Are Not Enough: A Question-Oriented Approach to Community Detection in Online Social Networks
• Rigidity and flexibility of biological networks
• Identifying communities by influence dynamics in social networks
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Leveraging disjoint communities for detecting overlapping community structure
• Perturbation centrality and Turbine: a novel centrality measure obtained using a versatile network dynamics tool
• Stress induces remodelling of yeast interaction and co-expression networks
• Nodes having a major influence to break cooperation define a novel centrality measure: game centrality
• The wisdom of networks: A general adaptation and learning mechanism of complex systems: The network core triggers fast responses to known stimuli; innovations require the slow network periphery and are encoded by core-remodeling
• Modular structure in C. elegans neural network and its response to external localized stimuli
• Translocatome: a novel resource for the analysis of protein translocation between cellular organelles
• Discovering Network Structure Beyond Communities
• A unified data representation theory for network visualization, ordering and coarse-graining
• System level mechanisms of adaptation, learning, memory formation and evolvability: the role of chaperone and other networks
• Criterions for locally dense subgraphs
• Potential application of network descriptions for understanding conformational changes and protonation states of ABC transporters
• Generating Post-hoc Explanations for Skip-gram-based Node Embeddings by Identifying Important Nodes with Bridgeness
• Rigidity and flexibility in protein-protein interaction networks: a case study on neuromuscular disorders
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Integrating epigenomic data and 3D genomic structure with a new measure of chromatin assortativity