Community structure in social and biological networks

DOI10.1073/PNAS.122653799zbMATH Open1032.91716arXivcond-mat/0112110OpenAlexW1971421925WikidataQ24534298 ScholiaQ24534298MaRDI QIDQ4547718FDOQ4547718

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)

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.

Full work available at URL: https://arxiv.org/abs/cond-mat/0112110

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

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30)

Cites Work

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

Cited In (only showing first 100 items - show all)

• Large dicliques in a directed inhomogeneous random graph
• Computing communities in complex networks using the Dirichlet processing Gaussian mixture model with spectral clustering
• Networks beyond pairwise interactions: structure and dynamics
• Edge intensity-based community measurement in complex networks
• Randomly stopped extreme Zipf extensions
• Distributed Community Detection in Dynamic Graphs
• Directed Community Detection With Network Embedding
• ON SUCCINCT REPRESENTATION OF KNOWLEDGE COMMUNITY TAXONOMIES WITH FORMAL CONCEPT ANALYSIS
• A spectral clustering-based framework for detecting community structures in complex networks
• Detecting community structure: from parsimony to weighted parsimony
• On the connectivity and the diameter of betweenness-uniform graphs
• Modularity density of network community divisions
• Statistical physics approaches to the complex Earth system
• Bounds and relations involving adjusted centrality of the vertices of a tree
• A measure for a balanced workload and its extremal values
• Network robustness to targeted attacks. The interplay of expansibility and degree distribution
• Fundamentals of spreading processes in single and multilayer complex networks
• An algorithm J-SC of detecting communities in complex networks
• Cluster synchronisation of directed complex dynamical networks with nonidentical nodes via pinning control
• Bayesian community detection
• Configuring random graph models with fixed degree sequences
• The information transmission in community networks
• Analysis of attachment models for directory and file trees
• Structural and functional clusters of complex brain networks
• On betweenness-uniform graphs.
• The k-Dense Method to Extract Communities from Complex Networks
• Core-periphery structure in networks (revisited)
• Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
• Evidential identification of influential nodes in network of networks
• EPIDEMIOLOGY MODEL ON SHORTCUT AND SMALL WORLD NETWORKS
• The community structure of human cellular signaling network
• Identifying the parametric occurrence of multiple steady states for some biological networks
• Weighted community detection and data clustering using message passing
• A min-cut approach to functional regionalization, with a case study of the Italian local labour market areas
• Structure in networks
• On the robustness of the generalized fused Lasso to prior specifications
• Synchronization-based scalability of complex clustered networks
• Bootstrapping on undirected binary networks via statistical mechanics
• Detection of structurally homogeneous subsets in graphs
• Detecting communities in networks using a Bayesian nonparametric method
• A divisive spectral method for network community detection
• Minimal paths between communities induced by geographical networks
• Co-controllability of drug-disease-gene network
• Defining and identifying cograph communities in complex networks
• Min-max communities in graphs: complexity and computational properties
• Fast layout computation of clustered networks: algorithmic advances and experimental analysis
• Vertex nomination schemes for membership prediction
• An algorithm for detecting communities in social networks
• Reset strategy for consensus in networks of clusters
• On the controllability of Corona product network
• Dominating communities for hierarchical control of complex networks
• Community detection with the weighted parsimony criterion
• The critical point of \(k\)-clique percolation in the Erdős-Rényi graph
• An order-based algorithm for minimum dominating set with application in graph mining
• Overlapping community detection in heterogeneous social networks via the user model
• An improved spectral clustering community detection algorithm based on probability matrix
• Quantitative measure for community detection in weighted networks
• Network community detection using modularity density measures
• A signal-diffusion-based spectral clustering method for community detection
• Controllability and modularity of complex networks
• Modeling transitivity in local structure graph models
• Toward optimal community detection: from trees to general weighted networks
• Social network community detection using agglomerative spectral clustering
• Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges
• SOCIAL DILEMMAS AND COOPERATION IN COMPLEX NETWORKS
• Using Community Structure to Detect Relevant Learnt Clauses
• DeCODe: a community-based algorithm for generating high-quality decompositions of optimization problems
• ChordLink: a new hybrid visualization model
• Community detection and stochastic block models: recent developments
• Consistency of community detection in networks under degree-corrected stochastic block models
• Community discovery using nonnegative matrix factorization
• Classification and estimation in the stochastic blockmodel based on the empirical degrees
• Model selection in overlapping stochastic block models
• A review of dynamic network models with latent variables
• \(k\)-core architecture and \(k\)-core percolation on complex networks
• A new modularity measure for fuzzy community detection problems based on overlap and grouping functions
• Consistency of spectral clustering in stochastic block models
• Uncovering space-independent communities in spatial networks
• Complex networks: structure and dynamics
• A branch-and-bound approach for maximum quasi-cliques
• Optimal adaptivity of signed-polygon statistics for network testing
• Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex 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
• Mining hidden links in social networks to achieve equilibrium
• The random subgraph model for the analysis of an ecclesiastical network in Merovingian Gaul
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Spectral redemption in clustering sparse networks
• Mathematical programming formulations for the collapsed k-core problem
• Link removal for the control of stochastically evolving epidemics over networks: a comparison of approaches
• Extracting backbones from weighted complex networks with incomplete information
• Fractional integral transform and application
• Modeling gene networks in \textit{Saccharomyces cerevisiae} based on gene expression profiles
• Impact of regularization on spectral clustering
• Community detection in dense random networks
• Mixture models and exploratory analysis in networks
• SAT-based models for overlapping community detection in networks
• Modelling development of epidemics with dynamic small-world networks
• A sub-optimal consensus design for multi-agent systems based on hierarchical LQR
• Efficient algorithms for game-theoretic betweenness centrality

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)