Geodesic
Computing Communities in Large Networks Using Random Walks
Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 191-218.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 similarity 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(mn2) and space O(n2) in the worst case, and in time O(n2logn) and space O(n2) 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. 
@article{JGAA_2006_10_2_a4,
     author = {Pascal Pons and Matthieu Latapy},
     title = {Computing {Communities} in {Large} {Networks} {Using} {Random} {Walks}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {191--218},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2006},
     doi = {10.7155/jgaa.00124},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00124/}
}
TY  - JOUR
AU  - Pascal Pons
AU  - Matthieu Latapy
TI  - Computing Communities in Large Networks Using Random Walks
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 191
EP  - 218
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00124/
DO  - 10.7155/jgaa.00124
LA  - en
ID  - JGAA_2006_10_2_a4
ER  - 
%0 Journal Article
%A Pascal Pons
%A Matthieu Latapy
%T Computing Communities in Large Networks Using Random Walks
%J Journal of Graph Algorithms and Applications
%D 2006
%P 191-218
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00124/
%R 10.7155/jgaa.00124
%G en
%F JGAA_2006_10_2_a4
Pascal Pons; Matthieu Latapy. Computing Communities in Large Networks Using Random Walks. Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 191-218. doi : 10.7155/jgaa.00124. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00124/

Cité par Sources :