Clustering and Community Detection in Directed Networks: A Survey

By Fragkiskos D. Malliaros, Michalis Vazirgiannis. 2013

732 citations recorded by the source corpus.

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 nonsymmetric as the source node transmits some property to the target one but not vice versa. 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 relevant application domains. Therefore, naturally there is a recent wealth of research production in the area of mining directed graphs — with clustering being the primary method sought and the primary tool for community detection and evaluation. The goal of this paper is to offer an in-depth comparative 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.

Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Debiasing Community Detection: The Importance of Lowly Connected Nodes (2019, background): “ety of things including karate club membership, political leanings, and deeply-held beliefs. Traditionally, these groups are identified by searching for densely-connected groups of nodes in the graph [14]. More recently, attributed approaches go beyond merely the links to cluster nodes based upon th”
Using Geodesic Space Density Gradients for Network Community Detection (2017, background): “Thus identification of network communities is an important topic across a number of research areas [14], [16].”
A Comprehensive Survey on Community Detection With Deep Learning (2021, background): “…the patterns and functions inherent to communities [36], [37], existing surveys have mainly focused on certain aspects of community detection, including speciﬁc techniques [13], [14], [38]–[41], different network types [5], [12], [42], community types [6], [7], and application scenarios [10], [43].”
A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning (2021, background): “cantly beyond some of the existing surveys [42], [43].”
Detecting cohesive and 2-mode communities indirected and undirected networks (2014, background): “Detecting communities of densely connected sets of nodes is an extensively researched area [14, 30, 35, 42] with a plethora of different algorithms and heuristics.”
Network Representation Learning: A Survey (2017, background): “decomposition of a matrix [2] with at least quadratic time”
Community detection in networks: A user guide (2016, background): “More info on network clustering can be found in several review articles (Chakraborty et al., 2016; Coscia et al., 2011; Fortunato, 2010; Malliaros and Vazirgiannis, 2013; Newman, 2012; Parthasarathy et al., 2011; Porter et al., 2009; Schaeffer, 2007; Xie et al., 2013).”