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.
Description
Finding community structure in very large networks
%0 Journal Article
%1 Clauset2004
%A Clauset, Aaron
%A Newman, M. E. J.
%A Moore, Cristopher
%D 2004
%K algorithm community_detection imported networks
%T Finding community structure in very large networks
%U http://arxiv.org/abs/cond-mat/0408187
%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^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.
@article{Clauset2004,
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.
},
added-at = {2009-08-18T18:31:46.000+0200},
author = {Clauset, Aaron and Newman, M. E. J. and Moore, Cristopher},
biburl = {https://www.bibsonomy.org/bibtex/23afdce9296ad1969c9eb53238271f598/nic},
description = {Finding community structure in very large networks},
interhash = {2c68e3c981a00380692a3b0b661d7cfd},
intrahash = {3afdce9296ad1969c9eb53238271f598},
keywords = {algorithm community_detection imported networks},
note = {cite arxiv:cond-mat/0408187
},
timestamp = {2009-08-18T18:31:46.000+0200},
title = {Finding community structure in very large networks},
url = {http://arxiv.org/abs/cond-mat/0408187},
year = 2004
}