Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks - art.. No:066111. Physical Review E 7006 (6 PT2) dECEMBER 2004

[Eugene Garfield]

BLOCK, COPY, AND PASTE FULL URL
Full text available at :
http://scitation.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=PLEEE8000070000006066111000001&idtype=cvips

Aaron Clauset       :  aaron at cs.unm.edu
MEJ Newman          :  mejn at umich.edu
Christopher Moore   :  moore at cs.unm.edu

TITLE:          Finding community structure in very large networks - art.
                no. 066111 (Article, English)
AUTHOR:         Clauset, A; Newman, MEJ; Moore, C
SOURCE:         PHYSICAL REVIEW E 7006 (6 PT 2). DEC 2004.
                p.NIL_1379-NIL_1384 AMERICAN PHYSICAL SOC, COLLEGE PK

SEARCH TERM(S):  PRICE DJD  rauth; PHYS REV E  source_abbrev_20

KEYWORDS+:       COMPLEX NETWORKS; INTERNET; GRAPHS; WEB

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(md log n) where d is the depth
of the dendrogram describing the community structure. Many real-world
networks are sparse and hierarchical, with msimilar ton and dsimilar
tolog 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 on-line
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 2x10(6) 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 ADDRESS: A Clauset, Univ New Mexico, Dept Comp Sci, Albuquerque, NM
                87131 USA

CITED REFERENCES:
CR ALBERT R, 1999, NATURE, V401, P130
   ALBERT R, 2002, REV MOD PHYS, V74, P47
   ARENAS A, 2004, EUR PHYS J B, V38, P373
   BOGUNA M, CONDMAT0309263
   CORMEN TH, 2001, INTRO ALGORITHMS
   DOROGOVTSEV SN, 2002, ADV PHYS, V51, P1079
   DUNNE JA, 2002, P NATL ACAD SCI USA, V99, P12917
   FALOUTSOS M, 1999, COMP COMM R, V29, P251
   FIEDLER M, 1973, CZECH MATH J, V23, P298
   FLAKE GW, 2002, IEEE COMPUT, V35, P66
   GASTNER MT, 2004, P NATL ACAD SCI USA, V101, P7499
   GIRVAN M, 2002, P NATL ACAD SCI USA, V99, P7821
   GLEISER PM, 2003, ADV COMPLEX SYST, V6, P565
   GUIMERA R, 2003, PHYS REV E 2, V68
   HOLME P, 2003, BIOINFORMATICS, V19, P532
   HOLME P, 2003, P 3 WORKSH COMP BIOC, P3
   ITO T, 2001, P NATL ACAD SCI USA, V98, P4569
   KAUFFMAN SA, 1969, J THEOR BIOL, V22, P437
   KERNIGHAN BW, 1970, BELL SYST TECH J, V49, P291
   KLEINBERG J, 1999, LECT NOTES COMPUTER, V1627, P1
   NEWMAN MEJ, CONDMAT0407503
   NEWMAN MEJ, 2003, SIAM REV, V45, P167
   NEWMAN MEJ, 2004, EUR PHYS J B, V38, P321
   NEWMAN MEJ, 2004, JPHYS REV E, V69, P66133
   NEWMAN MEJ, 2004, PHYS REV E 2, V69
   POTHEN A, 1990, SIAM J MATRIX ANAL A, V11, P430
   PRICE DJD, 1965, SCIENCE, V149, P510
   RADICCHI F, 2004, P NATL ACAD SCI USA, V101, P2658
   REDNER S, 1998, EUR PHYS J B, V4, P131
   SCOTT J, 2000, SOCIAL NETWORK ANAL
   STROGATZ SH, 2001, NATURE, V410, P268
   TYLER JR, 2003, P 1 INT C COMM TECHN
   WASSERMAN S, 1994, SOCIAL NETWORK ANAL
   WATTS DJ, 1998, NATURE, V393, P440
   WILKINSON DM, 2004, P NATL ACAD SCI U S1, V101, P5241
   WU F, 2004, EUR PHYS J B, V38, P331