Dynamic Social Network Analysis using Latent Space Models (2005)

Purnamrita Sarkar

Andrew Moore

Abstract

This paper explores two aspects of social network
modeling. First, we generalize a successful static model of
relationships into a dynamic model that accounts for friendships
drifting over time. Second, we show how to make it tractable to
learn such models from data, even as the number of entities n gets
large. The generalized model associates each entity with a point in
p-dimensional Euclidean latent space. The points can move as time
progresses but large moves in latent space are improbable. Observed
links between entities are more likely if the entities are close in
latent space. We show how to make such a model tractable
(sub-quadratic in the number of entities) by the use of appropriate
kernel functions for similarity in latent space; the use of low
dimensional KD-trees; a new efficient dynamic adaptation of
multidimensional scaling for a 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). We use both
synthetic and real-world data on up to 11,000 entities which indicate
near-linear scaling in computation time and improved performance over
four alternative approaches. We also illustrate the system operating
on twelve years of NIPS co-authorship data.

Full text

Download (application/pdf, 456.9 kB)

Approximate BibTeX Entry

@article{sarkar05b,
    Year = {2005},
    Journal = {SIGKDD Explorations: Special Edition on Link Mining},
    Title = {Dynamic Social Network Analysis using Latent Space Models}
}