Latent Social Network Influence

Citation

S. A. Myers & J. Leskovec "On the Convexity of Latent Social Network Inference" In Neural Information Processing Systems (NIPS), 2010.

Online version

Link to paper

Summary

This is an interesting paper of learning the graph structure which is not a typical Bayesian graph learning. The main problem that the authors try to solve is given a set of nodes and network diffusion, learn the graph over which the contagion spreads. The assumption is information diffusion often happens over an unknown network. Typically we observe the nodes getting infected and the time they get infected, however we cannot know who infected them. The infection can here can be blogs getting posted with a similar news articles, or people buying a new product or it can be a typical disease that is spreading on geographic or people network. This problem is converted to a maximum likelihood based convex optimization problem and further they introduce an $l_{1}$ penalty to penalize the graph with larger number of nodes.

Description of the method

Assume that there are $N$ nodes in the graph and we present a $NxN$ matrix A where

$A_{ij}=Pr(nodeiinfectsnodej|nodeiisinfected)$

A cascade is defined is based on transmission model $w(t)$ and recovery model $r(t)$. Transmission model defines how much time it takes for an infection to spread from one node to another and recovery model defines how long a node remains infected before it recovers. Further time when each node $i$ is infected is given by $\tau _{i}$. With a $D$ cascades given and a cascade we try to get MLE of the entries of the matrix A.

The following is maximum likelihood estimation problem. Here $X_{c}(t)$ is set of nodes that got infected at the time t and $\tau _{i}^{c}=\inf$ if the node i is never infected in the cascade c.

$L(A;D)=\prod _{c\in D}\left\lbrack \left\lbrace \prod _{i;\tau _{i}^{c}<\inf }P(i{\mbox{ infected at }}\tau _{i}^{c}|X_{c}(\tau _{i}^{c}))\right\rbrace \left\lbrace \prod _{i;\tau _{i}^{c}=\inf }P(i{\mbox{ never infected }}|X_{c}(t)\forall t)\right\rbrace \right\rbrack$

$L(A;D)=\prod _{c\in D}\left\lbrack \left\lbrace \prod _{i;\tau _{i}^{c}<\inf }\left(1-\prod _{j;\tau _{j}\leq \tau _{i}}(1-w(\tau _{i}^{c}-\tau _{j}^{c})A_{ij}\right)\right\rbrace \left\lbrace \prod _{i;\tau _{i}^{c}=\inf }\prod _{j;\tau _{j}^{c}<\inf }(1-A_{ij})\right\rbrace \right\rbrack$