Learning Continuous-Time Social Network Dynamics

Yu Fan, Christian R. Shelton

TL;DR

This paper bridges the gap between traditional sociology models of social networks and the more flexible framework of Continuous-Time Bayesian Networks (CTBNs). They introduce a novel sampling-based approach for parameter estimation that significantly outperforms existing methods, especially when dealing with incomplete or indirect observations of network dynamics.

What Problem Does This Paper Address?

Social networks are dynamic entities, with relationships forming and dissolving over time. While traditional sociology models capture some of these dynamics, they often rely on discrete time steps or require complete, synchronous observations of the network. This is a significant limitation because real-world social network data is frequently asynchronous, partial, and collected indirectly (e.g., through communication logs rather than direct relationship surveys). The authors aim to develop a more flexible and accurate method for learning the parameters of continuous-time social network models that can handle these challenging data scenarios. They specifically focus on extending models that consider the co-evolution of network structure and actor attributes.

Methods

The core contribution of this paper is framing existing social network models, particularly the network-attribute co-evolution model, within the Continuous-Time Bayesian Network (CTBN) framework. This allows them to leverage powerful CTBN inference techniques.

Key methodological advancements include:

  • CTBN Conversion: Demonstrating that network-attribute co-evolution models can be represented as CTBNs, enabling the application of CTBN inference algorithms.
  • Sampling-Based Parameter Estimation: Developing an Expectation-Maximization (EM) algorithm that uses importance sampling for the E-step. This approach generates samples that are consistent with the observed data, leading to more accurate parameter estimates compared to the traditional "method of moments" (MoM) which relies on forward sampling that doesn't fully utilize observational data.
  • Handling Indirect Observations: Introducing a "hidden social network dynamics model." In this model, the actual network structure is unobserved, but indirect observations (like emails) are available. They propose a Metropolis-Hastings (MH) algorithm for this model, which reuses the importance sampling framework to efficiently explore the vast state space of hidden network dynamics.

Datasets

  • Synthetic Network: A synthetic social network with 10 individuals and one time-variant attribute was generated to verify the learning algorithm's performance.
  • "50 Girls Data": A real-world dataset from the Teenage Friends and Lifestyle Study, containing network and attribute (alcohol consumption) data for 50 school girls over three observations.
  • Enron Email Dataset: A real-world dataset of emails exchanged among employees, used to evaluate the hidden social network dynamics model. The data was preprocessed to focus on emails within a specific year and between a subset of active users.

Key Insights and Ideas

  • CTBNs as a Unifying Framework: The paper elegantly shows how complex social network dynamics models can be unified under the CTBN framework, opening the door to more advanced inference techniques.
  • The Power of Sampling for Incomplete Data: The core insight is that sampling-based methods, when designed to be consistent with observations (even partial ones), provide a significant advantage over methods that rely on simpler, less informative sampling strategies. This is crucial for real-world data scarcity.
  • Indirect Observations Unlock New Possibilities: The introduction of the hidden social network model and its MH sampler demonstrates that valuable insights into network dynamics can be gleaned even when the network itself is not directly observed, by leveraging proxy data like communication events.
  • Co-evolution is Key: The paper reinforces the importance of modeling the intertwined evolution of network structure and actor attributes, as they mutually influence each other.

Key Results

  • Improved Accuracy: The proposed sampling-based EM algorithm consistently outperformed the traditional method of moments (MoM) in parameter estimation accuracy on both synthetic and real datasets.
  • Robustness to Data Sparsity: The sampling-based approach showed significantly higher accuracy than MoM when the amount of observational data was small.
  • Handling Asynchronous and Partial Data: The methods are shown to be effective with data that is not perfectly synchronized or complete, a common issue in sociological studies.
  • Effective Hidden Network Inference: The Metropolis-Hastings algorithm for the hidden social network model was able to learn meaningful parameters and infer network structures from email data, demonstrating the viability of the approach. For instance, learned parameters indicated that individuals tend to prefer reciprocated connections and are unlikely to form random links.

Limitations and Future Work

  • Computational Cost: While sampling-based methods offer advantages, they can still be computationally intensive, especially for very large networks. The paper mentions that exact inference is intractable for large networks.
  • Parameter Update for Weights: The paper notes that weight parameters (β) cannot be solved analytically in the EM algorithm and require conjugate gradient ascent, which can be computationally demanding.
  • Future Work: The authors suggest that their methods are general and can be extended to other continuous-time systems. They also highlight the potential for applying these techniques to a wider range of social dynamic data types. The paper also implicitly points towards further research in optimizing the sampling and inference algorithms for even larger-scale networks.

Summary updated

Abstract

We demonstrate that a number of sociology models for social network dynamics can be viewed as continuous time Bayesian networks (CTBNs). A sampling-based approximate inference method for CTBNs can be used as the basis of an expectation-maximization procedure that achieves better accuracy in estimating the parameters of the model than the standard method of moments algorithmfromthe sociology literature. We extend the existing social network models to allow for indirect and asynchronous observations of the links. A Markov chain Monte Carlo sampling algorithm for this new model permits estimation and inference. We provide results on both a synthetic network (for verification) and real social network data.
BibTeX
@inproceedings{fan2009learning,
  author = {Yu Fan and Christian R. Shelton},
  title = {{Learning Continuous-Time Social Network Dynamics}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=9aOgQgeYCo},
}
Figure