A state-space mixed membership blockmodel for dynamic network tomography. (English) Zbl 1194.62133

Summary: In a dynamic social or biological environment, the interactions between the actors can undergo large and systematic changes. We propose a model-based approach to analyze what we will refer to as the dynamic tomography of such time-evolving networks. Our approach offers an intuitive but powerful tool to infer the semantic underpinnings of each actor, such as its social roles or biological functions, underlying the observed network topologies. Our model builds on earlier work on a mixed membership stochastic blockmodel for static networks, and the state-space model for tracking object trajectories. It overcomes a major limitation of many current network inference techniques, which assume that each actor plays a unique and invariant role that accounts for all its interactions with other actors; instead, our method models the role of each actor as a time-evolving mixed membership vector that allows actors to behave differently over time and carry out different roles/functions when interacting with different peers, which is closer to reality.
We present an efficient algorithm for approximate inference and learning using our model. We applied our model to analyze a social network between monks (i.e., the Sampson’s network), a dynamic email communication network between the Enron employees, and a rewiring gene interaction network of fruit fly collected during its full life cycle. In all cases, our model reveals interesting patterns of the dynamic roles of the actors.


62P25 Applications of statistics to social sciences
62P10 Applications of statistics to biology and medical sciences; meta analysis
65C60 Computational problems in statistics (MSC2010)
91D30 Social networks; opinion dynamics


Full Text: DOI arXiv


