Finding local community structure in networks.

By Aaron Clauset. Physical review. E, Statistical, nonlinear, and soft matter physics, 2005

812 citations recorded by the source corpus.

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(k2d) 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.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/4ab328d8a9e7e85661c762bd36a66ba70bb5ec5e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

A classification for community discovery methods in complex networks (2011, background): “[19], an extension of modularity for directed networks [20] and some heuristic strategies developed to tackle the NPcompleteness characteristics of the modularity maximization problem (the external optimization [21], the local modularity computation [22] and the very efficient modularity unfolding [”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “Other recent work that has focused on developing local and/or near-linear time heuristics for community detection include [49, 158, 47, 21, 137].”
Community detection in networks: A user guide (2016, methodology): “They can be extended to a variety of contexts, e. g., directed networks (Peixoto, 2014), networks with weighted edges (Aicher et al., 2014), with overlapping communities (Airoldi et al., 2008), with multiple layers (Peixoto, 2015a), with annotations (Hric et al., 2016; Newman and Clauset, 2016).”
Detecting highly overlapping community structure by greedy clique expansion (2010, background): “[10, 14, 15, 17] This technique can be varied, but can be generally summarized in the following steps:”
Consensus clustering in complex networks (2012, background): “The most typical scenario is when the seeked partition or individual clusters correspond to extrema of a cost functio”
Statistical properties of community structure in large social and information networks (2008, background): “Other recent work that has focused on developing local and/or near-linear time heuristics for community detection include [48, 155, 46, 21, 134].”
A survey of community search over big graphs (2019, background): “[40] defined the local modularity of C as f(C)=I/T , where I is the number of edges with no end vertex in U , and T is the number of edges with at least one end vertex in B.”
Distributed community detection in delay tolerant networks (2007, background): “Clauset [2] deﬁnes a measure of local community structure and an algorithm that infers the hierarchy of communities that encloses a given vertex by exploring the graph one vertex at a time.”
Empirical comparison of algorithms for network community detection (2010, background): “Seco nd, other recent work has also focused on developing local and/o r earlinear time heuristics for community detection include [7] .”
Finding community structure in networks using the eigenvectors of matrices. (2006, methodology): “In this paper we focus on one approach to community detection that has proven particularly eﬀective, the optimization of the beneﬁt function known as “modu-larity” over the possible divisions of a network.”
A socio-aware overlay for publish/subscribe communication in delay tolerant networks (2007, background): “In[6], Clauset defines a measure of local community structure and an algorithm that infers the hierarchy of communities that encloses a given vertex by exploring the graph one vertex at a time.”
Modularity-maximizing graph communities via mathematical programming (2007, background): “…that modularity-maximizing clusterings often identify interesting community structure in real networks, and focused on diﬀerent heuristics for obtaining such clustering [8, 9, 11, 36–38 , Remark 1 It should be noted that graph communities found by maximizing modularity should be judged carefully.”