Clustering and Community Detection in Directed Networks: A Survey

Fragkiskos D. Malliaros; Michalis Vazirgiannis

Source-linked AI summary

Clustering and Community Detection in Directed Networks: A Survey

Fragkiskos D. Malliaros, Michalis Vazirgiannis

arXiv:1308.0971v1Aug 5, 2013cs.SIcs.IRphysics.bio-phphysics.comp-phphysics.soc-ph

TL;DR

The paper addresses the problem of clustering and community detection in directed networks, including the need for a formal and precise problem definition. It provides a comprehensive review of directed-network clustering methods and offers a supplementary classification intended to help practitioners.

Problem
A formal and precise definition of the graph clustering problem in directed networks remains a major issue to address.
Method
The paper thoroughly reviews clustering and community-detection methods for directed networks and organizes them using complementary classification schemes.
Results
The survey is presented as the first comprehensive review fully devoted to clustering and community detection in directed networks.
Takeaways & Limitations
The supplementary classification may be useful for practitioners working with directed-network clustering methods.
Takeaways & Limitations
Modularity-based approaches suffer from the resolution limit.

Abstract

from arXiv · show

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.

1. Introduction

Directed networks exhibit community structure, but clustering them is challenging because edge direction carries nonsymmetric semantics. This survey reviews directed-network clustering methods, organizes them by methodology and cluster properties, and discusses evaluation and applications.

Real-world networks often contain groups with high internal edge density and low density between groups, a property called clustering or community structure.
Graph clustering groups nodes by similarity, using topological features, node and edge characteristics, or both.
The survey focuses on grouping nodes within a single directed graph rather than clustering whole graphs as individual objects.
Directed-network clustering matters in Web, social, biological, neuroscience, and other applications where edge direction represents meaningful relations.
Ignoring direction allows undirected algorithms to be applied but may discard underlying semantics, including those in citation and Web networks.
The survey organizes prior work by methodological principles and by cluster properties, including patterns beyond simple edge density, and aims to support practitioners.

2. Basic Terminology and Background

This section establishes graph-theoretic, matrix, spectral, connectivity, and random-walk concepts used to study directed-network clustering. It also notes quality-measure limitations, including modularity’s resolution limit.

Graph Theory: Graphs may be directed or undirected, weighted or unweighted, and represented by nodes V and edges E.Directed edges are ordered pairs; undirected graphs contain both reciprocal edges.
Graph Theory: Bipartite graphs partition nodes into two disjoint sets whose edges connect only across the partitions.There are no edges between nodes belonging to the same partition.
Graph Theory: The adjacency matrix A records edge existence or weights, with symmetric A for undirected graphs and nonsymmetric A for directed graphs.Rows and columns represent graph nodes, while entries encode edges or their weights.
Graph Theory: Directed graphs distinguish in-degree from out-degree, and support strong, directed, and weak notions of connectivity.Weak connectivity ignores edge directionality, whereas strong connectivity requires directed paths in both directions between every node pair.
Linear Algebra and Spectral Graph Theory: Because directed adjacency matrices are nonsymmetric and may have complex eigenvalues, singular-value decomposition provides left and right singular vectors and singular values.The decomposition is A = UΣV^T, with Σ containing singular values.
Quality Measures: Modularity is used to quantify community quality, but optimization is computationally difficult and may miss communities below a characteristic size.This limitation is known as the resolution limit.

3. Clusters in Directed Networks – Intuition and Discussion

Directed-network clustering groups similar nodes, but the appropriate notion of similarity depends on the application and network features. The survey distinguishes density-based from pattern-based clusters and frames detection as optimizing an objective function, while noting that directedness complicates established measures.

A cluster is a set of nodes sharing common or similar features, with similarity and relevant characteristics defining the clustering notion.
Community detection first specifies an objective function capturing the chosen clustering structure, then assigns nodes to clusters while optimizing that function.
Directed-network clusters are categorized as density-based groups with edge-density structure or pattern-based groups exhibiting structures such as flow circulation.
No single clustering definition applies universally: the choice depends on the application domain, network features, prior structural knowledge, and desired cluster type.
Density-based Clusters: Density-based clustering seeks more intra-cluster than inter-cluster edges, exemplified by three dense groups versus a homogeneous directed network lacking obvious community structure.
Density-based Clusters: Extending density-based measures to directed graphs is nontrivial because directionality can invalidate desired cluster properties and complicate graph-theoretic quality measures.

4. Dealing with Edge Directionality: Approaches for Identifying Clusters-Communities in Directed Networks

