Compare Link Propagation Papers
Contents
Papers
Link propagation: A fast semi-supervised learning algorithm for link prediction , Kashima et al., SDM 2009 Fast and scalable algorithms for semi-supervised link prediction on static and dynamic graphs , Raymond et al. ECML-PKDD 2010.
Method
The first paper introduces the algorithm of "Link Propagation" which is a means of doing link prediction between nodes of a Graph, using the eigen-decomposition of its Laplacian. The second paper is an extension fo the first, in the sense that it builds up on the previous algoritm, introducing an approximate version thereof which operates faster and its performance is on par with the original one. The approximate algorithm relies on Matrix Decompositions, such as the Cholesky decomposition/factorization, and in particular its main idea is the approximation of the Laplacian of the Graph in a lower rank.
Dataset Used
The first paper uses a relatively large variety of different datasets, i.e.:
- KEGG/PATHWAY database
- A dataset derived from the following paper
- A social network dataset: here
The second paper uses multiple versions (of varying size) of the Web Spam Challenge dataset.
Problem
The problem in the first paper is merely the one of predicting missing links between nodes.
However, this is not the main focus of the second paper, even though it builds up on the same algorithm. The second paper is merely concerned with scaling up "Link Propagation" by introducing approximation in the computations, therefore it is more algorithmic oriented.