[1] Ahmed, A. and Xing, E. P. (2007). On tight approximate inference of logistic-normal admixture model. In Proceedings of the Eleventh International Conference on Artifical Intelligence and Statistics . Omnipress, Madison, WI.
[2] Airoldi, E., Blei, D., Xing, E. P. and Fienberg, S. (2005). A latent mixed membership model for relational data. In Proceedings of Workshop on Link Discovery: Issues, Approaches and Applications (LinkKDD-2005), The Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . Chicago, IL.
[3] Airoldi, E. M., Blei, D. M., Fienberg, S. E. and Xing, E. P. (2008). Mixed membership stochastic blockmodel. J. Mach. Learn. Res. 9 1981-2014. · Zbl 1225.68143
[4] Aitchison, J. (1986). The Statistical Analysis of Compositional Data . Chapman & Hall, New York. · Zbl 0688.62004
[5] Aitchison, J. and Shen, S. M. (1980). Logistic-normal distributions: Some properties and uses. Biometrika 67 261-272. · Zbl 0433.62012
[6] Barabasi, A. L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223
[7] Blei, D. and Lafferty, J. (2006a). Correlated topic models. In Advances in Neural Information Processing Systems 18 . MIT Press, Boston, MA. · Zbl 1129.62122
[8] Blei, D. M. and Lafferty, J. D. (2006b). Dynamic topic models. In ICML’06: Proceedings of the 23rd International Conference on Machine Learning 113-120. ACM Press, New York.
[9] Blei, D. M., Jordan, M. I. and Ng, A. Y. (2003). Hierarchical Bayesian models for applications in information retrieval. In Bayesian Statistics 7 (J. M. Bernardo, M. J. Bayarri, J. O. Berger, A. P. Dawid, D. Heckerman, A. F. M. Smith and M. West, eds.) 25-44. Oxford Univ. Press.
[10] Blei, D. M., Ng, A. and Jordan, M. I. (2003). Latent Dirichlet allocation. J. Mach. Learn. Res. 3 993-1022. · Zbl 1112.68379
[11] Breiger, R., Boorman, S. and Arabie, P. (1975). An algorithm for clustering relational data with applications to social network analysis and comparison with multidimensional scaling. J. Math. Psych. 12 328-383.
[12] Erosheva, E. and Fienberg, S. E. (2005). Bayesian mixed membership models for soft clustering and classification. In Classification-The Ubiquitous Challenge (C. Weihs and W. Gaul, eds.) 11-26. Springer, New York.
[13] Erosheva, E. A., Fienberg, S. E. and Lafferty, J. (2004). Mixed-membership models of scientific publications. Proc. Natl. Acad. Sci. 97 11885-11892.
[14] Fienberg, S. E., Meyer, M. M. and Wasserman, S. (1985). Statistical analysis of multiple sociometric relations. J. Amer. Statist. Assoc. 80 51-67.
[15] Frank, O. and Strauss, D. (1986). Markov graphs. J. Amer. Statist. Assoc. 81 832-842. · Zbl 0607.05057
[16] Ghahramani, Z. and Beal, M. J. (2001). Propagation algorithms for variational Bayesian learning. In Advances in Neural Information Processing Systems 13 . MIT Press, Boston, MA.
[17] Handcock, M. S., Raftery, A. E. and Tantrum, J. M. (2007). Model-based clustering for social networks. J. Roy. Statist. Soc. Ser. A 170 1-22. · Zbl 05273954
[18] Hoff, P. D. (2003). Bilinear mixed effects models for dyadic data. Technical Report 32, Univ. Washington, Seattle. · Zbl 1117.62353
[19] Hoff, P. D., Raftery, A. E. and Handcock, M. S. (2002). Latent space approaches to social network analysis. J. Amer. Statist. Assoc. 97 1090-1098. · Zbl 1041.62098
[20] Holland, P., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: Some first steps. Social Networks 5 109-137.
[21] Kleinberg, J. (2000). Navigation in a small world. Nature 406 845. · Zbl 1296.05181
[22] Kolar, M., Song, L., Ahmed, A. and Xing, E. P. (2010). Estimating time-varying networks. Ann. Appl. Statist. 4 94-123. · Zbl 1189.62142
[23] Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J. and Glance, N. (2007). Cost-effective outbreak detection in networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . ACM Press, New York.
[24] Leskovec, J., Lang, K., Dasgupta, A. and Mahoney, M. (2008). Statistical properties of community structure in large social and information networks. In Proc. 17th International Conference on World Wide Web . ACM Press, New York. · Zbl 1205.91144
[25] Li, W. and McCallum, A. (2006). Pachinko allocation: Dag-structured mixture models of topic correlations. In ICML’06: Proceedings of the 23rd International Conference on Machine Learning 577-584. ACM Press, New York.
[26] Lorrain, F. and White, H. C. (1971). Structural equivalence of individuals in social networks. J. Math. Soc. 1 49-80.
[27] Moody, J. and White, D. R. (2003). Structural cohesion and embeddedness: A hierarchical concept of social groups. Amer. Soc. Rev. 68 103-127.
[28] Pritchard, J., Stephens, M. and Donnelly, P. (2000). Inference of population structure using multilocus genotype data. Genetics 155 945-959. · Zbl 1083.62537
[29] Sampson, S. (1969). Crisis in a cloister. Unpublished doctoral dissertation, Cornell Univ.
[30] Sarkar, P. and Moore, A. W. (2005). Dynamic social network analysis using latent space models. SIGKDD Explor. Newsl. 7 31-40.
[31] Shetty, J. and Adibi, J. (2004). The Enron email dataset database schema and brief statistical report. Technical report, Information Sciences Institute, Univ. Southern California.
[32] Snijders, T. A. B. (2002). Markov chain Monte Carlo estimation of exponential random graph models. Journal of Social Structure 3 .
[33] Vardi, Y. (1996). Network tomography: Estimating source-destination traffic intensities from link data. J. Amer. Statist. Assoc. 91 365-377. · Zbl 0871.62103
[34] Wang, X. and McCallum, A. (2006). Topics over time: A non-Markov continuous-time model of topical trends. In KDD’06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 424-433. ACM Press, New York.
[35] Wasserman, S. and Pattison, P. (1996). Logit models and logistic regression for social networks: I. An introduction to Markov graphs and p * . Psychometrika 61 401-425. · Zbl 0866.92029
[36] White, H. C., Boorman, S. A. and Breiger, R. L. (1976). Social structure from multiple networks. I. Blockmodels of roles and positions. Amer. J. Soc. 81 730.
[37] Xing, E. P., Jordan, M. I. and Russell, S. (2003). A generalized mean field algorithm for variational inference in exponential families. In Proceedings of the 19th Annual Conference on Uncertainty in AI . Morgan Kaufmann, San Francisco, CA.
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.