Clustering and community detection in directed networks: a survey
From MaRDI portal
Publication:514409
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 2084315 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 1844609 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A Comparison of the Stability Characteristics of Some Graph Theoretic Clustering Methods
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A classification for community discovery methods in complex networks
- Authoritative sources in a hyperlinked environment
- Clustering by passing messages between data points
- Communities in Networks
- Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
- Community structure in social and biological networks
- Comparing clusterings -- an information based distance
- Complex networks: structure and dynamics
- Computing Communities in Large Networks Using Random Walks
- Digraph Laplacian and the degree of asymmetry
- Emergence of Scaling in Random Networks
- Graph clustering
- Graph spectra for complex networks
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Laplacians and the Cheeger inequality for directed graphs
- Large scale structure and dynamics of complex networks. From information technology to finance and natural science.
- Local Partitioning for Directed Graphs Using PageRank
- Mixed membership stochastic blockmodels
- Mixture models and exploratory analysis in networks
- Mutual or unrequited love: identifying stable clusters in social networks with uni- and bi-directional links
- Optimization by simulated annealing
- Random walks on digraphs, the generalized digraph Laplacian and the degree of asymmetry
- Relaxing the uniformity and independence assumptions using the concept of fractal dimension
- Role models for complex networks
- Spectral methods for graph clustering - a survey
- Stochastic Blockmodels for Directed Graphs
- The Structure and Function of Complex Networks
Cited in
(57)- A hierarchical decision-making framework in social networks for efficient disaster management
- Weighted community detection and data clustering using message passing
- Koopman-based spectral clustering of directed and time-evolving graphs
- Does isolating high-modularity communities prevent cascading failure?
- Mutual or unrequited love: identifying stable clusters in social networks with uni- and bi-directional links
- Detecting groups in large vector autoregressions
- Overlapping communities and roles in networks with node attributes: probabilistic graphical modeling, Bayesian formulation and variational inference
- Spectral co-clustering in multi-layer directed networks
- Approximation of the second eigenvalue of the \(p\)-Laplace operator in symmetric domains
- Modularity of directed networks: cycle decomposition approach
- Adaptive directional Haar tight framelets on bounded domains for digraph signal representations
- Representation of functions on big data associated with directed graphs
- Clustering method based on the elastic energy functional of directed signed weighted graphs
- Directed Community Detection With Network Embedding
- Model-Based Edge Clustering
- Direction matters in complex networks: a theoretical and applied study for greedy modularity optimization
- Community structure detection for directed networks through modularity optimisation
- On the detection of transitive clusters in undirected networks
- Dynamics of cluster structure in financial correlation matrix
- scientific article; zbMATH DE number 3843460 (Why is no real title available?)
- Diclique clustering in a directed random graph
- A parameterized complexity view on collapsing \(k\)-cores
- Computing communities in complex networks using the Dirichlet processing Gaussian mixture model with spectral clustering
- Community detection in complex networks: from statistical foundations to data science applications
- Identifiability and parameter estimation of the overlapped stochastic co-block model
- Direction matters: on influence-preserving graph summarization and max-cut principle for directed graphs
- CLBA: a Coulomb's law based algorithm for community detection in directed networks
- Weighting dissimilarities to detect communities in networks
- Inverse modelling-based multi-objective evolutionary algorithm with decomposition for community detection in complex networks
- Detection of structurally homogeneous subsets in graphs
- Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs
- A label propagation-based method for community detection in directed signed social networks
- Uniform and most uniform partitions of trees
- Percolation on complex networks: theory and application
- Robust Hierarchical Clustering for Directed Networks: An Axiomatic Approach
- Dynamical robustness of network of oscillators
- Robust asymmetric non-negative matrix factorization for clustering nodes in directed networks
- Complex network clustering algorithms
- Partitioning of relative sensing networks: a stability margin perspective
- Bayesian estimation of the latent dimension and communities in stochastic blockmodels
- Explore of the fuzzy community structure integrating the directed line graph and likelihood optimization
- Generalized \(k\)-core pruning process on directed networks
- Effective Resistance Preserving Directed Graph Symmetrization
- Applying correlation dimension to the analysis of the evolution of network structure
- A metric on directed graphs and Markov chains based on hitting probabilities
- A framework of mapping undirected to directed graphs for community detection
- An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
- Adaptive learning control synchronization for unknown time-varying complex dynamical networks with prescribed performance
- Co-clustering directed graphs to discover asymmetries and directional communities
- Directionality of real world networks as predicted by path length in directed and undirected graphs
- scientific article; zbMATH DE number 7307464 (Why is no real title available?)
- Bipartitioning of directed and mixed random graphs
- Analyzing the stock market based on the structure of \textit{kNN} network
- Group Definition Based on Flow in Community Detection
- Spectral based hypothesis testing for community detection in complex networks
- A method to cluster the nodes in a directed graph
- Structure-oriented prediction in complex networks
This page was built for publication: Clustering and community detection in directed networks: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q514409)