The survey classifies directed-network clustering methods by how they handle edge directionality, while allowing overlapping categories when approaches combine methodological features. It reviews transformations, extensions of undirected methods, alternative probabilistic and information-theoretic approaches, and related applications and future directions.

Naive graph transformation approach: Naive graph transformation treats directed graphs as undirected, enabling existing undirected clustering algorithms but discarding edge-direction semantics.In citation networks, replacing a one-way citation with an undirected edge incorrectly introduces reciprocity and loses the endorsement meaning.
Transformations maintaining directionality: Directionality-preserving transformations convert directed graphs into weighted unipartite or bipartite undirected networks before applying suitable clustering algorithms.Weights can encode directionality, while bipartite constructions separate hub and authority roles.
Extending clustering objective functions and methodologies to directed networks: Extensions of undirected objectives and algorithms adapt criteria such as modularity, weighted cuts, and spectral clustering to directed networks.These approaches explicitly incorporate directionality into objective functions or algorithmic tools rather than assuming edge symmetry.
Alternative approaches: Alternative approaches include information-theoretic methods, probabilistic models with statistical inference, stochastic blockmodeling, and other diverse methodologies.The survey reviews probabilistic-model and stochastic-blockmodeling methods separately because they rely on different statistical-inference concepts.
The survey uses overlapping classification when methods combine transformations with objective-function extensions and notes dynamic directed community detection as a future direction.It also reports that extending methodologies to directed networks constitutes the largest body of reviewed work.
The proposed classification organizes directed-network clustering methods according to their methodological principles and algorithmic approaches.
Reviewed methods can identify pattern-based or flow-based clusters, and directionality-aware modularity can reveal meaningful communities where ignoring direction cannot.Some transformations preserve connectivity and clarify community structure, while other modularity formulations address limitations of direction-insensitive criteria.

Modularity for Overlapping Communities

Overlapping-community modularity extends directed-network community evaluation beyond partitions in which each node belongs to only one community. Nodes receive graded memberships, which are combined into edge-community contributions and optimized to identify overlapping structure.

Motivation: Overlapping clustering allows directed-network nodes to belong to multiple communities simultaneously.This reflects the observation that real networks are often not divided into sharp sub-networks.
Modularity construction: The proposed modularity generalizes the configuration-model comparison by replacing hard community assignments with node and edge belonging coefficients.The construction assumes node memberships are independent when estimating expected belonging coefficients.
Membership representation: The method assigns each node a membership coefficient αi,c indicating its strength of belonging to community c.Each node is represented by a vector of membership coefficients across communities.
Edge contributions: For each directed edge, an edge-community belonging factor βe,c is computed from the membership coefficients of its two endpoints.The function βe,c = F(αi,c, αj,c) determines how strongly edge e belongs to community c.
Optimization: The membership function should yield zero modularity without community structure and higher values for better community structure.A genetic algorithm is presented to optimize the resulting criterion and identify overlapping communities in directed networks.

Local Definition of Modularity

Local modularity evaluates each directed community against a null expectation derived from that community and its neighboring communities rather than the full network. Experiments report more cohesive partitions when this local modularity is maximized.

Null model: The configuration model serves as the random-graph competitor, assigning equal edge probability to every node pair.This model ignores the relative positions of nodes in the graph.
Local modularity: Local modularity computes each community’s expected internal edges using the community and its neighboring communities.This contrasts with expectations based on the full network.
Local modularity: The local formulation uses internal and external edge counts for each community in its modularity calculation.The notation includes the number of edges within the community and edges contained in its neighborhood.
Experimental results: Maximizing Qlocal provides more cohesive partitions in both a school-interaction network and the metabolic network of E. coli.The comparison is reported for datasets involving students and classmates, and for E. coli metabolism.

Discussion

The discussion highlights modularity’s resolution limit and surveys spectral and cut-based approaches for directed-network clustering. Spectral methods can directly cluster graphs or optimize objective functions after matrix relaxation.

Discussion: Modularity optimization may miss communities smaller than a network-scale-dependent size.This resolution limit can produce single communities or merge smaller weakly connected communities.
Discussion: Meta-algorithmic approaches have been proposed to help overcome modularity’s resolution limit.The survey notes these approaches as possible remedies rather than eliminating the limitation itself.
Cut-based clustering: Cut-based clustering seeks partitions with few or low-weight inter-community edges and high-weight intra-community edges.Objective functions may use a single criterion or combine multiple criteria.
Spectral optimization: Cut-based objectives are typically computationally difficult, but relaxed matrix formulations enable spectral optimization through eigenvectors.The resulting eigenvectors can be used to obtain final clusters.
Spectral methods: Spectral methods serve both as clustering frameworks and as optimization frameworks for objective functions.The latter includes spectral optimization of modularity expressed in matrix form.

