Clustering and Community Detection in Directed Networks: A Survey

Abstract

Networks (or graphs) appear as dominant structures in diverse domains, including sociology, biology, neuroscience and computer science. In most of the aforementioned cases graphs are directed - in the sense that there is directionality on the edges, making the semantics of the edges non symmetric. An interesting feature that real networks present is the clustering or community structure property, under which the graph topology is organized into modules commonly called communities or clusters. The essence here is that nodes of the same community are highly similar while on the contrary, nodes across communities present low similarity. Revealing the underlying community structure of directed complex networks has become a crucial and interdisciplinary topic with a plethora of applications. Therefore, naturally there is a recent wealth of research production in the area of mining directed graphs - with clustering being the primary method and tool for community detection and evaluation. The goal of this paper is to offer an in-depth review of the methods presented so far for clustering directed networks along with the relevant necessary methodological background and also related applications. The survey commences by offering a concise review of the fundamental concepts and methodological base on which graph clustering algorithms capitalize on. Then we present the relevant work along two orthogonal classifications. The first one is mostly concerned with the methodological principles of the clustering algorithms, while the second one approaches the methods from the viewpoint regarding the properties of a good cluster in a directed network. Further, we present methods and metrics for evaluating graph clustering results, demonstrate interesting application domains and provide promising future research directions.

86 pages, 17 figures. Physics Reports Journal (To Appear)

References in corpus (17)

• Modularity and community structure in networks
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Comparing community structure identification
• Community structure in directed networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• An information-theoretic framework for resolving community structure in complex networks
• Mixture models and exploratory analysis in networks
• Robustness of community structure in networks
• Extending the definition of modularity to directed graphs with overlapping communities
• Size reduction of complex networks preserving modularity
• A Classification for Community Discovery Methods in Complex Networks
• Role models for complex networks
• Directed network modules
• Inversion method for content-based networks
• Centralized Modularity of N-Linked Glycosylation Pathways in Mammalian Cells
• Detecting groups of similar components in complex networks

Cited by in corpus (47)

• Community detection in networks: A user guide
• Higher-order organization of complex networks
• Percolation on complex networks: Theory and application
• A Comprehensive Survey on Community Detection with Deep Learning
• Nestedness in complex networks: Observation, emergence, and implications
• The many facets of community detection in complex networks
• Evolution of cooperation with asymmetric social interactions
• Machine Learning at the Edge: A Data-Driven Architecture with Applications to 5G Cellular Networks
• Magnetic eigenmaps for community detection in directed networks
• Statistical Analysis of Risk Assessment Factors and Metrics to Evaluate Radicalisation in Twitter
• Friendship Paradox Biases Perceptions in Directed Networks
• A Survey on the Densest Subgraph Problem and Its Variants
• Network structural origin of instabilities in large complex systems
• Different approaches to community detection
• Community detection in directed acyclic graphs
• Dynamical robustness of network of oscillators
• Navigating the Landscape of Multiplayer Games
• STWalk: Learning Trajectory Representations in Temporal Graphs
• Exploration of an Interdisciplinary Scientific Landscape
• Cycle and flow trusses in directed networks
• Identifying the global terror hubs and vulnerable motifs using complex network dynamics
• Network clustering and community detection using modulus of families of loops
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• Community-Aware Graph Signal Processing
• Weighted Community Detection and Data Clustering Using Message Passing
• Koopman-based spectral clustering of directed and time-evolving graphs
• Data clustering: a fundamental method in data science and management
• Local community extraction in directed networks
• Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs
• Emergence and persistence of communities in coevolutionary networks
• Multiple Kernel Representation Learning on Networks
• A metric on directed graphs and Markov chains based on hitting probabilities
• Spectral co-Clustering in Multi-layer Directed Networks
• Generalized $k$-core pruning process on directed networks
• Community detection for directed networks revisited using bimodularity
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Evolving community structure in the international pesticide trade networks
• Optimal timescale for community detection in growing networks
• Stochastic graph Voronoi tessellation reveals community structure
• Probing Black Hole Microstate Evolution with Networks and Random Walks
• Bipartitioning of directed and mixed random graphs
• Contribution of directedness in graph spectra
• From chambers to echo chambers: Quantifying polarization with a second-neighbor approach applied to Twitter's climate discussion
• Scalable Community Detection Using Quantum Hamiltonian Descent and QUBO Formulation
• An iterative spectral algorithm for digraph clustering
• Directed Network Laplacians and Random Graph Models
• Detecting Communities from Heterogeneous Graphs: A Context Path-based Graph Neural Network Model