Finding local community structure in networks

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(d*k^2) 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 this technique compares favorably to algorithms that require global knowledge. We also use this algorithm to extract meaningful local clustering information in the large recommender network of an online retailer and show the existence of mesoscopic structure.

7 pages, 6 figures

References in corpus (4)

• Finding community structure in very large networks
• Analysis of weighted networks
• A Local Method for Detecting Communities
• Citation Statistics From More Than a Century of Physical Review

Cited by in corpus (82)

• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Characterization of complex networks: A survey of measurements
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• The performance of modularity maximization in practical contexts
• Consensus clustering in complex networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Modularity-Maximizing Network Communities via Mathematical Programming
• Detecting highly overlapping community structure by greedy clique expansion
• Network Analysis of Particles and Grains
• Local resolution-limit-free Potts model for community detection
• Evaluating Local Community Methods in Networks
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Community extraction for social networks
• International collaboration clusters in Africa
• Common neighbours and the local-community-paradigm for link prediction in bipartite networks
• Computing communities in large networks using random walks (long version)
• Empirical Comparison of Algorithms for Network Community Detection
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Community Detecting By Signaling on Complex Networks
• Spectral tripartitioning of networks
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Communities and bottlenecks: Trees and treelike networks have high modularity
• A Survey on Theoretical Advances of Community Detection in Networks
• Communities in Networks
• Jerarca: Efficient Analysis of Complex Networks Using Hierarchical Clustering
• Measuring Significance of Community Structure in Complex Networks
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Community extraction in multilayer networks with heterogeneous community structure
• Efficient local behavioral change strategies to reduce the spread of epidemics in networks
• Memetic search for overlapping topics based on a local evaluation of link communities
• Detecting Community Structure in Dynamic Social Networks Using the Concept of Leadership
• Discovering Network Structure Beyond Communities
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Seeding for pervasively overlapping communities
• Local degree blocking model for link prediction in complex networks
• Literature Survey on Interplay of Topics, Information Diffusion and Connections on Social Networks
• The blessing of transitivity in sparse and stochastic networks
• Local community extraction in directed networks
• Communities and classes in symmetric fractals
• Triangles to Capture Social Cohesion
• Community Detection Across Multiple Social Networks based on Overlapping Users
• A Survey of Community Search Over Big Graphs
• Community Detection using a Measure of Global Influence
• Scalable Spectral Algorithms for Community Detection in Directed Networks
• Fast Community Identification by Hierarchical Growth
• Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning
• Multiscale Evolutionary Perturbation Attack on Community Detection
• Criterions for locally dense subgraphs
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Stochastic blockmodels for exchangeable collections of networks
• Local multiresolution order in community detection
• Local Hypergraph Clustering using Capacity Releasing Diffusion
• Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
• Uncovering migration systems through spatio-temporal tensor co-clustering
• Improving PageRank for Local Community Detection
• The Atlas for the Aspiring Network Scientist
• Community-detection cellular automata with local and long-range connectivity
• Region Detection in Markov Random Fields: Gaussian Case
• Metrics for Community Analysis: A Survey
• Fast community structure local uncovering by independent vertex-centred process
• Detecting Overlapping Link Communities by Finding Local Minima of a Cost Function with a Memetic Algorithm. Part 1: Problem and Method
• Evaluating for Diversity in Question Generation over Text
• Evaluating Overlapping Communities with the Conductance of their Boundary Nodes
• Using Model-based Overlapping Seed Expansion to detect highly overlapping community structure
• Inferring Local Structure from Pairwise Correlations
• Extracting Hidden Groups and their Structure from Streaming Interaction Data
• Real-Time Community Detection in Large Social Networks on a Laptop
• Homophyly Networks -- A Structural Theory of Networks
• Evaluating community structure in large network with random walks
• A New Benchmark For Evaluation Of Graph-Theoretic Algorithms
• A baseline for content-based blog classification
• Uncovering the Local Hidden Community Structure in Social Networks
• Node-centric community detection in multilayer networks with layer-coverage diversification bias
• Sparse Nonnegative Matrix Factorization for Multiple Local Community Detection
• Algorithm Engineering for Cut Problems
• Application of a cognitive-inspired algorithm for detecting communities in mobility networks
• Overlapping Community Detection by Local Decentralised Vertex-centred Process
• Community Structures Are Definable in Networks: A Structural Theory of Networks
• Structure Amplification on Multi-layer Stochastic Block Models