[go: up one dir, main page]

Skip to main content

A Simple Model for Complex Networks with Arbitrary Degree Distribution and Clustering

  • Conference paper
Statistical Network Analysis: Models, Issues, and New Directions (ICML 2006)

Part of the book series: Lecture Notes in Computer Science ((LNCCN,volume 4503))

Included in the following conference series:

  • 1489 Accesses

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Newman, M.E.J.: Spread of epidemic disease on networks. Physical Review E 66(1), art. no.–016128 (2002)

    Google Scholar 

  2. Dezsó, Z., Barabási, A.L.: Halting viruses in scale-free networks. Physical Review E 65, art. no. 055103 (2002)

    Google Scholar 

  3. Frank, O., Strauss, D.: Markov graphs. Journal of the American Statistical Association 81(395), 832–842 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  4. 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)

    Google Scholar 

  5. Wasserman, S.S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge (1994)

    Google Scholar 

  6. Borgatti, S.P., Everett, M.G., Freeman, L.C.: Ucinet 5.0 for Windows. Analytic Technologies, Natick (1999)

    Google Scholar 

  7. Barndorff-Nielsen, O.E.: Information and Exponential Families in Statistical Theory. Wiley, New York (1978)

    MATH  Google Scholar 

  8. Hunter, D.R., Handcock, M.S.: Inference in curved exponential family models for networks. Journal of Computational and Graphical Statistics, to appear (2006)

    Google Scholar 

  9. 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)

    Google Scholar 

  10. 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)

    Google Scholar 

  11. Bollobas, B.: Random Graphs. Academic Press, New York (1985)

    MATH  Google Scholar 

  12. Newman, M.E.J.: The structure and function of complex networks. SIAM Review 45(2), 167–256 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  13. Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)

    Article  MathSciNet  Google Scholar 

  14. Pastor-Satorras, R., Vespignani, A.: Epidemic dynamics and endemic states in complex networks. Physical Review E 63(6), art. no.–066117 (2001)

    Google Scholar 

  15. Albert, R., Barabási, A.L.: Topology of evolving networks: Local events and universality. Physical Review Letters 85(24), 5234–5237 (2000)

    Article  Google Scholar 

  16. 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)

    Article  Google Scholar 

  17. Simon, H.: On a class of skew distribution functions. Biometrika 42(3-4), 435–440 (1955)

    Article  Google Scholar 

  18. 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)

    Article  MathSciNet  Google Scholar 

  19. 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)

    Article  MathSciNet  Google Scholar 

  20. 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)

    Article  Google Scholar 

  21. Johnson, N., Kotz, S., Kemp, A.: Univariate discrete distributions, 2nd edn. Wiley series in probability and mathematical statistics. Wiley, New York (1992)

    MATH  Google Scholar 

  22. Levene, M., Fenner, T., Loizou, G., Wheeldon, R.: A stochastic model for the evolution of the web. Computer Networks 39(3), 277–287 (2002)

    Article  Google Scholar 

  23. 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)

    Article  Google Scholar 

  24. 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)

    MathSciNet  Google Scholar 

  25. Snijders, T.A.B.: Markov chain monte carlo estimation of exponential random graph models. Journal of Social Structure 3(2) (2002)

    Google Scholar 

  26. 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)

    Google Scholar 

  27. 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)

    Google Scholar 

  28. Besag, J.: Statistical analysis of non-lattice data. The Statistician 24, 179–195 (1975)

    Article  Google Scholar 

  29. 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)

    Article  Google Scholar 

  30. Strauss, D., Ikeda, M.: Pseudolikelihood estimation for social networks. Journal of the American Statistical Association 85, 204–212 (1990)

    Article  MathSciNet  Google Scholar 

  31. Newman, M.E.J.: Assortative mixing in networks. Physical Review Letters 89(20), art no. – 208701 (2002)

    Google Scholar 

  32. 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)

    Google Scholar 

  33. 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Edoardo Airoldi David M. Blei Stephen E. Fienberg Anna Goldenberg Eric P. Xing Alice X. Zheng

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics