Advertisement

Download PDF

Random graph models for dynamic networks

  • Xiao Zhang
  • Cristopher Moore
  • Mark E. J. Newman
  • Xiao Zhang
    • 1
  • Cristopher Moore
    • 2
  • Mark E. J. Newman
    • 1
    • 2
  1. 1.Department of PhysicsUniversity of MichiganAnn ArborUSA
  2. 2.Santa Fe InstituteSanta FeUSA
Regular Article
First Online: 18 October 2017
Received:
Revised:

Abstract

Recent theoretical work on the modeling of network structure has focused primarily on networks that are static and unchanging, but many real-world networks change their structure over time. There exist natural generalizations to the dynamic case of many static network models, including the classic random graph, the configuration model, and the stochastic block model, where one assumes that the appearance and disappearance of edges are governed by continuous-time Markov processes with rate parameters that can depend on properties of the nodes. Here we give an introduction to this class of models, showing for instance how one can compute their equilibrium properties. We also demonstrate their use in data analysis and statistical inference, giving efficient algorithms for fitting them to observed network data using the method of maximum likelihood. This allows us, for example, to estimate the time constants of network evolution or infer community structure from temporal network data using cues embedded both in the probabilities over time that node pairs are connected by edges and in the characteristic dynamics of edge appearance and disappearance. We illustrate these methods with a selection of applications, both to computer-generated test networks and real-world examples.

Keywords

Statistical and Nonlinear Physics 
Download to read the full article text

