Abstract

for Dynamic Networks Myunghwan Kim Jure Leskovec Stanford University Stanford University Stanford, CA 94305 Stanford, CA 94305 mykim@stanford.edu jure@cs.stanford.eduRelational data—like graphs, networks, and matrices—is often dynamic, where the relational struc-ture evolves over time. A fundamental problem in the analysis of time-varying network data is toextract a summary of the common structure and the dynamics of the underlying relations betweenthe entities. Here we build on the intuition that changes in the network structure are driven by dy-namics at the level of groups of nodes. We propose a nonparametric multi-group membership modelfor dynamic networks. Our model contains three main components: We model the birth and death ofindividual groups with respect to the dynamics of the network structure via a distance dependent In-dian Buffet Process. We capture the evolution of individual node group memberships via a FactorialHidden Markov model. And, we explain the dynamics of the network structure by explicitly mod-eling the connectivity structure of groups. We demonstrate our model’s capability of identifying thedynamics of latent groups in a number of different types of network data. Experimental results showthat our model provides improved predictive performance over existing dynamic network models onfuture network forecasting and missing link prediction.