Clauset A. "Finding local community structure in networks" Physical Review E 72(2): Art. No:026132 Part 2, August 2005.

[Eugene Garfield]

A. Clauset : E-mail Addresses: aaron at cs.unm.edu

Title: Finding local community structure in networks

Author(s): Clauset A

Source: PHYSICAL REVIEW E 72 (2): Art. No. 026132 Part 2, AUG 2005

Document Type: Article
Language: English
Cited References: 27      Times Cited: 1

Abstract:
Although the inference of global community structure in networks has
recently become a topic of great interest in the physics community, all
such algorithms require that the graph be completely known. Here, we define
both a measure of local community structure and an algorithm that infers
the hierarchy of communities that enclose a given vertex by exploring the
graph one vertex at a time. This algorithm runs in time O(k(2)d) for
general graphs when d is the mean degree and k is the number of vertices to
be explored. For graphs where exploring a new vertex is time consuming, the
running time is linear, O(k). We show that on computer-generated graphs the
average behavior of this technique approximates that of algorithms that
require global knowledge. As an application, we use this algorithm to
extract meaningful local clustering information in the large recommender
network of an online retailer.

KeyWords Plus: COMPLEX NETWORKS; GRAPHS
Addresses: Clauset A (reprint author), Univ New Mexico, Dept Comp Sci,
Albuquerque, NM 87131 USA
Univ New Mexico, Dept Comp Sci, Albuquerque, NM 87131 USA

E-mail Addresses: aaron at cs.unm.edu

Publisher: AMERICAN PHYSICAL SOC, ONE PHYSICS ELLIPSE, COLLEGE PK, MD 20740-
3844 USA
Subject Category: PHYSICS, FLUIDS & PLASMAS; PHYSICS, MATHEMATICAL
IDS Number: 960BB
ISSN: 1539-3755


CITED REFERENCES:
ALBERT R
Statistical mechanics of complex networks
REVIEWS OF MODERN PHYSICS 74 : 47 2002

 BAGROW JP
CONDMAT0412482

 BOLLOBAS B
RANDOM GRAPHS : 1985

 CLAUSET A
Finding community structure in very large networks
PHYSICAL REVIEW E 70 : Art. No. 066111 2004

 DOROGOVTSEV SN
Evolution of networks
ADVANCES IN PHYSICS 51 : 1079 2002

 FALOUTSOS M
title not available
COMP COMM R 29 : 251 1999

 FIEDLER M
ALGEBRAIC CONNECTIVITY OF GRAPHS
CZECHOSLOVAK MATHEMATICAL JOURNAL 23 : 298 1973

 FLAKE GW
IEEE COMPUT 35 : 66 2002

 GIRVAN M
Community structure in social and biological networks
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF
AMERICA 99 : 7821 2002

 ITO T
A comprehensive two-hybrid analysis to explore the yeast protein interactome
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF
AMERICA 98 : 4569 2001

 KERNIGHAN BW
BELL SYST TECH J 49 : 291 1970

 KLEINBERG J
LECT NOTES COMPUTER 1627 : 1 1999

 NEWMAN MEJ
Detecting community structure in networks
EUROPEAN PHYSICAL JOURNAL B 38 : 321 2004

 NEWMAN MEJ
Analysis of weighted networks
PHYSICAL REVIEW E 70 : Art. No. 056131 2004

 NEWMAN MEJ
Finding and evaluating community structure in networks
PHYSICAL REVIEW E 69 : Art. No. 026113 2004

 NEWMAN MEJ
Fast algorithm for detecting community structure in networks
PHYSICAL REVIEW E 69 : Art. No. 066133 2004

 NEWMAN MEJ
Why social networks are different from other types of networks
PHYSICAL REVIEW E 68 : Art. No. 036122 2003

 NEWMAN MEJ
Mixing patterns in networks
PHYSICAL REVIEW E 67 : Art. No. 026126 2003

 NEWMAN MEJ
The structure and function of complex networks
SIAM REVIEW 45 : 167 2003

 POTHEN A
PARTITIONING SPARSE MATRICES WITH EIGENVECTORS OF GRAPHS
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 11 : 430 1990

 PRICE DJD
NETWORKS OF SCIENTIFIC PAPERS
SCIENCE 149 : 510 1965

 RADICCHI F
Defining and identifying communities in networks
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF
AMERICA 101 : 2658 2004

 REDNER S
PHYSICS0407137
 SCOTT J
SOCIAL NETWORK ANAL : 2000

 STROGATZ SH
Exploring complex networks
NATURE 410 : 268 2001

 WASSERMAN S
SOCIAL NETWORK ANAL : 1994

 WU F
Finding communities in linear time: a physics approach
EUROPEAN PHYSICAL JOURNAL B 38 : 331 2004