Abstract:
|
One of the fundamental problems in network science is link prediction, where the goal is to predict the existence of a link between two nodes based on observed network topology as well as information on nodes (node covariates) if applicable. A common di?culty for many existing methods for link prediction is the lack of certain negative examples of absent edges. Recently, Zhao et al. (2015) proposed a method to resolve this issue by providing a relative ranking of potential links by their probabilities. Since there is no structural assumption on networks in Zhao et al. (2015), the computational cost may become high for large networks. In this talk, we propose a new method to reduce the model complexity, by assuming that the latent probability matrix can be decomposed as a product of two low-rank matrices. A super-e?cient algorithm is developed, based on solving Lyapunov equations iteratively. The algorithm is computationally e?cient and performs well under di?erent simulation settings. We apply the proposed method to predict missing edges in a network of political blogs and a regulatory network of E. coli.
|