BiRank: Towards Ranking on Bipartite Graphs

BiRank: Towards Ranking on Bipartite Graphs（扩展到TriRank）

• 2017，IEEE，高明，何向南

• 解决问题：ranking vertices of a bipartite graph, graph ranking, bipartite
  graphs对图中的顶点进行排序.

• 传统方法问题：PageRank, HITS 只使用了graph structure

• 本文方法：graph link structure（就是定义的边的权重，一个只与时间有关的单调、递减、指数衰减函数）, prior
  information of vertices(query vector，其实就是用的顶点的邻居数), regularization
  function, fast convergence, (linear in the number of graph edges,
  对称归一化。时间复杂度O(E)

• BiRank的输入和输出模型：1. 初始化：为使得模型快速收敛，p，u的初始化为S^TS和SST的主正交向量。

• 对比方法：View Count, Comment Count in the Past, Multivariate Linear model, PageRank, Co-HITS, BGER. 2. recommendation: Popularity, ItemKNN, PureSVD, PageRank, TagRW

• 数据集：Synthetic Random Graphs （边服从uniform
  distribution，10K*20K大小），Synthetic Power-law Graphs（生成图的算法见R-energy
  for evaluating robustness of dynamic networks），Yelp和Amazon。

• 源代码、评估指标：NDCG@K

• 实验分析了哪些方面：模拟数据：1.收敛问题，迭代方法能否收敛到正则框架推理下的稳定值，迭代速度10轮；2：控制网络结构和查询向量参与度的参数，与收敛速率的关系，查询向量参与度越大，收敛越快；3.验证一下时间复杂度线性于边数量。真实数据第一个任务BiRank：1. 评估指标（Spearman coefficient），2. 参数调整（grid search，10% held out），3：各个算法，评估指标对比，详细的实验分析（总体分析，拆开分析）。真实数据第二个任务TriRank：1.评估指标（NDCG@K）。