Finding community structure in very large networks

@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}, keywords = {methodology, network}, month = {August}, posted-at = {2005-12-06 01:46:48}, priority = {3}, title = {Finding community structure in very large networks}, url = {http://arxiv.org/abs/cond-mat/0408187}, year = {2004} }

TY - ELEC ID - citeulike:95936 L3 - citeulike-article-id:95936 TI - Finding community structure in very large networks N2 - 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. KW - methodology KW - network AU - Clauset, Aaron AU - Newman, MEJ AU - Moore, Cristopher PY - 2004/08/30/ UR - http://arxiv.org/abs/cond-mat/0408187 ER -