Accuracy estimation of link-based similarity measures and its application

Link-based similarity measures play a significant role in many graph based applications. Consequently, measuring node similarity in a graph is a fundamental problem of graph datamining. Personalized pagerank (PPR) and simrank (SR) have emerged as the most popular and influential link-based similarity measures. Recently, a novel link-based similarity measure, penetrating rank (P-Rank), which enriches SR, was proposed. In practice, PPR, SR and P-Rank scores are calculated by iterative methods. As the number of iterations increases so does the overhead of the calculation. The ideal solution is that computing similarity within the minimum number of iterations is sufficient to guarantee a desired accuracy. However, the existing upper bounds are too coarse to be useful in general. Therefore, we focus on designing an accurate and tight upper bounds for PPR, SR, and P-Rank in the paper. Our upper bounds are designed based on the following intuition: the smaller the difference between the two consecutive iteration steps is, the smaller the difference between the theoretical and iterative similarity scores becomes. Furthermore, we demonstrate the effectiveness of our upper bounds in the scenario of top-k similar nodes queries, where our upper bounds helps accelerate the speed of the query. We also run a comprehensive set of experiments on real world data sets to verify the effectiveness and efficiency of our upper bounds.     

大数据下基于异步累积更新的高效P-Rank计算方法

P-Rank是SimRank的扩展形式,也是一种相似度度量方法,被用来计算网络中任意两个结点的相似性.不同于SimRank只考虑结点的入度信息,P-Rank还加入了结点的出度信息,从而更加客观准确地评价结点间的相似程度.随着大数据时代的到来,P-Rank需要处理的数据日益增大.使用MapReduce等分布式模型实现大规模P-Rank迭代计算的方法,本质上是一种同步迭代方法,不可避免地具有同步迭代方法的缺点:迭代时间(尤其是迭代过程中处理器等待的时间)长,计算速度慢,因此效率低下.为了解决这一问题,采用了一种迭代计算方法——异步累积更新算法.这个算法实现了异步计算,减少了计算过程处理器结点的等待时间,提高了计算速度,节省了时间开销.从异步的角度实现了P-Rank算法,将异步累积更新算法应用在了P-Rank上,并进行了对比实验.实验结果表明该算法有效地提高了计算收敛速度.     

基于结构相似性的RDF数据聚类分割

随着语义网的快速发展,RDF数据呈现出海量的增长特征,单机的RDF数据管理系统的可扩展性成为RDF数据发展的瓶颈,分布式的存储是解决这一难题的有效方法。而在数据的分布式存储中,数据分割是其中一个关键问题。文中根据RDF数据可以用有向图来描述特性,利用P-Rank基于结构的节点相似性度量方式计算图结点间的相似度,使用AP聚类算法对度量结果进行聚类,实现RDF数据的有效分割。实验结果表明,该方法能够有效地完成RDF数据的分割,使得类间相似度较小,而类内相似度较大。