Link Discovery using Graph Feature Tracking

Emile Richard (1) , Nicolas Baskiotis (2) , Theodoros Evgeniou (3) , Nicolas Vayatis (1)

1 ENS Cachan - École normale supérieure - Cachan
2 MALIRE - Machine Learning and Information Retrieval
3 INSEAD - Institut Européen d'administration des Affaires

We consider the problem of discovering links of an evolving undirected graph given a series of past snapshots of that graph. The graph is observed through the time sequence of its adjacency matrix and only the presence of edges is observed. The absence of an edge on a certain snapshot cannot be distinguished from a missing entry in the adjacency matrix. Additional information can be provided by examining the dynamics of the graph through a set of topological features, such as the degrees of the vertices. We develop a novel methodology by building on both static matrix completion methods and the estimation of the future state of relevant graph features. Our procedure relies on the formulation of an optimization problem which can be approximately solved by a fast alternating linearized algorithm whose properties are examined. We show experiments with both simulated and real data which reveal the interest of our methodology.

Domaines: Informatique [cs]

Emile Richard, Nicolas Baskiotis, Theodoros Evgeniou, Nicolas Vayatis. Link Discovery using Graph Feature Tracking. Neural Information Processing Systems, NIPS, Dec 2010, Vancouver, Canada. pp.1966-1974. ⟨hal-01289169⟩