Laplacian Matrix for Directed Networks

Directed spectral clustering generalizes Laplacian and normalized-cut ideas through random-walk-based matrices. The resulting eigenvectors support bipartitioning, k-partitioning, and extensions to labeled, multiple-view directed graphs.

Directed Laplacian: Chung’s directed Laplacian is based on a random walk and uses the stationary distribution of that walk.Its construction provides a directed-network analogue of the Laplacian used for spectral clustering.
Directed Laplacian: The directed Laplacian satisfies a Cheeger inequality, making its second-smallest non-zero eigenvector useful for approximating a good network cut.This connects the spectral quantity to normalized-cut approximation.
Hierarchical clustering: Hierarchical directed spectral clustering recursively uses the eigenvector associated with the second-smallest non-zero eigenvalue to split graphs into two clusters.The recursive process may terminate when a resulting subgraph contains fewer than p nodes.
Directed spectral algorithm: A directed spectral algorithm forms a symmetrized matrix from the transition matrix and stationary distribution, then partitions vertices by the signs of its second-eigenvector entries.The stated output is a two-part partition minimizing normalized cut.
Extensions: Using eigenvectors associated with the k largest eigenvalues extends the method from bipartitioning to k-partitioning.The framework is also extended to labeled data and multiple graph views.

Cut-based Measures for Directed Networks

Cut-based methods adapt normalized-cut and spectral ideas to directed networks by preserving directionality or transforming the problem into a symmetric one. Weighted-cut parameters and random-walk formulations provide flexible objectives, but eigenvector methods work best when modular structure is clear.

Weighted cuts: Weighted cut generalizes normalized cut by parameterizing cluster balance with T and normalization with T ′.Different choices of T and T ′ recover multiple normalized-cut measures, making the criterion more flexible.
Weighted cuts: Optimizing weighted cut can be relaxed to an analogous symmetric problem, enabling existing spectral algorithms and theoretical results to extract clusters.The symmetrized weighted-cut formulation produced better results than simple linear-algebraic symmetrizations in experiments.
Normalized and spectral cuts: Directed-network clustering extends normalized cuts through objectives that account for asymmetric transitions and directed edge structure.Directed formulations can use Laplacian eigenvectors or transition probabilities to approximate cut criteria.
Random-walk formulations: Random-walk methods identify clusters through low transition probabilities between sets, with PageRank-style teleportation handling directed graphs and missing edges.Forward and backward walks can separately model authority- and hub-based structure, while two-step walks capture co-citation and co-reference patterns.
Spectral limitations: Eigenvector-based clustering is limited in practice because real large networks rarely have clear modular structure or step-wise eigenvector components.Correlation-based methods address this by transforming directed adjacency information with A A^T and clustering correlated eigenvector components.

Clique Percolation Method for Overlapping Community Detection

Directed clique percolation extends overlapping-community detection by defining direction-sensitive k-cliques and joining adjacent cliques into modules. The directed k-clique definition is explicitly non-unique.

Undirected foundation: Clique percolation detects dense connected modules locally, allowing communities to overlap when nodes belong to multiple modules.In the undirected formulation, modules are unions of adjacent k-cliques sharing k −1 nodes.
Directed extension: A directed k-clique is a complete subgraph whose nodes can be ordered so every pair has an edge from higher to lower order.The ordering uses each node’s restricted out-degree within the clique.
Directed extension: Directed k-clique modules are unions of adjacent directed k-cliques, but the proposed directed definition is not unique.The authors note that alternative extensions can also be considered.

Local Density Clustering

Local and information-theoretic approaches detect directed communities from neighborhood density, random-walk flow, compression, or matrix regularities. These methods include seed-based searches, co-clustering, and scalable minimum-description formulations.

Local Density Clustering: Directed local-density clustering maximizes the product f(C) = δℓ(C) · δr(C) for a subgraph containing a specified seed node.The search expands locally around the seed using internal and external directed degrees.
Information-theoretic methods: Isomap identifies directed pattern-based clusters by combining random walks with compression of information-flow descriptions.The reviewed results state that it detects clusters of flow patterns induced by directed edges.
Information-theoretic methods: Information-theoretic methods partition nodes to minimize the description length of a random walk using a two-level code for communities and nodes.Shorter descriptions arise when the walk crosses between communities infrequently.
Co-clustering: AutoPart co-clusters adjacency matrices into rectangular homogeneous blocks whose compression cost evaluates candidate structures.Rows and columns are reordered so blocks represent groups with high or low connection density.
Co-clustering: AutoPart treats community detection as co-clustering, determines the number of clusters automatically with MDL, and scales linearly with the number of edges.The cited description presents these as the algorithm’s main features.

