Community structure in social and biological networks

DOI10.1073/PNAS.122653799MaRDI QIDQ4547718zbMATH OpenOpenAlexWikidataFDO

Authors Michelle Girvan, M. E. J. Newman

Publication date 11 September 2002

Published in Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0112110, http://www.pnas.org/content/vol99/issue12/#APPLIED_MATHEMATICS

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30)

Abstract: A number of recent studies have focused on the statistical properties of networked systems such as social networks and the World-Wide Web. Researchers have concentrated particularly on a few properties which seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this paper, we highlight another property which is found in many networks, the property of community structure, in which network nodes are joined together in tightly-knit groups between which there are only looser connections. We propose a new method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer generated and real-world graphs whose community structure is already known, and find that it detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well-known - a collaboration network and a food web - and find that it detects significant and informative community divisions in both cases.

Recommendations

• Fast unfolding of communities in large networks
• Detecting network communities: a new systematic and efficient algorithm
• Mixing patterns and community structure in networks
• Algorithms and Models for the Web-Graph
• Community discovery algorithms: an overview

Cites work

• A new status index derived from sociometric analysis
• Collective dynamics of `small-world' networks
• Emergence of Scaling in Random Networks
• Exploring complex networks

Cited in

(only showing first 100 items - show all)

• Finding community structure in spatial maritime shipping networks
• scientific article; zbMATH DE number 7415085 (Why is no real title available?)
• Mixing patterns and community structure in networks
• DeCODe: a community-based algorithm for generating high-quality decompositions of optimization problems
• SAT-based models for overlapping community detection in networks
• Classification and estimation in the stochastic blockmodel based on the empirical degrees
• Community detection based on network communicability
• Modelling development of epidemics with dynamic small-world networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Graph clustering
• Pseudo-likelihood methods for community detection in large sparse networks
• Improved Bayesian inference for the stochastic block model with application to large networks
• The dynamic random subgraph model for the clustering of evolving networks
• scientific article; zbMATH DE number 7626732 (Why is no real title available?)
• \(k\)-core architecture and \(k\)-core percolation on complex networks
• FAST COMMUNITY IDENTIFICATION BY HIERARCHICAL GROWTH
• The implications of network structure for epidemic dynamics
• A new modularity measure for fuzzy community detection problems based on overlap and grouping functions
• Detecting Community Structure by Network Vectorization
• SOCIAL DILEMMAS AND COOPERATION IN COMPLEX NETWORKS
• A multiscale community blockmodel for network exploration
• Improvements on SCORE, especially for weak signals
• An individual-based approach to SIR epidemics in contact networks
• Impacts of clustering on interacting epidemics
• Fast unfolding of communities in large networks
• The \(\sigma\) law of evolutionary dynamics in community-structured population
• Predicting missing links via local information
• Reconstruction and estimation in the planted partition model
• \textsf{SATGraf}: visualizing the evolution of SAT formula structure in solvers
• Detecting communities and their evolutions in dynamic social networks -- a Bayesian approach
• Consistency of spectral clustering in stochastic block models
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• A sub-optimal consensus design for multi-agent systems based on hierarchical LQR
• Fast and accurate determination of modularity and its effect size
• Review of statistical network analysis: models, algorithms, and software
• Model identification of a network as compressing sensing
• Large-scale structure of time evolving citation networks
• Mathematical programming formulations for the collapsed k-core problem
• Estimating the number of communities by spectral methods
• Variational Bayesian inference and complexity control for stochastic block models
• Emergence of segregation in evolving social networks
• Rate-optimal graphon estimation
• Phase diagram and metastability of the Ising model on two coupled networks
• A goodness-of-fit test for stochastic block models
• Model selection in overlapping stochastic block models
• Spectral redemption in clustering sparse networks
• A branch-and-bound approach for maximum quasi-cliques
• Link removal for the control of stochastically evolving epidemics over networks: a comparison of approaches
• Model selection and clustering in stochastic block models based on the exact integrated complete data likelihood
• The structure of scientific collaboration networks
• Extracting backbones from weighted complex networks with incomplete information
• Fractional integral transform and application
• Mining blackhole and volcano patterns in directed graphs: a general approach
• Modeling gene networks in \textit{Saccharomyces cerevisiae} based on gene expression profiles
• Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication
• What's in a crowd? Analysis of face-to-face behavioral networks
• ChordLink: a new hybrid visualization model
• Impact of regularization on spectral clustering
• A graph-theoretic approach on optimizing informed-node selection in multi-agent tracking control
• Community detection and stochastic block models: recent developments
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• Using Community Structure to Detect Relevant Learnt Clauses
• Community detection in dense random networks
• Overlapping stochastic block models with application to the French political blogosphere
• Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks
• Uncovering space-independent communities in spatial networks
• A review of dynamic network models with latent variables
• \(L^1\) group consensus of multi-agent systems with switching topologies and stochastic inputs
• When are networks truly modular?
• Efficient algorithms for game-theoretic betweenness centrality
• A divide-and-link algorithm for hierarchical clustering in networks
• On the hardness of SAT with community structure
• Community structure inspired algorithms for SAT and \#SAT
• Exploiting resolution-based representations for MaxSAT solving
• Uncovering latent structure in valued graphs: a variational approach
• Mining hidden links in social networks to achieve equilibrium
• Optimal adaptivity of signed-polygon statistics for network testing
• Finding overlapping communities in networks by label propagation
• The stochastic topic block model for the clustering of vertices in networks with textual edges
• Complex networks: structure and dynamics
• Mixture models and exploratory analysis in networks
• The random subgraph model for the analysis of an ecclesiastical network in Merovingian Gaul
• Hierarchical Community Detection by Recursive Partitioning
• Consistency of community detection in networks under degree-corrected stochastic block models
• Community detection in sparse random networks
• Community discovery using nonnegative matrix factorization
• Assessing experimentally derived interactions in a small world
• Data mining of social networks represented as graphs
• Assessing the quality of multilevel graph clustering
• Cluster synchronization induced by one-node clusters in networks with asymmetric negative couplings
• The enumeration of vertex induced subgraphs with respect to the number of components
• Local law and Tracy-Widom limit for sparse stochastic block models
• Variational Bayes model averaging for graphon functions and motif frequencies inference in \(W\)-graph models
• Global and local targeted immunization in networks with community structure
• Divisive heuristic for modularity density maximization
• Social structure optimization in team formation
• Social centrality using network hierarchy and community structure
• Mixing local and global information for community detection in large networks
• A locally optimal hierarchical divisive heuristic for bipartite modularity maximization
• Clustering as a dual problem to colouring

This page was built for publication: Community structure in social and biological networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4547718)