Size reduction of complex networks preserving modularity

Abstract

The ubiquity of modular structure in real-world complex networks is being the focus of attention in many trials to understand the interplay between network topology and functionality. The best approaches to the identification of modular structure are based on the optimization of a quality function known as modularity. However this optimization is a hard task provided that the computational complexity of the problem is in the NP-hard class. Here we propose an exact method for reducing the size of weighted (directed and undirected) complex networks while maintaining invariant its modularity. This size reduction allows the heuristic algorithms that optimize modularity for a better exploration of the modularity landscape. We compare the modularity obtained in several real complex-networks by using the Extremal Optimization algorithm, before and after the size reduction, showing the improvement obtained. We speculate that the proposed analytical size reduction could be extended to an exact coarse graining of the network in the scope of real-space renormalization.

14 pages, 2 figures

References in corpus (15)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• Analysis of weighted networks
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Community detection in complex networks using Extremal Optimization
• Self-similar community structure in organisations
• Community Structure in Jazz
• Classes of complex networks defined by role-to-role connectivity profiles
• Maximizing Modularity is hard
• Thermodynamics of Community Structure

Cited by in corpus (74)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Multilayer Networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• A smart local moving algorithm for large-scale modularity-based community detection
• Community structure in directed networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The map equation
• Clustering and Community Detection in Directed Networks: A Survey
• Analysis of the structure of complex networks at different resolution levels
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Robustness of community structure in networks
• Extending the definition of modularity to directed graphs with overlapping communities
• 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
• Graph Metrics for Temporal Networks
• Analysis of community structure in networks of correlated data
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Identifying the Community Structure of the International-Trade Multi Network
• Local resolution-limit-free Potts model for community detection
• Defecting or not defecting: how to "read" human behavior during cooperative games by EEG measurements
• LinkRank: Finding communities in directed networks
• Coauthorship and Citation Networks for Statisticians
• Improved community structure detection using a modified fine tuning strategy
• Motif-based communities in complex networks
• Z-score-based modularity for community detection in networks
• Network Community Detection: A Review and Visual Survey
• Finding multiple core-periphery pairs in networks
• Core-periphery structure requires something else in the network
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• Magnetic eigenmaps for community detection in directed networks
• Using Triangles to Improve Community Detection in Directed Networks
• Network Quotients: Structural Skeletons of Complex Systems
• Detecting communities of triangles in complex networks using spectral optimization
• Communities unfolding in multislice networks
• Communities and beyond: mesoscopic analysis of a large social network with complementary methods
• Universality of the stochastic block model
• Community detection in directed acyclic graphs
• Flow stability for dynamic community detection
• Measuring Cultural Dynamics Through the Eurovision Song Contest
• Social and place-focused communities in location-based online social networks
• Combinatorial approach to Modularity
• Modularity and the spread of perturbations in complex dynamical systems
• Mesoscopic analysis of networks: applications to exploratory analysis and data clustering
• Alternative approach to community detection in networks
• Structure and stability of online chat networks built on emotion-carrying links
• Detecting Communities in Tripartite Hypergraphs
• Finding overlapping communities in networks using evolutionary method
• Community detection for networks with unipartite and bipartite structure
• Multiple bipolar fuzzy measures: an application to community detection problems for networks with additional information
• Detecting groups of similar components in complex networks
• Cycle flow based module detection in directed recurrence networks
• Modularity in Multilayer Networks using Redundancy-based Resolution and Projection-based Inter-Layer Coupling
• Scalable Spectral Algorithms for Community Detection in Directed Networks
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Investigating structural and functional aspects of the brain's criticality in stroke
• Search for overlapped communities by parallel genetic algorithms
• Finding Community Structure with Performance Guarantees in Complex Networks
• Community detection for directed networks revisited using bimodularity
• Modeling international crisis synchronization in the World Trade Web
• Evaluating the effect of topic consideration in identifying communities of rating-based social networks
• Evolving community structure in the international pesticide trade networks
• Habitat variability does not generally promote metabolic network modularity in flies and mammals
• Community detection analysis in wind speed-monitoring systems using mutual information-based complex network
• Optimal timescale for community detection in growing networks
• The Atlas for the Aspiring Network Scientist
• Metrics for Community Analysis: A Survey
• A subset selection based approach to finding important structure of complex networks
• Mining Essential Relationships under Multiplex Networks
• On the Relationship Between Modularity and Stability in Software Packages
• Functional and spatial rewiring jointly generate convergent-divergent units in self-organizing networks
• Representation of functions on big data associated with directed graphs