信息网络中一个有效的基于链接的结点相似度度量

作     者：张应龙 李翠平 陈红 

作者机构：数据工程与知识工程教育部重点实验室(中国人民大学)北京100872 华东交通大学软件学院江西南昌330045 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2014年第25卷第11期

页      面：2602-2615页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家重点基础研究发展计划(973)(2014CB340402 2012CB316205) 国家自然科学基金(61272137 61033010 61202114) 国家社会科学基金(12&ZD220) 国家高技术研究发展计划(863)(2014AA015200) 国家高等学校学科创新引智计划 

主　　题：随机游走:相似度度量 SimRank Personalized PageRank 

摘      要：信息网络无处不在.通过把网络中的对象抽象为点,把对象之间的关系刻画为边,相应的信息网络就可以用图来表示.图中结点相似度计算是图数据管理中的基本问题,在很多领域都有运用,比如社会网络分析、信息检索和推荐系统等.其中,著名的相似度度量是以Personalized Page Rank和Sim Rank为代表.这两种度量本质都是以图中的路径来定义,然而它们侧重的路径截然不同.为此,提出了一个度量Super Sim Rank.它不仅涵盖了这些路径,而且考虑了Personalized Page Rank和Sim Rank两者都没有考虑的路径,从而能够更加体现出这种链接关系的本质.在此基础上对Super Sim Rank进行了理论分析,从而提出了相应的优化算法,使得计算性能从最坏情况O(kn4)提高到O(knl).这里,k是迭代次数,n是结点数,l是边数.最后,通过实验验证了Super Sim Rank优于Sim Rank和Personalized Page Rank,同时验证了优化算法在各种情况下都是有效的.