Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2004-12-14
in Proceedings of the 20th International Symposium on Computer and Information Sciences, ISCIS'05, LNCS 3733, 284-293 (2005)
Physics
Condensed Matter
Disordered Systems and Neural Networks
15 pages, 4 figures
Scientific paper
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, it works at various scales, and it can be used in an agglomerative algorithm to compute efficiently the community structure of a network. We propose such an algorithm 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). Experimental evaluation shows 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. This is very promising because our algorithm can be improved in several ways, which we sketch at the end of the paper.
Latapy Matthieu
Pons Pascal
No associations
LandOfFree
Computing communities in large networks using random walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing communities in large networks using random walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing communities in large networks using random walks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-226801