On the Application of Link Analysis Algorithms for Ranking Bipartite Graphs
This work addresses the need for more efficient ranking methods in large, dynamic bipartite graphs, which is an incremental improvement for applications like search engines and social networks.
The paper tackles the problem of ranking items in bipartite graphs, which are common in information retrieval applications like recommender systems and search engines, by proposing a novel algorithm called BipartiteRank that introduces an alternative teleportation method based on graph structure, and it is supported by mathematical arguments and experimental tests on real data.
Recently bipartite graphs have been widely used to represent the relationship two sets of items for information retrieval applications. The Web offers a wide range of data which can be represented by bipartite graphs, such us movies and reviewers in recomender systems, queries and URLs in search engines, users and posts in social networks. The size and the dynamic nature of such graphs generate the need for more efficient ranking methods. In this thesis, at first we present the fundamental mathematical backround that we use subsequently and we describe the basic principles of the Perron-Frobebius theory for non negative matrices as well as the the basic principles of the Markov chain theory. Then, we propose a novel algorithm named BipartiteRank, which is suitable to rank scenarios, that can be represented as a bipartite graph. This algorithm is based on the random surfer model and inherits the basic mathematical characteristics of PageRank. What makes it different, is the fact that it introduces an alternative type of teleportation, based on the block structure of the bipartite graph in order to achieve more efficient ranking. Finally, we support this opinion with mathematical arguments and then we confirm it experimentally through a series of tests on real data.