Computing communities in large networks using random walks (long version)

Abstract

Dense subgraphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Computing them however is generally expensive. We propose here a measure of similarities between vertices based on random walks which has several important advantages: it captures well the community structure in a network, it can be computed efficiently, and it can be used in an agglomerative algorithm to compute efficiently the community structure of a network. We propose such an algorithm, called Walktrap, which runs in time O(mn^2) and space O(n^2) in the worst case, and in time O(n^2log n) and space O(n^2) in most real-world cases (n and m are respectively the number of vertices and edges in the input graph). Extensive comparison tests show that our algorithm surpasses previously proposed ones concerning the quality of the obtained community structures and that it stands among the best ones concerning the running time.

20 pages, 5 figures, long version

References in corpus (20)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Natural Scales in Geographical Patterns
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical organization of modularity in metabolic networks
• Defining and identifying communities in networks
• Community detection in complex networks using Extremal Optimization
• Finding local community structure in networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Finding Communities in Linear Time: A Physics Approach
• A Method to Find Community Structures Based on Information Centrality
• A Local Method for Detecting Communities
• Diffusion on Complex Networks : A way to probe their large scale topological structures
• Coarse grains: the emergence of space and order
• Hub-Based Community Finding

Cited by in corpus (9)

• Towards realistic artificial benchmark for community detection algorithms evaluation
• SEMgraph: An R Package for Causal Network Analysis of High-Throughput Data with Structural Equation Models
• On converting community detection algorithms for fuzzy graphs in Neo4j
• Commonsense Reasoning and Large Network Analysis: A Computational Study of ConceptNet 4
• Comparison and Benchmark of Graph Clustering Algorithms
• Community Detection Clustering via Gumbel Softmax
• Weighted Graph Nodes Clustering via Gumbel Softmax
• Simplification of networks via conservation of path diversity and minimisation of the search information
• Revisiting Causality Inference in Memory-less Transition Networks