A nonparametric view of network models and Newman–Girvan and other modularities
Proceedings of the National Academy of SciencesPublished 23 November 2009Open access
Peter J. Bickel, Aiyou Chen
Citations814
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An attempt at unifying points of view and analyses of these objects coming from the social sciences, statistics, probability and physics communities are presented and the approach to the Newman–Girvan modularity, widely used for “community” detection, is applied.
Abstract
Prompted by the increasing interest in networks in many fields, we present an attempt at unifying points of view and analyses of these objects coming from the social sciences, statistics, probability and physics communities. We apply our approach to the Newman-Girvan modularity, widely used for "community" detection, among others. Our analysis is asymptotic but we show by simulation and application to real examples that the theory is a reasonable guide to practice.
Keywords
Physics and Astronomy
Physical Review EFinding and evaluating community structure in networks
13,892 Citations2004Michelle G. Newman, Michelle Girvan
It is demonstrated that the algorithms proposed are highly effective at discovering community structure in both computer-generated and real-world network data, and can be used to shed light on the sometimes dauntingly complex structure of networked systems.
On Spectral Clustering: Analysis and an algorithm
7,751 Citations2001Andrew Y. Ng, Michael I. Jordan +1 more
A simple spectral clustering algorithm that can be implemented using a few lines of Matlab is presented, and tools from matrix perturbation theory are used to analyze the algorithm, and give conditions under which it can be expected to do well.
Physical Review EFinding community structure in networks using the eigenvectors of matrices
4,801 Citations2006M. E. J. Newman
A modularity matrix plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations, and a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong are proposed.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
NatureFunctional cartography of complex metabolic networks
4,013 Citations2005Roger Guimerà, Luı́s A. Nunes Amaral
A methodology is proposed that can find functional modules in complex networks, and classify nodes into universal roles according to their pattern of intra- and inter-module connections, which yields a ‘cartographic representation’ of complex networks.
Proceedings of the National Academy of SciencesResolution limit in community detection
3,045 Citations2006Santo Fortunato, Marc Barthélemy
It is found that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined.
Social NetworksStochastic blockmodels: First steps
2,855 Citations1983Paul W. Holland, Kathryn Blackmond Laskey +1 more
Estimation techniques are developed for the special case of a single relation social network, with blocks specified a priori, and an extension of the model allows for tendencies toward reciprocation of ties beyond those explained by the partition.
PubMedMixed Membership Stochastic Blockmodels.
1,526 Citations2008Edoardo M. Airoldi, David M. Blei +2 more
This paper describes a latent variable model of such data called the mixed membership stochastic blockmodel, which extends blockmodels for relational data to ones which capture mixed membership latent relational structure, thus providing an object-specific low-dimensional representation.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Dealing With Label Switching in Mixture Models
1,088 Citations2000Matthew Stephens
It is demonstrated that this fails in general to solve the ‘label switching’ problem, and an alternative class of approaches, relabelling algorithms, which arise from attempting to minimize the posterior expected loss under a class of loss functions are described.
Proceedings of the National Academy of SciencesAn information-theoretic framework for resolving community structure in complex networks
822 Citations2007Martin Rosvall, Carl T. Bergstrom
An information-theoretic foundation for the concept of modularity in networks is developed and the modules of which the network is composed are identified by finding an optimal compression of its topology, capitalizing on regularities in its structure.
arXiv (Cornell University)Mixed membership stochastic blockmodels
786 Citations2007Edoardo M. Airoldi, David M. Blei +2 more
Regional conference series in mathematicsComplex Graphs and Networks
702 Citations2006Fan Chung, Linyuan Lü
Journal of ClassificationEstimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure
682 Citations1997Tom A. B. Snijders, Krzysztof Nowicki
A posteriori blockmodeling for graphs is proposed and it is shown that when the number of vertices tends to infinity while the probabilities remain constant, the block structure can be recovered correctly with probability tending to 1.
Proceedings of the National Academy of SciencesMixture models and exploratory analysis in networks
567 Citations2007M. E. J. Newman, E. A. Leicht
A general technique for detecting structural features in large-scale network data that works by dividing the nodes of a network into classes such that the members of each class have similar patterns of connection to other nodes is described.
Random Structures and AlgorithmsThe phase transition in inhomogeneous random graphs
545 Citations2007Béla Bollobás, Svante Janson +1 more
The “classical” random graph models, in particular G(n,p), are “homogeneous,” in the sense that the degrees tend to be concentrated around a typical value.
Cambridge University Press eBooksGeneralized Blockmodeling
470 Citations2004Patrick Doreian, Vladimir Batagelj +1 more
arXiv (Cornell University)Graph limits and exchangeable random graphs
279 Citations2007Persi Diaconis, Svante Janson
A clear connection between deFinetti's theorem for exchangeable arrays and the emerging area of graph limits is developed and the graph theory is translated into more classical prob- ability.
arXiv (Cornell University)Modeling homophily and stochastic equivalence in symmetric relational data
211 Citations2007Peter D. Hoff
BotGraph: large scale spamming botnet detection
167 Citations2009Yao Zhao, Yinglian Xie +5 more
A novel system called BotGraph is designed and implemented to detect a new type of botnet spamming attacks targeting major Web email providers and uncovers the correlations among botnet activities by constructing large user-user graphs and looking for tightly connected subgraph components.