Abstract
We present a stochastic model for networks with arbitrary degree distributions and average clustering coefficient. Many descriptions of networks are based solely on their computed degree distribution and clustering coefficient. We propose a statistical model based on these characterizations. This model generalizes models based solely on the degree distribution and is within the curved exponential family class. We present alternative parameterizations of the model. Each parameterization of the model is interpretable and tunable. We present a simple Markov Chain Monte Carlo (MCMC) algorithm to generate networks with the specified characteristics. We provide an algorithm based on MCMC to infer the network properties from network data and develop statistical inference for the model. The model is generalizable to include mixing based on attributes and other complex social structure. An application is made to modeling a protein to protein interaction network.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Newman, M.E.J.: Spread of epidemic disease on networks. Physical Review E 66(1), art. no.–016128 (2002)
Dezsó, Z., Barabási, A.L.: Halting viruses in scale-free networks. Physical Review E 65, art. no. 055103 (2002)
Frank, O., Strauss, D.: Markov graphs. Journal of the American Statistical Association 81(395), 832–842 (1986)
Handcock, M.S.: Degeneracy and inference for social network models. Paper presented at the Sunbelt XXII International Social Network Conference in New Orleans, LA (2002)
Wasserman, S.S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge (1994)
Borgatti, S.P., Everett, M.G., Freeman, L.C.: Ucinet 5.0 for Windows. Analytic Technologies, Natick (1999)
Barndorff-Nielsen, O.E.: Information and Exponential Families in Statistical Theory. Wiley, New York (1978)
Hunter, D.R., Handcock, M.S.: Inference in curved exponential family models for networks. Journal of Computational and Graphical Statistics, to appear (2006)
Handcock, M.S.: Assessing degeneracy in statistical models of social networks. Working paper #39, Center for Statistics and the Social Sciences, University of Washington (2003)
Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Random graphs with arbitrary degree distributions and their applications. Physical Review E 64, 026118 (2001)
Bollobas, B.: Random Graphs. Academic Press, New York (1985)
Newman, M.E.J.: The structure and function of complex networks. SIAM Review 45(2), 167–256 (2003)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Pastor-Satorras, R., Vespignani, A.: Epidemic dynamics and endemic states in complex networks. Physical Review E 63(6), art. no.–066117 (2001)
Albert, R., Barabási, A.L.: Topology of evolving networks: Local events and universality. Physical Review Letters 85(24), 5234–5237 (2000)
Liljeros, F., Edling, C.R., Amaral, L.A.N., Stanley, H.E., Åberg, Y.: The web of human sexual contacts. Nature 411(6840), 907–908 (2001)
Simon, H.: On a class of skew distribution functions. Biometrika 42(3-4), 435–440 (1955)
Kendall, M.: Natural law in the social sciences: Presidential address. Journal of the Royal Statistical Society Series A-Statistics in Society 124(1), 1–16 (1961)
Irwin, J.: The place of mathematics in medical and biological statistics. Journal of the Royal Statistical Society Series A (General) 126(1), 1–45 (1963)
Jones, J., Handcock, M.S.: An assessment of preferential attachment as a mechanism for human sexual network formation. Proceedings of the Royal Society of London, B 270, 1123–1128 (2003)
Johnson, N., Kotz, S., Kemp, A.: Univariate discrete distributions, 2nd edn. Wiley series in probability and mathematical statistics. Wiley, New York (1992)
Levene, M., Fenner, T., Loizou, G., Wheeldon, R.: A stochastic model for the evolution of the web. Computer Networks 39(3), 277–287 (2002)
Dorogovtsev, S.N., Mendes, J.F.F., Samukhin, A.N.: Structure of growing networks with preferential linking. Physical Review Letters 85(21), 4633–4636 (2000)
Geyer, C.J., Thompson, E.A.: Constrained monte carlo maximum likelihood calculations (with discussion). Journal of the Royal Statistical Society, Series B 54, 657–699 (1992)
Snijders, T.A.B.: Markov chain monte carlo estimation of exponential random graph models. Journal of Social Structure 3(2) (2002)
Handcock, M.S.: Progress in statistical modeling of drug user and sexual networks. Manuscript, Center for Statistics and the Social Sciences, University of Washington (2000)
Snijders, T.A.B., Pattison, P., Robins, G.L., Handcock, M.S.: New specifications for exponential random graph models. Sociological Methodology 36, to appear (2006)
Besag, J.: Statistical analysis of non-lattice data. The Statistician 24, 179–195 (1975)
Xenarios, I., Salwinski, L., Duan, X.J., Higney, P., Kim, S., Eisenberg, D.: Dip, the database of interacting proteins: a research tool for studying cellular networks of protein interactions. Nucleic Acids Res. 28, 289–291 (2002)
Strauss, D., Ikeda, M.: Pseudolikelihood estimation for social networks. Journal of the American Statistical Association 85, 204–212 (1990)
Newman, M.E.J.: Assortative mixing in networks. Physical Review Letters 89(20), art no. – 208701 (2002)
Morris, M.: Local rules and global properties: Modeling the emergence of network structure. In: Breiger, R., Carley, K., Pattison, P. (eds.) Dynamic Social Network Modeling and Analysis, pp. 174–186. Committee on Human Factors, Board on Behavioral, Cognitive, and Sensory Sciences. National Academy Press, Washington (2003)
Handcock, M.S.: Statistical models for social networks: Inference and degeneracy. In: Breiger, R., Carley, K., Pattison, P. (eds.) Dynamic Social Network Modeling and Analysis, pp. 229–240. Committee on Human Factors, Board on Behavioral, Cognitive, and Sensory Sciences. National Academy Press, Washington (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Handcock, M.S., Morris, M. (2007). A Simple Model for Complex Networks with Arbitrary Degree Distribution and Clustering. In: Airoldi, E., Blei, D.M., Fienberg, S.E., Goldenberg, A., Xing, E.P., Zheng, A.X. (eds) Statistical Network Analysis: Models, Issues, and New Directions. ICML 2006. Lecture Notes in Computer Science, vol 4503. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73133-7_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-73133-7_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73132-0
Online ISBN: 978-3-540-73133-7
eBook Packages: Computer ScienceComputer Science (R0)