Community detection in complex networks using Extremal Optimization

Abstract

We propose a novel method to find the community structure in complex networks based on an extremal optimization of the value of modularity. The method outperforms the optimal modularity found by the existing algorithms in the literature. We present the results of the algorithm for computer simulated and real networks and compare them with other approaches. The efficiency and accuracy of the method make it feasible to be used for the accurate identification of community structure in large complex networks.

4 pages, 4 figures

References in corpus (6)

• Finding community structure in very large networks
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• Community Structure in Jazz
• Subnetwork hierarchies of biochemical pathways
• Identifying "communities" within energy landscapes

Cited by in corpus (232)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Community detection in graphs
• From Louvain to Leiden: guaranteeing well-connected communities
• 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
• Characterization of complex networks: A survey of measurements
• A smart local moving algorithm for large-scale modularity-based community detection
• The Kuramoto model in complex networks
• The performance of modularity maximization in practical contexts
• Modularity and community detection in bipartite networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Detect overlapping and hierarchical community structure in networks
• Clustering and Community Detection in Directed Networks: A Survey
• Community detection in networks with positive and negative links
• Analysis of the structure of complex networks at different resolution levels
• Generalized Louvain Method for Community Detection in Large Networks
• Ranking spreaders by decomposing complex networks
• Spectral methods for network community detection and graph partitioning
• Module identification in bipartite and directed networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• 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
• Modularity-Maximizing Network Communities via Mathematical Programming
• Size reduction of complex networks preserving modularity
• Community Detection via Maximization of Modularity and Its Variants
• A Classification for Community Discovery Methods in Complex Networks
• Community Detection in Complex Networks Using Genetic Algorithms
• Analysis of community structure in networks of correlated data
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• The clustering coefficient and community structure of bipartite networks
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Identifying network communities with a high resolution
• Limited resolution in complex network community detection with Potts model approach
• On Automorphism Groups of Networks
• Maximizing Modularity is hard
• Community Structure of the Physical Review Citation Network
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Accuracy of Mean-Field Theory for Dynamics on Real-World Networks
• Mixing local and global information for community detection in large networks
• Link Prediction in Complex Networks: A Mutual Information Perspective
• Quantifying and identifying the overlapping community structure in networks
• The unreasonable effectiveness of tree-based theory for networks with clustering
• Faster unfolding of communities: speeding up the Louvain algorithm
• Improved community structure detection using a modified fine tuning strategy
• Motif-based communities in complex networks
• Statistical significance of communities in networks
• When are networks truly modular?
• Deciphering Network Community Structure by Surprise
• Computing communities in large networks using random walks (long version)
• Enhancing community detection using a network weighting strategy
• Frustrated hierarchical synchronization and emergent complexity in the human connectome network
• Currency and commodity metabolites: Their identification and relation to the modularity of metabolic networks
• Spectral methods for the detection of network community structure: a comparative analysis
• Surprise maximization reveals the community structure of complex networks
• Z-score-based modularity for community detection in networks
• Ideological and Temporal Components of Network Polarization in Online Political Participatory Media
• Community Detecting By Signaling on Complex Networks
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Multiway spectral community detection in networks
• Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
• Patterns, entropy, and predictability of human mobility and life
• Median evidential c-means algorithm and its application to community detection
• Network Community Detection: A Review and Visual Survey
• Bicomponents and the robustness of networks to failure
• Complex networks vulnerability to module-based attacks
• Communicability Graph and Community Structures in Complex Networks
• Exploring the limits of community detection strategies in complex networks
• Synchronization and modularity in complex networks
• Clustering Drives Assortativity and Community Structure in Ensembles of Networks
• Exploring the structural regularities in networks
• Identification of network modules by optimization of ratio association
• Local dominance unveils clusters in networks
• Will the US Economy Recover in 2010? A Minimal Spanning Tree Study
• Comparison and validation of community structures in complex networks
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• A Parameterized Centrality Metric for Network Analysis
• A New Metric for Quality of Network Community Structure
• Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
• Detecting Important Nodes to Community Structure Using the Spectrum of the Graph
• Phase transitions in semisupervised clustering of sparse networks
• DynaMo: Dynamic Community Detection by Incrementally Maximizing Modularity
• Accuracy and Precision of Methods for Community Identification in Weighted Networks
• Covariance, correlation matrix and the multi-scale community structure of networks
• Trading strategies in the Italian interbank market
• Universal fractal scaling of self-organized networks
• Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
• Large network community detection by fast label propagation
• Communities in Networks
• Towards realistic artificial benchmark for community detection algorithms evaluation
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Modular networks emerge from multiconstraint optimization
• Degree Distribution in Quantum Walks on Complex Networks
• Playing the role of weak clique property in link prediction: A friend recommendation model
• Detecting communities of triangles in complex networks using spectral optimization
• Robust Detection of Hierarchical Communities from Escherichia coli Gene Expression Data
• The Role of Weight on Community Structure of Networks
• Detection of node group membership in networks with group overlap
• Limitation of multi-resolution methods in community detection
• Network community detection using modularity density measures
• A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
• Null models for network data
• Identifying communities by influence dynamics in social networks
• Measuring Significance of Community Structure in Complex Networks
• Fast and accurate determination of modularity and its effect size
• Disentangling homophily, community structure and triadic closure in networks
• Community structures and role detection in music networks
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Cross-validation estimate of the number of clusters in a network
• Communicability and multipartite structures in complex networks at negative absolute temperatures
• Solving large Minimum Vertex Cover problems on a quantum annealer
• Optimal map of the modular structure of complex networks
• Promoting information spreading by using contact memory
• Identifying significant edges via neighborhood information
• Optimizing an Organized Modularity Measure for Topographic Graph Clustering: a Deterministic Annealing Approach
• A New Computationally Efficient Measure of Topological Redundancy of Biological and Social Networks
• Hopping in the crowd to unveil network topology
• Tracking Traders' Understanding of the Market Using e-Communication Data
• A new measure for community structures through indirect social connections
• Magic-State Functional Units: Mapping and Scheduling Multi-Level Distillation Circuits for Fault-Tolerant Quantum Architectures
• Combinatorial approach to Modularity
• Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
• Walk modularity and community structure in networks
• Optimal transport on wireless networks
• Growing community networks with local events
• Mesoscopic analysis of networks: applications to exploratory analysis and data clustering
• Community detection in networks via nonlinear modularity eigenvectors
• Alternative approach to community detection in networks
• Effect of size heterogeneity on community identification in complex networks
• Multiplex Communities and the Emergence of International Conflict
• Network comparison using directed graphlets
• Consistency landscape of network communities
• Maximizing Barber's bipartite modularity is also hard
• Synchronization transition in Sakaguchi-Kuramoto model on complex networks with partial degree-frequency correlation
• Graph Compression -- Save Information by Exploiting Redundancy
• A similarity-based community detection method with multiple prototype representation
• Multi-resolution community detection in massive networks
• Finding Community Structure Based on Subgraph Similarity
• Parallel Generation of Massive Scale-Free Graphs
• Fuzzy Overlapping Community Quality Metrics
• Detecting Communities in Tripartite Hypergraphs
• Evolving network structure of academic institutions
• Optimizing at the Ergodic Edge
• Non-parametric resampling of random walks for spectral network clustering
• Comparative analysis on the selection of number of clusters in community detection
• Insights from Graph Theory on the Morphologies of Actomyosin Networks with Multilinkers
• Variational Community Partition with Novel Network Structure Centrality Prior
• Community detection for weighted bipartite networks
• Complexity of Networks (reprise)
• Weighted hypersoft configuration model
• Finding overlapping communities in networks using evolutionary method
• Partition of Networks into Basins of Attraction
• A Fixed-Mass multifractal approach for unweighted complex networks
• Spectral coarse graining for random walk in bipartite networks
• Structural dynamics of plant-pollinator mutualistic networks
• Total variation based community detection using a nonlinear optimization approach
• Multiple phases in modularity-based community detection
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Community detection for networks with unipartite and bipartite structure
• Intervality and coherence in complex networks
• Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks
• Unsupervised clustering analysis: a multiscale complex networks approach
• Evolutionary Subnetworks in Complex Systems
• Communities and classes in symmetric fractals
• Quality functions in community detection
• Detecting the optimal number of communities in complex networks
• Latent Poisson models for networks with heterogeneous density
• Modularity in Multilayer Networks using Redundancy-based Resolution and Projection-based Inter-Layer Coupling
• Efficient Bayesian Community Detection using Non-negative Matrix Factorisation
• Community Detection in Complex Networks Using Agents
• Multi-level algorithms for modularity clustering
• Detecting network communities beyond assortativity-related attributes
• Fast Community Identification by Hierarchical Growth
• Non-overlapping community detection
• Additive Approximation Algorithms for Modularity Maximization
• Small Worlds in Space: Synchronization, Spatial and Relational Modularity
• Inferring network topology via the propagation process
• Network Community Detection on Metric Space
• A Spectral Representation of Power Systems with Applications to Adaptive Grid Partitioning and Cascading Failure Localization
• Modeling international crisis synchronization in the World Trade Web
• Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
• Extending modularity by capturing the similarity attraction feature in the null model
• Finding Community Structure with Performance Guarantees in Complex Networks
• Network modularity in the presence of covariates
• A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme
• On weakly optimal partitions in modular networks
• Comprehensive spectral approach for community structure analysis on complex networks
• Superelliptical laws for complex networks
• Shaping Communities out of Triangles
• Improved Deep Embeddings for Inferencing with Multi-Layered Networks
• Network growth approach to macroevolution
• Structure and evolution of a European Parliament via a network and correlation analysis
• DANI: A Fast Diffusion Aware Network Inference Algorithm
• The Atlas for the Aspiring Network Scientist
• Gene-based and semantic structure of the Gene Ontology as a complex network
• Botnet Detection using Social Graph Analysis
• Router-level community structure of the Internet Autonomous Systems
• On the Evolution of Neuron Communities in a Deep Learning Architecture
• Nearest Neighbor search in Complex Network for Community Detection
• Cluster Synchronization of Networks via a Canonical Transformation for Simultaneous Block Diagonalization of Matrices
• The ubiquity of small-world networks
• Weighted Label Propagation Algorithm based on Local Edge Betweenness
• Modeling Graphs Using a Mixture of Kronecker Models
• Generic criticality of community structure in random graphs
• Terminal-Set-Enhanced Community Detection in Social Networks
• Spectral community detection in heterogeneous large networks
• An exact-arithmetic algorithm for spanning tree modulus
• Reconstructing propagation networks with temporal similarity metrics
• Controlled Label Propagation: Preventing Over-Propagation through Gradual Expansion
• On role extraction for digraphs via neighbourhood pattern similarity
• Network Reconstruction and Controlling Based on Structural Regularity Analysis
• Emergence of Nestedness in the Public Internet Peering Ecosystem
• Gumbel-softmax Optimization: A Simple General Framework for Combinatorial Optimization Problems on Graphs
• Identification of Community Structures in Networks Employing a Modified Divisive Algorithm
• The spreading ability of nodes towards localized targets in complex networks
• Absence of a resolution limit in in-block nestedness
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay
• Error-Correcting Decoders for Communities in Networks
• Aligning Statistical Dynamics Captures Biological Network Functioning
• Zombie Account Detection Based on Community Detection and Uneven Assignation PageRank
• Compressibility of complex networks
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
• CIIA:A New Algorithm for Community Detection
• Exploring the space of graphs with fixed discrete curvatures
• Interplay between Network Topology and Dynamics in Neural Systems
• A framework for community detection in heterogeneous multi-relational networks