On the Application of Link Analysis Algorithms for Ranking Bipartite Graphs
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Information RetrievalRetrievalSimilar Papers 제목 키워드 기반
Confidence-Weighted Bipartite Ranking
Bipartite ranking is a fundamental machine learning and data mining problem. It commonly concerns the maximization of the AUC metric. Recently, a number of studies have proposed online bipartite ranking algorithms to lea…
BiRank: Towards Ranking on Bipartite Graphs
The bipartite graph is a ubiquitous data structure that can model the relationship between two entity types: for instance, users and items, queries and webpages. In this paper, we study the problem of ranking vertices of…
Addressing Time Bias in Bipartite Graph Ranking for Important Node Identification
The goal of the ranking problem in networks is to rank nodes from best to worst, according to a chosen criterion. In this work, we focus on ranking the nodes according to their quality. The problem of ranking the nodes i…
Graph RankingActive Bipartite Ranking
In this paper, we develop an active learning framework for the bipartite ranking problem. Motivated by numerous applications, ranging from supervised anomaly detection to credit-scoring through the design of medical diag…
BicliqueEncoder: An Efficient Method for Link Prediction in Bipartite Networks using Formal Concept Analysis and Transformer Encoder
We propose a novel and efficient method for link prediction in bipartite networks, using \textit{formal concept analysis} (FCA) and the Transformer encoder. Link prediction in bipartite networks finds practical applicati…
Link PredictionPredictionProduct Recommendation