Community structure in directed networks

Abstract

We consider the problem of finding communities or modules in directed networks. The most common approach to this problem in the previous literature has been simply to ignore edge direction and apply methods developed for community discovery in undirected networks, but this approach discards potentially useful information contained in the edge directions. Here we show how the widely used benefit function known as modularity can be generalized in a principled fashion to incorporate the information contained in edge directions. This in turn allows us to find communities by maximizing the modularity over possible divisions of a network, which we do using an algorithm based on the eigenvectors of the corresponding modularity matrix. This method is shown to give demonstrably better results than previous methods on a variety of test networks, both real and computer-generated.

5 pages, 3 figures

References in corpus (14)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Fast algorithm for detecting community structure in networks
• Evolution of networks
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Modularity from Fluctuations in Random Graphs and Complex Networks
• An information-theoretic framework for resolving community structure in complex networks
• Mixture models and exploratory analysis in networks
• Module identification in bipartite and directed networks
• Size reduction of complex networks preserving modularity
• A network-based ranking system for American college football

Cited by in corpus (159)

• Community detection in graphs
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• A smart local moving algorithm for large-scale modularity-based community detection
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The complex network of global cargo ship movements
• Clustering and Community Detection in Directed Networks: A Survey
• The evolutionary origins of modularity
• Community detection in networks with positive and negative links
• Illuminating search spaces by mapping elites
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Global labor flow network reveals the hierarchical organization and dynamics of geo-industrial clusters in the world economy
• Narrow scope for resolution-limit-free community detection
• 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
• Community Detection via Maximization of Modularity and Its Variants
• The multilayer connectome of Caenorhabditis elegans
• A Classification for Community Discovery Methods in Complex Networks
• Graph Metrics for Temporal Networks
• Analysis of community structure in networks of correlated data
• Edge direction and the structure of networks
• Modularity clustering is force-directed layout
• Effect of correlations on network controllability
• LinkRank: Finding communities in directed networks
• Exploring the Free Energy Landscape: From Dynamics to Networks and Back
• Community Structure of the Physical Review Citation Network
• Full-density multi-scale account of structure and dynamics of macaque visual cortex
• Coauthorship and Citation Networks for Statisticians
• Analyzing complex functional brain networks: fusing statistics and network science to understand the brain
• The evolutionary origins of hierarchy
• Network structure of inter-industry flows
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Heterogeneous Bond Percolation on Multitype Networks with an Application to Epidemic Dynamics
• Tensor Spectral Clustering for Partitioning Higher-order Network Structures
• Emergence of core-peripheries in networks
• The frustrated brain: From dynamics on motifs to communities and networks
• Modularity measure of networks with overlapping communities
• Spectral tripartitioning of networks
• Mesoscopic organization reveals the constraints governing C. elegans nervous system
• Kantian fractionalization predicts the conflict propensity of the international system
• Cluster-based feedback control of turbulent post-stall separated flows
• Finding multiple core-periphery pairs in networks
• Core-periphery structure requires something else in the network
• A Parameterized Centrality Metric for Network Analysis
• A functional clustering algorithm for the analysis of dynamic network data
• A New Metric for Quality of Network Community Structure
• A Spectral Framework for Anomalous Subgraph Detection
• Magnetic eigenmaps for community detection in directed networks
• Networking - A Statistical Physics Perspective
• Modular architecture facilitates noise-driven control of synchrony in neuronal networks
• Communities in Networks
• Four Years of FAccT: A Reflexive, Mixed-Methods Analysis of Research Contributions, Shortcomings, and Future Prospects
• Network community-based model reduction for vortical flows
• Feature-Gathering Dependency-Based Software Clustering Using Dedication and Modularity
• Detecting communities of triangles in complex networks using spectral optimization
• Post-processing partitions to identify domains of modularity optimization
• Diffusion-based neuromodulation can eliminate catastrophic forgetting in simple neural networks
• Influence of Reciprocal links in Social Networks
• On the Complexity of Newman's Community Finding Approach for Biological and Social Networks
• Efficient community-based control strategies in adaptive networks
• Detecting Cohesive and 2-mode Communities in Directed and Undirected Networks
• Centralized Modularity of N-Linked Glycosylation Pathways in Mammalian Cells
• Network structural origin of instabilities in large complex systems
• Identifying vortical network connectors for turbulent flow modification
• Impact of hierarchical modular structure on ranking of individual nodes in directed networks
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
• Magnetic Eigenmaps for the Visualization of Directed Networks
• Community detection in directed acyclic graphs
• Structure of Heterogeneous Networks
• Sampling properties of directed networks
• Determining the number of factors in a forecast model by a random matrix test: cryptocurrencies
• The Emergence of Canalization and Evolvability in an Open-Ended, Interactive Evolutionary System
• Combinatorial approach to Modularity
• Modularity and the spread of perturbations in complex dynamical systems
• Strong associations between microbe phenotypes and their network architecture
• Complex-valued information entropy measure for networks with directed links (digraphs). Application to citations by community agents with opposite opinions
• Co-community Structure in Time-varying Networks
• Cycle and flow trusses in directed networks
• Consistency landscape of network communities
• Emergence of scale-free close-knit friendship structure in online social networks
• Worldwide Scientific Landscape on Fires in Photovoltaic
• An ensemble meta-estimator to predict source code testability
• The specificity and robustness of long-distance connections in weighted, interareal connectomes
• Identifying the Community Roles of Social Capitalists in the Twitter Network
• Randomized methods to characterize large-scale vortical flow network
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Communication and trust in the bounded confidence model
• Weighted Community Detection and Data Clustering Using Message Passing
• Finding overlapping communities in networks using evolutionary method
• Analysis of risk propagation using the world trade network
• Temporal prediction of epidemic patterns in community networks
• A community role approach to assess social capitalists visibility in the Twitter network
• Guiding Neuroevolution with Structural Objectives
• Structural dynamics of plant-pollinator mutualistic networks
• Wall-induced anisotropy effects on turbulent mixing in channel flow: A network-based analysis
• Comparison of Cross-Validation Methods for Stochastic Block Models
• Local community extraction in directed networks
• Modularity in Multilayer Networks using Redundancy-based Resolution and Projection-based Inter-Layer Coupling
• Random walks in directed modular networks
• Detecting groups of similar components in complex networks
• A Survey of Community Search Over Big Graphs
• Cycle flow based module detection in directed recurrence networks
• Community Detection using a Measure of Global Influence
• Discovering universal statistical laws of complex networks
• Additive Approximation Algorithms for Modularity Maximization
• Measuring dynamical systems on directed hyper-graphs
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Scalable Spectral Algorithms for Community Detection in Directed Networks
• Generalized $k$-core pruning process on directed networks
• Forget Partitions: Cluster Synchronization in Directed Networks Generate Hierarchies
• Node-Context Network Clustering using PARAFAC Tensor Decomposition
• On the reliable and efficient numerical integration of the Kuramoto model and related dynamical systems on graphs
• Search for overlapped communities by parallel genetic algorithms
• Communities recognition in the Chesapeake Bay ecosystem by dynamical clustering algorithms based on different oscillators systems
• Community detection for directed networks revisited using bimodularity
• Extending modularity by capturing the similarity attraction feature in the null model
• On the Stability of Community Detection Algorithms on Longitudinal Citation Data
• Antifragility of stochastic transport on networks with damage
• Habitat variability does not generally promote metabolic network modularity in flies and mammals
• A simpler spectral approach for clustering in directed networks
• A New Community Definition For MultiLayer Networks And A Novel Approach For Its Efficient Computation
• Evaluating the effect of topic consideration in identifying communities of rating-based social networks
• Feedback arcs and node hierarchy in directed networks
• Eigenvectors for clustering: Unipartite, bipartite, and directed graph cases
• Finding Influential Cores via Normalized Ricci Flows in Directed and Undirected Hypergraphs with Applications
• Can Few Lines of Code Change Society ? Beyond fack-checking and moderation : how recommender systems toxifies social networking sites
• Temporal stability in human interaction networks
• Structure-Preserving Community In A Multilayer Network: Definition, Detection, And Analysis
• The Atlas for the Aspiring Network Scientist
• A Coevolutionary Variable Neighborhood Search Algorithm for Discrete Multitasking (CoVNS): Application to Community Detection over Graphs
• Comprehensive spectral approach for community structure analysis on complex networks
• Ranking of Communities in Multiplex Spatiotemporal Models of Brain Dynamics
• Higher-Order Spectral Clustering of Directed Graphs
• Metrics for Community Analysis: A Survey
• Modelling and Predicting Online Vaccination Views using Bow-tie Decomposition
• Return to basics: Clustering of scientific literature using structural information
• Detecting highly cyclic structure with complex eigenpairs
• Vortical interactions in turbulent thermoacoustic systems
• Quantitative Function and Algorithm for Community Detection in Bipartite Networks
• Mutual or Unrequited Love: Identifying Stable Clusters in Social Networks with Uni- and Bi-directional Links
• Identification de rôles communautaires dans des réseaux orientés appliquée à Twitter
• Unveiling Contextual Similarity of Things via Mining Human-Thing Interactions in the Internet of Things
• An analysis of community structure in Brazilian political topic-based Twitter networks
• SArF Map: Visualizing Software Architecture from Feature and Layer Viewpoints
• Rôle communautaire des capitalistes sociaux dans Twitter
• Refinement for community structures of bipartite networks
• CellSegmenter: unsupervised representation learning and instance segmentation of modular images
• Optimisation dans la détection de communautés recouvrantes et équilibre de Nash
• Community Integration Algorithms (CIAs) for Dynamical Systems on Networks
• Overlapping Community Detection Optimization and Nash Equilibrium
• Modularity of Erdős-Rényi random graphs
• Block-corrected Modularity for Community Detection
• Functional and spatial rewiring jointly generate convergent-divergent units in self-organizing networks
• Spectral Complexity of Directed Graphs and Application to Structural Decomposition
• Network Community Detection with A Successive Spectral Relaxation Method
• Identifying Community Structures in Dynamic Networks
• A fast clustering algorithm for mining social network data
• Finding New Order in Biological Functions from the Network Structure of Gene Annotations
• Improving Data Forwarding in Mobile Social Networks with Infrastructure Support: A Space-Crossing Community Approach