@article{clauset2004, abstract = {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(mdlog 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 log2 n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web-site of a large online retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400 000 vertices and 2 million edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.}, author = {Clauset, Aaron and Newman, M. E. J. and and Cristopher Moore}, doi = {10.1103/PhysRevE.70.066111}, interhash = {69be2649d5ff3e66ad7dfadac4a1841f}, intrahash = {458e03efb1ef50a5338907bb58c426f6}, journal = {Physical Review E}, pages = {1-- 6}, title = {Finding community structure in very large networks}, year = 2004 } @article{clauset-2004-70, author = {Clauset, Aaron and Newman, M. E. J. and Moore, Cristopher}, interhash = {2c68e3c981a00380692a3b0b661d7cfd}, intrahash = {0ea285bfc0f5a46ffec8a213e5133ba6}, journal = {Physical Review E}, pages = 066111, title = {Finding community structure in very large networks}, url = {http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0408187}, volume = 70, year = 2004 } @article{clauset-2004-70, author = {Clauset, Aaron and Newman, M.E.J. and Moore, Cristopher}, interhash = {2c68e3c981a00380692a3b0b661d7cfd}, intrahash = {a35d69f1d41a6cdd0632c5e1cadb4d44}, journal = {Physical Review E}, pages = 066111, title = {Finding community structure in very large networks}, url = {http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0408187}, volume = 70, year = 2004 } @misc{citeulike:95936, 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^2 n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web-site of a large online retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400,000 vertices and 2 million edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.}, author = {Clauset, Aaron and Newman, M. E. J. and Moore, Cristopher}, citeulike-article-id = {95936}, eprint = {cond-mat/0408187}, interhash = {2c68e3c981a00380692a3b0b661d7cfd}, intrahash = {f9a12630a6d31d576ea5222219a4cf0b}, month = {August}, priority = {0}, title = {Finding community structure in very large networks}, url = {http://arxiv.org/abs/cond-mat/0408187}, year = 2004 }