References

  1. 1.
    M.E.J. Newman, Networks: An Introduction (Oxford University Press, Oxford, 2010)Google Scholar
  2. 2.
    P. Holme, J. Saramäki, Phys. Rep. 519, 97 (2012)ADSCrossRefGoogle Scholar
  3. 3.
    P. Holme, Eur. Phys. J. B 88, 1 (2015)CrossRefGoogle Scholar
  4. 4.
    S. Boccaletti, G. Bianconi, R. Criado, C.I. del Genio, J. Gomez-Gardenes, M. Romance, I. Sendina-Nadal, Z. Wang, M. Zanin, Phys. Rep. 544, 1 (2014)ADSMathSciNetCrossRefGoogle Scholar
  5. 5.
    M. De Domenico, C. Granell, M.A. Porter, A. Arenas, Nat. Phys. 12, 901 (2016)CrossRefGoogle Scholar
  6. 6.
    P. Grindrod, D.J. Higham, Proc. R. Soc. Lond. A 466, 753 (2010)ADSCrossRefGoogle Scholar
  7. 7.
    P. Grindrod, D.J. Higham, IMA J. Manage. Math. 23, 1 (2012)CrossRefGoogle Scholar
  8. 8.
    P. Grindrod, D.J. Higham, M.C. Parsons, Internet Math. 8, 402 (2012)MathSciNetCrossRefGoogle Scholar
  9. 9.
    J. Ugander, L. Backstrom, J. Kleinberg, Subgraph frequencies: Mapping the empirical, extremal geography of large graph collections, in Proceedings of the 22nd International Conference on World Wide Web, Association of Computing Machinery, New York (2013), pp. 1307–1318Google Scholar
  10. 10.
    E.P. Xing, W. Fu, L. Song et al., Ann. Appl. Stat. 4, 535 (2010)MathSciNetCrossRefGoogle Scholar
  11. 11.
    T. Yang, Y. Chi, S. Zhu, Y. Gong, R. Jin, Mach. Learn. 82, 157 (2011)MathSciNetCrossRefGoogle Scholar
  12. 12.
    M. Kim, J. Leskovec, Nonparametric multi-group membership model for dynamic networks, in Proceedings of the 2013 Conference on Neural Information Processing Systems, edited by C.J.C. Burges, L. Bottou, M. Welling, Z. Ghahramani, K.Q. Weinberger (MIT Press, Cambridge, MA, 2013), pp. 1385–1393Google Scholar
  13. 13.
    C. Matias, V. Miele, J. R. Stat. Soc. B (2016)Google Scholar
  14. 14.
    A. Ghasemian, P. Zhang, A. Clauset, C. Moore, L. Peel, Phys. Rev. X 6, 031005 (2016)Google Scholar
  15. 15.
    K.S. Xu, A.O. Hero III, Dynamic stochastic blockmodels: statistical models for time-evolving networks, in Social Computing, Behavioral-Cultural Modeling and Prediction (Springer, Berlin, 2013), pp. 201–210Google Scholar
  16. 16.
    K.S. Xu, Stochastic block transition models for dynamic networks, in Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, edited by G. Lebanon, S.V.N. Vishwanathan (2015), pp. 1079–1087Google Scholar
  17. 17.
    C. Matias, T. Rebafka, F. Villers, A semiparametric extension of the stochastic block model for longitudinal networks, arXiv:1512.07075 (2015)
  18. 18.
    N. Perra, B. Gonçalves, R. Pastor-Satorras, A. Vespignani, Sci. Rep. 2 (2012)Google Scholar
  19. 19.
    S. Liu, N. Perra, M. Karsai, A. Vespignani, Phys. Rev. Lett. 112, 118702 (2014)ADSCrossRefGoogle Scholar
  20. 20.
    M. Ogura, V.M. Preciado, IEEE Trans. Network Sci. Eng. 3, 44 (2016)MathSciNetCrossRefGoogle Scholar
  21. 21.
    Q. Han, K. Xu, E. Airoldi, Consistent estimation of dynamic, multi-layer block models, in Proceedings of the 32nd International Conference on Machine Learning, edited by F. Bach, D. Blei (Omnipress, Madison, WI, 2015), pp. 1511–1520Google Scholar
  22. 22.
    N. Stanley, S. Shai, D. Taylor, P.J. Mucha, IEEE Trans. Network Sci. Eng. 3, 95 (2016)MathSciNetCrossRefGoogle Scholar
  23. 23.
    A. Clauset, C. Moore, M.E.J. Newman, Nature 88, 98 (2008)ADSCrossRefGoogle Scholar
  24. 24.
    D. Liben-Nowell, J. Kleinberg, J. Assoc. Inform. Sci. Technol. 58, 1019 (2007)CrossRefGoogle Scholar
  25. 25.
    R. Guimerà, M. Sales-Pardo, Proc. Natl. Acad. Sci. USA 106, 22073 (2009)ADSCrossRefGoogle Scholar
  26. 26.
    P. Erdős, A. Rényi, Publ. Math. 6, 290 (1959)Google Scholar
  27. 27.
    P. Erdős, A. Rényi, Publ. Math. Inst. Hungarian Acad. Sci. 5, 17 (1960)Google Scholar
  28. 28.
    M. Molloy, B. Reed, Random Struct. Algor. 6, 161 (1995)CrossRefGoogle Scholar
  29. 29.
    M.E.J. Newman, S.H. Strogatz, D.J. Watts, Phys. Rev. E 64, 026118 (2001)ADSCrossRefGoogle Scholar
  30. 30.
    F. Chung, L. Lu, Proc. Natl. Acad. Sci. USA 99, 15879 (2002)ADSMathSciNetCrossRefGoogle Scholar
  31. 31.
    P.W. Holland, K.B. Laskey, S. Leinhardt, Social Networks 5, 109 (1983)MathSciNetCrossRefGoogle Scholar
  32. 32.
    B. Karrer, M.E.J. Newman, Phys. Rev. E 83, 016107 (2011)ADSMathSciNetCrossRefGoogle Scholar
  33. 33.
    B.W. Kernighan, S. Lin, Bell Syst. Tech. J. 49, 291 (1970)CrossRefGoogle Scholar
  34. 34.
    A. Decelle, F. Krzakala, C. Moore, L. Zdeborová, Phys. Rev. Lett. 107, 065701 (2011)ADSCrossRefGoogle Scholar
  35. 35.
    L. Danon, J. Duch, A. Diaz-Guilera, A. Arenas, J. Stat. Mech. 2005, P09008 (2005)CrossRefGoogle Scholar
  36. 36.
    M. Meilă, J. Multivariate Anal. 98, 873 (2007)MathSciNetCrossRefGoogle Scholar
  37. 37.
    L. Michell, P. West, Health Educ. Res. 11, 39 (1996)CrossRefGoogle Scholar
  38. 38.
    M. Pearson, P. West, Connections 25, 59 (2003)Google Scholar
  39. 39.
    M. Pearson, C. Sieglich, T. Snijders, Connections 27, 47 (2006)Google Scholar
  40. 40.
    R. Mastrandrea, J. Fournet, A. Barrat, PLoS One 10, e0136497 (2015)CrossRefGoogle Scholar
  41. 41.
    J.C. Silva, L. Bennett, L.G. Papageorgiou, S. Tsoka, Eur. Phys. J. B 89, 1 (2016)CrossRefGoogle Scholar

Copyright information

© EDP Sciences, SIF, Springer-Verlag GmbH Germany 2017

Personalised recommendations