Clustering and community detection in directed networks: a survey
From MaRDI portal
Publication:514409
DOI10.1016/J.PHYSREP.2013.08.002zbMATH Open1356.05151arXiv1308.0971OpenAlexW3098742898WikidataQ30040732 ScholiaQ30040732MaRDI QIDQ514409FDOQ514409
Fragkiskos D. Malliaros, Michalis Vazirgiannis
Publication date: 1 March 2017
Published in: Physics Reports (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1308.0971
Recommendations
Applications of graph theory (05C90) Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82)
Cites Work
- Title not available (Why is that?)
- Clustering by Passing Messages Between Data Points
- Optimization by Simulated Annealing
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complex networks: structure and dynamics
- Mixed membership stochastic blockmodels
- Emergence of Scaling in Random Networks
- Mixture models and exploratory analysis in networks
- The Structure and Function of Complex Networks
- Community structure in social and biological networks
- Graph clustering
- Stochastic Blockmodels for Directed Graphs
- Comparing clusterings -- an information based distance
- Title not available (Why is that?)
- Authoritative sources in a hyperlinked environment
- Laplacians and the Cheeger inequality for directed graphs
- Large scale structure and dynamics of complex networks. From information technology to finance and natural science.
- Computing Communities in Large Networks Using Random Walks
- Relaxing the uniformity and independence assumptions using the concept of fractal dimension
- Title not available (Why is that?)
- Communities in Networks
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Spectral methods for graph clustering - a survey
- A Comparison of the Stability Characteristics of Some Graph Theoretic Clustering Methods
- Mutual or Unrequited Love: Identifying Stable Clusters in Social Networks with Uni- and Bi-directional Links
- Random Walks on Digraphs, the Generalized Digraph Laplacian and the Degree of Asymmetry
- Title not available (Why is that?)
- Digraph Laplacian and the Degree of Asymmetry
- A classification for community discovery methods in complex networks
- Local Partitioning for Directed Graphs Using PageRank
- Role models for complex networks
Cited In (46)
- Community structure detection for directed networks through modularity optimisation
- Computing communities in complex networks using the Dirichlet processing Gaussian mixture model with spectral clustering
- Adaptive learning control synchronization for unknown time-varying complex dynamical networks with prescribed performance
- Directed Community Detection With Network Embedding
- Spectral based hypothesis testing for community detection in complex networks
- Representation of functions on big data associated with directed graphs
- Robust Hierarchical Clustering for Directed Networks: An Axiomatic Approach
- Adaptive directional Haar tight framelets on bounded domains for digraph signal representations
- Percolation on complex networks: theory and application
- Detecting groups in large vector autoregressions
- Applying correlation dimension to the analysis of the evolution of network structure
- Analyzing the stock market based on the structure of \textit{kNN} network
- On the detection of transitive clusters in undirected networks
- Generalizedk-core pruning process on directed networks
- A label propagation-based method for community detection in directed signed social networks
- Dynamical robustness of network of oscillators
- Structure-oriented prediction in complex networks
- Uniform and most uniform partitions of trees
- Community detection in complex networks: from statistical foundations to data science applications
- CLBA: a Coulomb's law based algorithm for community detection in directed networks
- Bayesian estimation of the latent dimension and communities in stochastic blockmodels
- Partitioning of relative sensing networks: a stability margin perspective
- Weighted community detection and data clustering using message passing
- Approximation of the second eigenvalue of the \(p\)-Laplace operator in symmetric domains
- Identifiability and parameter estimation of the overlapped stochastic co-block model
- Weighting dissimilarities to detect communities in networks
- Inverse modelling-based multi-objective evolutionary algorithm with decomposition for community detection in complex networks
- Does isolating high-modularity communities prevent cascading failure?
- Spectral co-clustering in multi-layer directed networks
- Clustering method based on the elastic energy functional of directed signed weighted graphs
- Direction matters in complex networks: a theoretical and applied study for greedy modularity optimization
- Title not available (Why is that?)
- A hierarchical decision-making framework in social networks for efficient disaster management
- Robust asymmetric non-negative matrix factorization for clustering nodes in directed networks
- Overlapping communities and roles in networks with node attributes: probabilistic graphical modeling, Bayesian formulation and variational inference
- Modularity of directed networks: cycle decomposition approach
- Effective Resistance Preserving Directed Graph Symmetrization
- Dynamics of cluster structure in financial correlation matrix
- A Metric on Directed Graphs and Markov Chains Based on Hitting Probabilities
- Model-Based Edge Clustering
- Title not available (Why is that?)
- Title not available (Why is that?)
- Bipartitioning of directed and mixed random graphs
- Group Definition Based on Flow in Community Detection
- Koopman-based spectral clustering of directed and time-evolving graphs
- An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
Uses Software
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)
