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

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