Community Structure Exploration and Evaluation Methods

Alternative directed-community methods target structures that ordinary density-based clustering can miss, including influential-node kernels, reciprocal tendencies, bounded-path components, directed cores, and game-theoretic groupings.

Community Kernels: Community-kernel methods separate influential nodes into kernels and associate auxiliary communities with their followers or related nodes.This addresses near-bipartite social-network structure that density-based methods may partition incorrectly.
Community Kernels: Greedy kernel detection and WeBA provide approximation guarantees for a computationally difficult problem, and both scale linearly with network size.The methods are designed for large-scale social networks.
Mutuality-Tendency Aware Community Detection: Mutuality-aware spectral clustering maximizes reciprocal tendencies within clusters while minimizing them across clusters.In the illustrated case, it keeps most mutual connections within the same group, unlike traditional spectral clustering.
Connected Components based Method: Strongly p-connected components require directed paths of length at most p in both directions between every node pair, followed by merging to adjust community size.This provides a stricter connected-component notion for community exploration.
Core-based Community Exploration: Directed core methods extend k-core analysis through (k, ℓ)-D-cores, while other approaches formulate group membership as a non-cooperative game.D-cores measure directed cohesion; game-theoretic methods model competing membership hypotheses.

Extracting the Best Clusters on Large Scale Directed Networks

Large directed networks may require methods that extract only their strongest clusters rather than enumerate and rank every possible cluster. TopGC addresses this need by finding variable-size, clique-like clusters with linear running time in network size and scalable similarity search.

Motivation: As networks grow, clustering complexity makes scalability important, while applications often need only the strongest or highest-quality clusters.Enumerating all clusters and retaining only the top ones can waste time and space.
TopGC: TopGC finds the best connected, clique-like clusters in directed and undirected networks, allowing variable-size clusters.Its design targets applications that require only a subset of strongly connected clusters.
TopGC: TopGC runs in linear time with respect to network size.The passage reports linear running time for networks of variable-size clusters.
TopGC: The algorithm uses neighbor-set overlap as a similarity signal because nodes with similar neighbors generally belong to the same cluster.Clique nodes provide the motivating case: their neighbor sets, excluding themselves, match exactly.
TopGC: Locality Sensitive Hashing accelerates the search for nodes with similar neighborhoods, with a modified version reducing memory consumption.The method is designed to retain only the best clusters and is described as highly parallelizable for MapReduce.

Dynamic Networks

Dynamic directed-network clustering must discover communities in evolving snapshots and detect when those communities change. The survey also distinguishes density-based clusters from pattern-based structures and notes that many methods combine both notions.

Dynamic Networks: Dynamic networks evolve through node and edge additions or deletions, so community analysis must account for graph streams rather than isolated static graphs.The survey defines a dynamic network as a sequence of graphs G := {G(1), G(2), . . . , G(t), . . .}.
Dynamic Networks: Dynamic community detection has two subtasks: assigning nodes to communities and quantifying or detecting structural changes over time.Change points mark times when a significant change has occurred in the identified community structure.
Dynamic Networks: An incremental procedure can cluster static snapshots and compare partitions across time to identify change points in the graph stream.The comparison requires a similarity measure between partitions, alongside updates when new graph segments arrive.
Dynamic Networks: For dynamic weighted directed networks, one approach combines Random Walks with Restart, local modularity, partition similarity, and partition updates.Random Walks with Restart computes node relevance scores, while local modularity examines partition quality.
Clustering Notions: Density-based clusters require high internal and low external edge density, whereas pattern-based clusters use structural criteria beyond edge density.Pattern-based examples include citation structures and subgraphs with strong information flow.
Clustering Notions: Many directed-network methods identify mixed clusters by combining density with edge-direction, incoming/outgoing similarity, or other structural patterns.Graph symmetrization can allow nodes to cluster together even without a direct edge in the original directed network.

6. Evaluation Metrics and Benchmarking

Evaluating directed-network clustering involves quality measures, comparisons with ground truth or other algorithms, and stability under graph perturbations. The survey emphasizes that directed benchmarks and comparative evaluation remain underdeveloped.

