×

zbMATH — the first resource for mathematics

A nonparametric view of network models and Newman-Girvan and other modularities. (English) Zbl 1359.62411
Summary: 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.

MSC:
62M45 Neural nets and related approaches to inference from stochastic processes
62G20 Asymptotic properties of nonparametric inference
Software:
BotGraph
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Doreian P Batagelj V Ferligoj A (2005) Generalized Blockmodeling (Cambridge Univ Press, Cambridge, UK).
[2] Airoldi, Mixed-membership stochastic blockmodels, J Machine Learning Res 9 pp 1981– (2008) · Zbl 1225.68143
[3] Erdös, On the evolution of random graphs, Publ Math Inst Hungar Acad Sci 5 pp 17– (1960)
[4] DOI: 10.1002/rsa.20168 · Zbl 1123.05083
[5] Zhao Y (2009) Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation Botgraph: Large scale spamming botnet detection (USENIX, Berkeley, CA), pp 321–334.
[6] DOI: 10.1103/PhysRevE.69.026113
[7] DOI: 10.1038/nature03288
[8] Chung FRK Lu L (2006) CBMS Regional Conference Series in Mathematics, Complex Graphs and Networks (Am Math Soc, Providence, RI).
[9] Kallenberg O (2005) Probability and Its Application, Probabilistic symmetries and invariance principles (Springer, New York). · Zbl 1084.60003
[10] DOI: 10.1016/0378-8733(83)90021-7
[11] DOI: 10.1007/s003579900004 · Zbl 0896.62063
[12] Hoff, Modeling homophily and stochastic equivalence in symmetric relational data 20, in: Advances in Neural Information Processing Systems pp 657– (2008)
[13] Diaconis, Graph limits and exchangeable random graphs, Rendiconti di Matematica 28 pp 33– (2008) · Zbl 1162.60009
[14] Hardy G Littlewood J Polya G (1988) Inequalities (Cambridge Univ Press, Cambridge, UK), 2nd Ed.
[15] DOI: 10.1073/pnas.0610537104 · Zbl 1155.91026
[16] DOI: 10.1103/PhysRevE.74.036104
[17] DOI: 10.1073/pnas.0605965104
[18] Ng, On spectral clustering: Analysis and an algorithm 14, in: Advances in Neural Information Processing Systems pp 849– (2001)
[19] DOI: 10.1111/1467-9868.00265 · Zbl 0957.62020
[20] Zachary, An information flow model for conflict and fission in small groups, J Anthropol Res 33 pp 452– (1977)
[21] DOI: 10.1073/pnas.0611034104
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.