Institute for Software Research
School of Computer Science, Carnegie Mellon University


Bayesian Mixed-Membership Models
of Complex and Evolving Networks

Edoardo Maria Airoldi

December 2006

Ph.D. Thesis (COS)


Keywords: Statistics, machine learning, unsupervised learning, semi-supervised learning, hierarchical models, latent variables, diffusion, variance allocation, time series, data integration, variational inference, particle filters, text analysis, social network analysis, protein interactions, molecular biology of the cell

Over the past three years I have been working on probabilistic models of multivariate attributes and relations. My work suggests a probabilistic framework and a general modeling approach to complex and evolving networks, which is based on the four concepts of mixed membership, motifs, dynamics and integration. In this thesis, I present such a framework and discuss its properties. In particular, the main goal of the research is to establish the essential elements of formal models of complexity that reconcile the global properties of a system with local phenomena of interest, in a generative fashion.

A solution to the global/local trade-off is to express complexity through hierarchical mixtures of simple patterns, i.e., motifs, that evolve over time. Complex global behavior emerges from the combination of local interaction patterns and their dynamics. I discuss the extent to which this novel framework incorporates, generalizes, and extends other probabilistic approaches present in the literature, and argue that it provides the foundations of a statistical theory of random graphs.

A major part of the effort is devoted to the analysis of modeling issues related to the four essential aspects listed above, in the context of applications to social and biological networks. I also investigate theoretical and computational issues such as the geometrical intuition of the latent allocation task–an important inference objective shared by the various models encompassed by this framework.

233 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by