Recovering temporally rewiring networks: a model-based approach

ABSTRACT

A plausible representation of relational information among entities in dynamic systems such as a living cell or a social community is a stochastic network which is topologically rewiring and semantically evolving over time. While there is a rich literature on modeling static or temporally invariant networks, much less has been done toward modeling the dynamic processes underlying rewiring networks, and on recovering such networks when they are not observable. We present a class of hidden temporal exponential random graph models (htERGMs) to study the yet unexplored topic of modeling and recovering temporally rewiring networks from time series of node attributes such as activities of social actors or expression levels of genes. We show that one can reliably infer the latent time-specific topologies of the evolving networks from the observation. We report empirical results on both synthetic data and a Drosophila lifecycle gene expression data set, in comparison with a static counterpart of htERGM.

REFERENCES

• 1: Edoardo Airoldi , David Blei , Eric Xing , Stephen Fienberg, A latent mixed membership model for relational data, Proceedings of the 3rd international workshop on Link discovery, p.82-89, August 21-25, 2005, Chicago, Illinois [doi>10.1145/1134271.1134283]
• 2: Arbeitman, et al. (2002). Gene expression during the life cycle of Drosophila melanogaster. Science, 297, 2270--2275.
• 3: Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286, 509--512.
• 4: Fienberg, S. E., Meyer, M. M., & Wasserman, S. (1985). Statistical analysis of multiple sociometric relations. Journal of the American Statistical Association, 80, 51--67.
• 5: Frank, O., & Strauss, D. (1986). Markov graphs. Journal of the American Statistical Association, 81, 832--842.
• 6: Friedman, N., Linial, M., Nachman, I., & Pe'er, D. (2000). Using Bayesian networks to analyze expression data. Journal of Computatonal Biology, 7, 601--620.
• 7: Hanneke, S., & Xing, E. P. (2006). Discrete temporal models of social networks. Proceedings of the ICML'06 Workshop on Statistical Network Analysis.
• 8: Heckerman, D. (1995). A tutorial on learning with Bayesian networks. Technical Report MSR-TR-95-06.
• 9: Hoff, P. D., Raftery, A. E., & Handcock, M. S. (2002). Latent space approaches to social network analysis. Journal of the American Statistical Association, 97, 1090--1098.
• 10: Haiyan Hu , Xifeng Yan , Yu Huang , Jiawei Han , Xianghong Jasmine Zhou, Mining coherent dense subgraphs across massive biological networks for functional discovery, Bioinformatics, v.21 n.1, p.213-221, January 2005 [doi>10.1093/bioinformatics/bti1049]
• 11: Lawrence, N. D., Sanguinetti, G., & Rattray, M. (2007). Modelling transcriptional regulation using Gaussian processes. NIPS 19.
• 12: Luscombe, N. M., et al. (2004). Genomic analysis of regulatory network dynamics reveals large topological changes. Nature, 431, 308--312.
• 13: Iain Murray , Zoubin Ghahramani, Bayesian learning in undirected graphical models: approximate MCMC algorithms, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.392-399, July 07-11, 2004, Banff, Canada
• 14: Murray, I., Ghahramani, Z., & MacKay, D. J. C. (2006). MCMC for doubly-intractable distributions. UAI 2006.
• 15: Robins, G., Pattison, P., Kalish, Y., & Lusher, D. (2007). An introduction to exponential random graph (p*) models for social networks. Social Networks, 29, 173--191.
• 16: Sarkar, P., & Moore, A. W. (2006). Dynamic social network analysis using latent space models. NIPS 18, 1145--1152.
• 17: Strauss, D., & Ikeda, M. (1990). Pseudolikelihood estimation for social networks. Journal of the American Statistical Association, 85, 204--212.
• 18: Wasserman, S., & Pattison, P. (1996). Logit models and logistic regression for social networks: I. an introduction to markov graphs and p*. Psychometrika, 61, 401--425.
• 19: Wentao Zhao , Erchin Serpedin , Edward R. Dougherty, Inferring gene regulatory networks from time series data using the minimum description length principle, Bioinformatics, v.22 n.17, p.2129-2135, September 2006 [doi>10.1093/bioinformatics/btl364]