历史图上的PageRank算法设计与实现

摘要： 近些年来,对于静态图的研究越来越全面、深入，已经形成了完善的理论体系。但是，如果考虑到生活中的一些应用问题，如社交网络中不断变化的关系等，使用静态图表示此类时刻都在变化的关系似乎显得有些乏力。而历史图可以用以表示动态变化。PageRank算法是用于衡量网页重要程度的算法，而网络中不断有网站新建或删除，这样的网络用历史图来表示显得相当贴切，因此我们考虑在历史图上利用CSR(Compressed Sparse Row)结构实现PageRank,使得程序能够给出在几个目标时间的各网站的评分，进而能够提供网站评分的变化情况，给出网站影响力趋势的预测。在Wekipedia提供的网页互相连接的Hyperlink networks数据集上将其性能与在链表上实现PageRank算法作比较，结果显示其性能大大优于使用链表结构，并且随着数据规模和目标时间规模的增大，其优势将会越来越明显。

关键词： PageRank；CSR(Compressed Sparse Row)结构；历史图 

1 引言

1.1 课题背景及研究的目的和意义

在这个时代，大数据是信息化发展到一定阶段的产物。大数据不仅仅是数量上的大，在其背后隐藏着各个行业、领域错综复杂的关系，而这样的关系往往蕴含着商业价值与科研价值[1]。“图”是用来表示关系的一种很好的数据结构，它能够有效且直观地描述现实生活中各个事物之间的复杂关系以及各个事物本身所具有的一些性质。在现实生活中所存在的对象可以抽象为图中的顶点，对象和对象之间的某种或者多种关系可以抽象为顶点与顶点之间的单边或者多边关系。例如在社交网络中，用户与用户之间的好友关系等。

对于传统的图数据来说，它是静态的，只能表示一个单一时刻的数据。但是在真实世界中，对于每时每刻都在变化的生命体及其组成来说，静态图注定无法表示，Przytycka等人认为在未来的工作中从静态网络分析提升到动态网络分析是必不可少的[2]。同理，面对随时随地都在变化的互联网，每时每刻都有页面的不断加入和退出。因此我们需要一个更好的结构来表示该类情况。

1.2 国内外在该研究方向的现状

传统的PageRank 推荐算法需要全图迭代到收敛，因此其时间复杂度非常高，严重影响了推荐的效率。曹军深入分析了PageRank的关键技术，并对其存在的商业问题进行了思考[3]。为了减少算法的耗时，常家伟等人[4]在PageRank算法的迭代过程中加入可控制迭代次数的参数b和一个用于修剪结果向量的阈值α。然后针对主题相关性的问题中，使用了归一化的邻接矩阵的特征值与特征向量来评估节点之间的距离，从而产生最终的推荐列表，而列表中的对象主题相关性则会较高些。对于APP搜索来说，虽然按照关键词搜索出来的应用主题相关性比较高，但是质量参差不齐。因此李春生等人[5]在PageRank算法基础上引入保持时间因子，使用户保存时间越短的 APP 逐渐悬沉下去，保存时间长的 APP 能快速浮上来。在Francisco Pedroche等人[6]的研究中，PageRank被认为是马尔科夫链（1阶）的静止状态，它利用先前状态的知识来转换系统的状态。他们利用“个性化向量”来让PageRank可以偏向某个节点。而且他们将PageRank和多路复用网络结合起来，定义了Multiplex PageRank。

对于传统的静态图完善的理论体系结构来说，历史图仍在发展中。如果时间回退3-5年，鲜有相关论文产出。近几年，越来越多的关注被集中在历史图相关方面的研究。

在文献[7]中，历史图被描述为一系列的静态图序列。由于面向大规模动态图的可达查询研究较少，且尚存在所以压缩困难以及图结构待优化等问题，丁琳琳等人[8]提出了一种支持大规模数据的基于改进哈夫曼编码的可达查询处理方法。该方法首先对预处理图进行结构上的两次压缩，得到双压缩图；其次，基于双压缩图提出一种前缀label索引，该索引能够有效表达节点间的可达关系。最后，提出双压缩图的演进和可达查询处理及优化算法。面向结构变化的动态图匹配问题最早在 2009年由 Wang 和 Chen 提出 , 他们构建邻节点树(NNT)[9]并依此对匹配候选集进行过滤,从而有效减少假阳性匹配结果的产生。 这之后的代表性算法包括IncIsoMatch [10]、SJ-Tree[11]等,它们对子图匹配的执行效率进一步提升提供了不同看法。文献[12]指出：给定一个网络图，计算给定两点之间距离是一个重要的问题。文献介绍了最先进的基于空间相干和基于顶点重要性的方法的综合比较。并使用具有多达两千万个顶点的各种真实道路网络，分别计算了两种技术的预处理时间，空间消耗和查询效率，以此来评估两种技术。

2 PageRank算法