Link Prediction on Evolving Data using Tensor Factorization

AutorStephan Spiegel, Jan Clausen, Sahin Albayrak, Jerome Kunegis
QuellePAKDD-2011: Proceeding of ACM International Workshop on Behavior Informatics (BI-2011), Shenzhen, China 
LinksDownload   |   BibTeX 

Within the last few years a lot of research has been done on large social and information networks. One of the principal challenges concerning complex networks is link prediction. Most link prediction algorithms are based on the underlying network structure in terms of traditional graph theory. In order to design efficient algorithms for large scale networks, researchers increasingly adapt methods from advanced matrix and tensor computations. This paper proposes a novel approach of link prediction for complex networks by means of multi-way tensors. In addition to structural data we furthermore consider temporal evolution of a network. Our approach applies the canonical Parafac decomposition to reduce tensor dimensionality and to retrieve latent trends. For the development and evaluation of our proposed link prediction algorithm we employed various popular datasets of online social networks like Facebook and Wikipedia. Our results show significant improvements for evolutionary networks in terms of prediction accuracy measured through mean average precision.