View source for Dynamic Social Network Analysis using Latent Space Models

From Cohen Courses

← Dynamic Social Network Analysis using Latent Space Models

You do not have permission to edit this page, for the following reason:

---

You can view and copy the source of this page.

This is one of the [[Category::paper]] written in course [[Social Media Analysis 10-802 in Spring 2011]] == Citation == Purnamrita Sarkar, Andrew W. Moore "Dynamic Social Network Analysis using Latent Space Models" == Online Version == [http://www.sigkdd.org/explorations/issues/7-2-2005-12/4-Sarkar.pdf SIGKDD 2005] == Summary == This paper address the problem of [[AddressesProblem::Social Network Analysis]] using the method of [[UsesMethod::Latent Space Models]]. More specifically, it addresses the problem of network evolution in social network analysis, by modelling the way in which the friendships drift over time. It efficiently learns this even when ''n'' is large, by assuming that nodes represented by points in the latent space do not make large movements over time. Hence it is a latent space model developed for dynamic analysis of social networks to predict the future link structure of the graph. This paper is generalization of static modelling in [[UsesMethod::Latent Space Models]] to Dynamic Social Networks by allowing latent coordinates to change smoothly over time, that is, between any two discretized time steps large movements of points are improbable. This technique is applied to [[UsesDataset::NIPS]] data to analysis the dynamics of network evolution. It is a very powerful visualization tool to help understanding of evolution of the underlying network over time. == Overview of the Method == Suppose that each observed link is associated with a discrete time step, then each time step produces its own graph. Further, with the Markov assumption the latent locations at the next time step are conditionally independent of locations in all other time steps given locations in current time step. This is very similar to method to [http://malt.ml.cmu.edu/mw/index.php/HMM HMM] models. Let <math> G_t </math> be the graph at the time step ''t'' with ''n'' nodes. Let each node at the time step ''t'' be represented in p-dimensional latent space, and let <math> X_t </math> be a <math> n \times p</math> matrix where each row represents the co-ordinates of a node. The conditional independence assumption shown in the figure below and hence we have the following :<math> \begin{array}{lcl} X_t & = & \underset{X}{\operatorname{arg\,max}}\ P(X|G_t, X_{t-1})\\ & = & \underset{X}{\operatorname{arg\,max}}\ P(G_t | X) P(X|X_{t-1})\\ \end{array} </math> [[File:DSNL_HMM.png]] Hence we need to model two probability distributions <math> P(G_t|X) </math> and <math> P(X_t| X_{t-1}) </math>. The intuition is that <math> P(G_t|X) </math> is to estimate a graph such that links between pairs of entities which are far away in the latent Euclidian space are less probable and other distribution <math> P(X_t | X_{t-1}) </math> models the smoothness and assigns large movements of points in latent space less probable. === Model Description=== Let us denote the distance between two nodes <math> i, j</math> in the euclidean latent space as <math> d_{ij} </math>. Also, a radius parameter <math> r_i </math> is introduced for every node <math> i </math>, which is learned from the data. Further, <math> r_{ij} </math> is defined as greater of the radius of nodes <math> i </math> and <math> j </math>. Then the probability that there is a link between nodes $i$ and $j$ is given by :<math> p_{ij} = \frac{1}{1 + e^{(d_{ij} - r_{ij}}} </math> Therefore the probability that we observe a graph <math> G_t </math> given coordinates <math> X_t </math> is given by :<math> p(G_t|X_t) = \prod_{i\sim j} p_{ij} \prod_{i\not \sim j} (1-p_{ij}) </math> Further, they show that it is possible to eliminate quadratic computation of the model over all pairs of links by introducing bi-quadratic kernel, hence it simplifies that two nodes have high probability of a link if their latent coordinates are within the radius of <math> r_{ij} </math> of one another. The transition probability <math> P(X_t | X_{t-1})</math> is simply taken as Guassian in the following way. The parameter <math> \sigma </math> controls the smoothness of transition :<math> X_t \sim N(X_{t-1}, \sigma^2) </math> === Algorithm === Now that the probability distributions are estimable we need to do the optimization problem to find the right <math> X </math> which maximizes the product of these probability distributions. First, the latent coordinates are initialized by a time-dependent variation of the classical [[UsesMethod::Multidimensional Scaling]]. The second part encourages small changes in pairwise distances between two consecutive time steps. There is a parameter <math> \lambda </math> that controls relative importance of previous and current time steps. Further, they use [http://en.wikipedia.org/wiki/Kd-tree KD-Trees] to efficiently compute the gradient of the optimization problem and search in the neighborhoods of the coordinate points in the previous time step. == Datasets Used== The Dynamic Social Network in Latent space model is applied for visualizing and predicting the links in the [[UsesDataset::NIPS]].

Return to Dynamic Social Network Analysis using Latent Space Models.