Probabilistic Modeling of Dynamic Networks Using Latent Space Models

• Activity Number: 379
• Type: Invited
• Date/Time: Tuesday, August 3, 2010 : 2:00 PM to 3:50 PM
• Sponsor: General Methodology
• Author(s): Purnamrita Sarkar*+ and Andrew Moore
• Companies: Carnegie Mellon University and Google
• Keywords: Latent Space Models ; Dynamic Network

Abstract

We generalize the successful static model of relationships (Raftery et al.) into a dynamic model that accounts for friendships drifting over time. We show how to make it tractable (sub-quadratic in number of entities) to learn such models from data. We achieve this by using appropriate kernel functions for similarity in latent space, the use of low dimensional kd-trees, a new efficient dynamic adaptation of multidimensional scaling for first pass of approximate projection of entities into latent space, and an efficient conjugate gradient update rule for non-linear local optimization in which amortized time per entity during an update is O(log n). In addition to large real-world social networks, we also successfully modeled the occurrences of Salmonella outbreaks in USDA-controlled food processing establishments as a network evolving over time.