Evaluation Metrics and Benchmarking: Clustering evaluation may compare partitions with known node assignments, benchmark graphs with inherent communities, or quality measures such as directed modularity.Algorithm runtime is also a crucial comparison criterion.
Quality Measures: Quality indices can rank partitions, but their accuracy may not always indicate the most appropriate clustering result and can be biased by the measure used.Comparative studies of quality measures are available for undirected graphs but missing for directed versions.
Benchmarking: Directed-network evaluation remains premature because sufficiently large datasets with known community structure are difficult to obtain and few benchmarks exist.This limits direct comparison against reliable ground truth.
Stability: Stability evaluation tests whether significant clusters remain identifiable after perturbing the input graph.Stability is measured through the operations needed to transform the original clustering into the perturbed result.
Ground-Truth Measures: Ground-truth comparisons can use precision, recall, and an F-measure that matches each produced cluster to the ground-truth cluster maximizing F(Ci, Cj).The average F-measure summarizes the produced clustering over its clusters.
Information-Theoretic Measures: NMI equals one for identical clusterings and zero when the two clusterings totally disagree.The measure is based on mutual information and entropies and can compare assignments without ground-truth data.

7. Real-world Applications on Directed Networks

Directed-network clustering is applied across social, information, technological, biological, and scientific systems. These applications use communities to expose interaction structure, thematic categories, scientific relationships, software modules, and biologically meaningful groups.

Social, Information and Technological Networks: Social-network clustering analyzes nonreciprocal interactions and can reveal structure in systems such as student friendships and large online platforms.A directed student network may encode one student’s indicated liking for another.
Social, Information and Technological Networks: In Web and Wikipedia networks, nodes represent webpages or lemmas and directed hyperlinks; clustering can identify thematic categories and support recommender systems.The Wikipedia example identifies meaningful categories of lemmas.
Citation Networks: Citation-network clustering studies relationships among scientific papers and can map connections between disciplines.Rosvall and Bergstrom applied a flow-based method to about 6.5 million citations to create a map of scientific disciplines.
Citation Networks: The mapped scientific structure is described as U-shaped, with social sciences and engineering at opposite sides and several fields joining them.Medicine, molecular biology, chemistry, and physics are positioned between those sides.
Technological Networks: Other applications include patent citations for knowledge transfer between technology fields and call graphs for partitioning software into smaller modules.Graph clustering was applied to Java and Cobol programs.
Biological Networks: Biological directed networks include metabolic pathways, gene regulatory networks, and food webs, where clustered groups may have biological meaning.Food-web community structure is linked to robustness under perturbations.

8. Open Problems and Future Research Directions

The survey identifies formal definition, methodological consistency, evaluation, parameterization, scalability, and comparative experimentation as central open problems in directed-network clustering.

Problem Foundations: A formal and precise definition of what constitutes a good cluster or community in directed networks remains the foremost task.The survey cautions that no single definition may fit all application needs.
Problem Foundations: Directed clustering methods are not fully consistent because they adopt diverse requirements and cannot straightforwardly extend undirected concepts such as density.Even direct generalizations from undirected clustering may not transfer cleanly to directed networks.
Algorithm Design: Future algorithms should address parameter sensitivity, scalability, and evaluation while minimizing user-specified parameters and computational complexity.Approximation, heuristics, distributed computing, and MapReduce are identified as possible responses to scalability constraints.
Scalability: Extending directed-network clustering to massive graphs, including billion-node networks, is an important direction for distributed methods.The survey specifically highlights MapReduce as a framework for studying very large networks.
Evaluation: Evaluation remains difficult when ground-truth community structure is unavailable, motivating reliable benchmark directed graphs and stronger comparative studies.The survey calls for experiments comparing algorithms across directed-network types and scales.

Towards Data-driven and Application-driven Approaches

The survey points toward data-driven, application-driven, local, dynamic, and richer-network approaches for directed community detection. Its review organizes existing methods and evaluation tools while identifying domain-specific extensions as future work.

Data-driven Approaches: Data-driven algorithms can exploit structural patterns discovered in directed-network data during community-detection design.The approach studies network structure first and incorporates relevant observations into algorithm construction.
Application-driven Approaches: Application-driven methods should adapt clustering algorithms to the differing features of social, biological, economic, and neuroscience networks.The survey describes directed-network clustering as application-oriented and domain-specific.
Local Community Detection: Local definitions and algorithms could evaluate subgraphs instead of partitioning entire graphs, supporting exploration of large or weakly structured networks.The survey presents local methods as potentially useful when no clear community structure exists.
Richer Network Settings: Future work should extend directed clustering to signed, probabilistic, heterogeneous, and dynamic networks with richer edge, node, or temporal information.These settings include positive or negative interactions, uncertain edge existence, multiple node and link types, and evolving graphs.
Survey Synthesis: The survey provides a comprehensive review organized by four methodological categories and a supplementary classification based on cluster type.It also presents evaluation tools, applications, and future research directions for directed-network clustering.