dorsal/arxiv
View SchemaComputing communities in large networks using random walks (long version)
| Authors | Pascal Pons, Matthieu Latapy |
|---|---|
| Categories | |
| ArXiv ID | physics/0512106 |
| URL | https://arxiv.org/abs/physics/0512106 |
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.
{
"annotation_id": "6e8e3ee0-b609-4e66-842c-c4155553f56a",
"date_created": "2026-03-02T18:01:03.350000Z",
"date_modified": "2026-03-02T18:01:03.350000Z",
"file_hash": "880f2936b6a22451c113b7b085396055d9c5e31c06397759f7fc968d3fb6ae63",
"private": false,
"record": {
"abstract": "Dense subgraphs of sparse graphs (communities), which appear in most\nreal-world complex networks, play an important role in many contexts. Computing\nthem however is generally expensive. We propose here a measure of similarities\nbetween vertices based on random walks which has several important advantages:\nit captures well the community structure in a network, it can be computed\nefficiently, and it can be used in an agglomerative algorithm to compute\nefficiently the community structure of a network. We propose such an algorithm,\ncalled Walktrap, which runs in time O(mn^2) and space O(n^2) in the worst case,\nand in time O(n^2log n) and space O(n^2) in most real-world cases (n and m are\nrespectively the number of vertices and edges in the input graph). Extensive\ncomparison tests show that our algorithm surpasses previously proposed ones\nconcerning the quality of the obtained community structures and that it stands\namong the best ones concerning the running time.",
"arxiv_id": "physics/0512106",
"authors": [
"Pascal Pons",
"Matthieu Latapy"
],
"categories": [
"physics.soc-ph",
"cond-mat.dis-nn",
"cond-mat.stat-mech"
],
"title": "Computing communities in large networks using random walks (long version)",
"url": "https://arxiv.org/abs/physics/0512106"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "2806e832-9ea7-48b9-a7e4-d0a5bd1c4bb3",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}