图具有可以有效描述现实世界中各类对象及其关系的性质,因此被广泛应用在社交网络处理、智能交通网络和生物分子等众多领域,图中节点间相似度的计算以及对节点的某个或某些(Top-k)相似节点的查询一直是图领域的热点问题。由于传统的图节点相似度计算方法不仅要计算出节点间相似度还需要进行排序,取出其中的Top-k来满足需求,因此,通常在小规模图或者静态图上具有较高的效率,但随着互联网以及大数据等技术的不断发展和普及,图数据中节点的数目与日俱增,规模愈发庞大,且图节点数据更新频率也愈发频繁,使得现有相似节点的查询算法无法适应大规模动态图,处理效率很低。因此,针对这一问题,本文对处理图节点相似领域比较经典的SimRank算法进行改进,深入研究大规模动态图相似节点Top-k查询算法。首先,根据节点相似的程度,对相似关系加以区分,定义了三种相似关系:直相似关系、次相似关系和泛相似关系。其次,根据与查询节点成直相似关系的节点个数n与k的关系,分别采用相应的算法进行相似节点的查找。其中当k-n的差大于一定数值时,由于可能需要取到查询节点的3步以上的邻居节点集合,这时,通过取单向图的方法来提高查询效率。当图数据发生变化时,采用触发式更新策略,判断该更新与查询的关联程度,关联程度较密切时,对图数据采用即时更新的方法,否则,采用定时更新的方法。本文分别从大规模图相似节点Top-k查询以及动态图的更新维护两个角度进行查询。本文的主要内容如下:(1)改进SimRank算法。为了避免原始SimRank算法中,由于叠加使得多个“远关系”的和大于“近关系”和的情况,使其更符合实际应用的需求,本文根据相似关系的远近,依次将相似关系分为三种类型:直相似、次相似和泛相似关系,并且对这三种相似关系分别给出相应的相似度计算方法。(2)查找与查询节点成泛相似关系的节点时,采用在反向图中提取单向图的方法来提高查询效率,减少数据冗余。(3)解决大规模图节点的相似性Top-k查询更新维护问题。采用快照的方法来记录一段时间内图的变化情况,采用触发式更新策略,当图更新与查询关联程度较大,采用即时更新策略;当图更新与查询关联程度较小,采用定时更新策略,将更新合并后,统一更新图。(4)在模拟数据集和真实数据集上进行了实验,验证了本文方法在大规模动态图上实现相似节点Top-k查询的有效性和可行性,且具有良好的查询效率。