The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(m d log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m ~ n and d ~ log n, in which case our algorithm runs in essentially linear time, O(n log
Description
Citebase - Finding community structure in very large networks
%0 Journal Article
%1 Clauset04communityLarge
%A Clauset, Aaron
%A Newman, M. E. J.
%A Moore, Cristopher
%D 2004
%J Physical Review E
%K 04 Clauset Newman clustering community discovery graph large networks
%P 066111
%T Finding community structure in very large networks
%U doi:10.1103/PhysRevE.70.066111
%V 70
%X The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(m d log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m ~ n and d ~ log n, in which case our algorithm runs in essentially linear time, O(n log
@article{Clauset04communityLarge,
abstract = {The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(m d log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m ~ n and d ~ log n, in which case our algorithm runs in essentially linear time, O(n log},
added-at = {2008-10-29T18:52:52.000+0100},
author = {Clauset, Aaron and Newman, M. E. J. and Moore, Cristopher},
biburl = {https://www.bibsonomy.org/bibtex/20ea285bfc0f5a46ffec8a213e5133ba6/lee_peck},
description = {Citebase - Finding community structure in very large networks},
interhash = {2c68e3c981a00380692a3b0b661d7cfd},
intrahash = {0ea285bfc0f5a46ffec8a213e5133ba6},
journal = {Physical Review E},
keywords = {04 Clauset Newman clustering community discovery graph large networks},
pages = 066111,
timestamp = {2009-02-02T16:47:03.000+0100},
title = {Finding community structure in very large networks},
url = {doi:10.1103/PhysRevE.70.066111},
volume = 70,
year = 2004
}