Link Prediction on Evolving Data using Tensor Factorization


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.

	author = {Spiegel, Stephan and Kunegis, Jérôme and Clausen, Jan and Albayrak, Sahin},
	title = {Link Prediction on Evolving Data using Tensor Factorization},
	booktitle = {PAKDD-2011: Proceeding of ACM International Workshop on Behavior Informatics (BI-2011)},
	year = {2011},
 	location = {Shenzhen, China},
 	publisher = {ACM},
 	address = {New York, NY, USA},
Stephan Spiegel, Jan Hendrik Clausen, Sahin Albayrak, Jérôme Kunegis
Conference Paper
PAKDD-2011: Proceeding of ACM International Workshop on Behavior Informatics (BI-2011), Shenzhen, China