面向时序图的K-truss社区搜索算法研究*

徐兰天，李荣华，王国仁，王 彪

北京理工大学计算机学院，北京 100081

1 引言

当前世界信息技术日新月异，每天都会产生大量的信息，越来越多的信息可以组成图结构的数据。在现实世界的许多网络，如社交网络[1-2]、化学网络[3]和图像处理[4-5]等都可以应用图网络。

近年来，图论研究提出用团来解决大图数据中的社区发现问题，即用团来描述大图数据中联系紧密的社区结构。然而团的定义过于严格，在很多情况下不能得到理想的结果，而且极大团的查找都是

NPC（non-deterministic polynomial complete problem）问题。幸而近期又出现许多类团结构，例如K-truss、Kcore等。K-truss结构能很好地体现出紧密社区结构中各节点的关系，其定义的要求要弱于定义严格的团结构，但是大于K-core。最重要的是，K-truss的查找不再是NPC问题，可以大大提高算法效率。

在现实生活中，实体间的联系并不是一成不变的，他们会随着时间而变化，或者实体间的联系本身就带有时间属性。比如在电话的通信网络中，一通电话的双方可以作为两个节点，打电话的行为会在两点间建立边的联系；在学者协作网络中，一个协作出版物的合作学者可以作为节点，协作出版物的出版会使各学者直接形成边联系。然而以上两种边的联系不是永久持续的，电话的通信联系会在电话挂断后被终止，协作出版物出版后学者的联系也会终止。在这种情况下，如果忽略边的时间属性会丢失大量信息。

本文的主要贡献在于基于K-truss模型提出了一种新的适合于时序图数据的持续社区模型，还提出了一种近似线性时间的时序图社区搜索算法。……