聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

IEEE TSMCS'22:时序网络中的稳定拟团挖掘

2023-03-27 13:15 浏览: 2676284 次 我要评论(0 条) 字号:

近年来,从静态图中挖掘社区是复杂网络分析中的一个重要任务。然而传统的静态社区与时序图中的社区概念有很大的不同,并随之而来带来新的问题。比如怎样在时序图中挖掘出稳定的社区,使得社区中的顶点随时间推移仍能维持稳定且稠密的连接。同时,这些稳定社区可能存在互相包含的情况,而显然那些被包含的社区是无意义的。因此,为了对上述现象进行有效的建模,本文提出一种新的模型——极大的ρ-稳定(δ,γ)-拟团(Maximal -Stable-(δ,γ)-Quasi-Clique,SQC)。SQC要求发现的所有的稳定社区彼此不包含,从而保证了结果中每个稳定社区的极大性。此外,由于挖掘所有的SQC是一个NP-难问题,于是本文首先设计一个时序图削减算法TGRA去大幅度地降低原始时序图的规模。然后,在削减之后的时序图上,进而提出分而治之的算法框架BB&SCM,并辅之四个高效的剪枝策略来缩短枚举时间。最后,在七个真实的数据集中做大量的实验来验证所提出方法的效率和有效性。

该成果“Mining Stable Quasi-Cliques on Temporal Networks”发表在IEEE Transactions on Systems, Man, and Cybernetics: Systems(TSMCS)上。TSMCS是控制论领域的顶级期刊之一,属于中科院一区。每年录用率在10%以下,有着非常严格的审稿过程,每篇论文需5-7个审稿人评审。

  • 论文链接:

    https://ieeexplore.ieee.org/document/9424972


研究背景与动机

世界万物的交互沿着时间维度推进,如电信话务网络、在线社交网络、科学合作网络、知识图谱以及物联网。人们通常将这类附有时间信息的交互网络建模成时序图。与传统的静态图相比,时序图刻画了交互的时间信息。因此,时序图能够更加细粒度的揭示交互的来源和演化过程。其中,挖掘大规模时序图中的稳定社区结构对于深入理解和管理此类网络具有重要的科研意义和应用价值。然而,适应时序图的稳定社区定义需综合考虑子图在时序稠密性和时序稳定性两方面的关联特性,因而时序图上的稳定社区的建模更加复杂。现存的方法却对社区的稳定性研究并不充分,不能刻画时序图中社区的稳定性。比如,突发性社区只关注了社区在某一段时间区间内的时序稠密性、周期性社区只考虑了社区出现的时间间隔的周期性。总而言之,这些方法都忽略了社区在不同时间区间上时序稠密性的综合表现(比如,时序稠密性出现的频率)。而显然,这样的综合表现更能真实客观地反应社区的稳定性。此外,不同的稳定社区可能存在互相包含的情况,挖掘出包含的社区既浪费时间又无现实意义。因此,为了有效地对极大稳定社区进行建模,本文基于传统的拟团(Quasi-Clique)来提出ρ-稳定-(δ,γ)-拟团来探索时序图中稳定社区挖掘问题。


设计与实现

本文将静态图中γ-拟团的定义扩展到时序图中,以同时捕捉社区的结构特性和时间特性从而综合衡量社区的结构稠密度和时序稳定性。具体而言,一个(δ,γ)-拟团是由一个顶点集H和一个时间区间T构成,它从平均交互强度的视角来度量H中的顶点在T内互相紧密联系的程度。即H中每个节点在T中的平均度数至少为 (δ,γ)*(|H|-1)。需要注意的是,(δ,γ)-拟团本质上和拟团有显著的不同。比如,(δ,γ)-拟团考虑了更加丰富的时间信息来分析时序图的时序稠密性。此外,相较于其它的子图模型(比如,k-核或者完全图),拟团因引入了参数γ而使得它比完全图更加灵活,同时其在结构上的稠密性又大于k-核。因此,将拟团用于稳定社区的建模更加合理。随后,为了刻画社区的时序稳定性,本文借鉴频繁子图模式中的支持集的概念,将社区的稳定性定义为其对应的极大稠密区间中不重复的时间戳个数在整个时序区间的占比。由此,综合度量社区在不同时间区间上的时序稠密性,并基于此提出了ρ-稳定-(δ,γ)-拟团。即,一个时序子图是ρ-稳定-(δ,γ)-拟团,当且仅当它是连通的时序子图并且它的社区稳定性不小于ρ。最后,本文提出了极大的ρ-稳定-(δ,γ)-拟团(Maximal ρ-Stable-(δ,γ)-Quasi-Clique,SQC)来对极大稳定社区进行建模。SQC要求发现的所有的-稳定-(δ,γ)-拟团彼此不包含,从而保证了结果中每个稳定社区的极大性。由于找出所有的SQC是一个NP-难问题,本文首先设计一个时序图削减算法TGRA来缩小SQC的搜索空间。

时序图削减算法:由于找出所有的极大的ρ-稳定(δ,γ)-拟团是一个NP-难问题,所以直接在原始时序图上进行搜索是不可行的。因此,本文首先提出了一种有效的时序图削减算法TGRA,它能在保证不丢失任何极大的ρ-稳定(δ,γ)-拟团的前提下削减原始时序图的规模(实验结果表明了TGRA能削减原图98%的顶点),并在近似线性时间内完成。TGRA的核心思想是利用节点稳定性的剪枝技术来迭代的删除不合格的顶点。具体而言,其先为每个节点计算出其极大候选稠密区间,然后计算该节点在这些极大候选区间上的稠密度是否满足条件,如果不满足则表明这些节点不可能出现在最终的结果社区中,从而移除这些节点并增量式地更新与被删除节点相邻的节点的极大候选稠密区间。为了快速计算出节点的极大稠密区间,TGRA先递归地计算出所有的极大的j-截断稠密区间,并将这些区间按起始时间排序。然后将多个具有相同开始时间的区间进行合并,只保留具有最大结束时间的区间,合并之后的区间便是节点对应的极大候选稠密区间。

分而治之的枚举算法:在经过TGRA削减之后的时序图上,本文进一步提出了一个分而治之的算法框架BB&SCM来寻找所有的SQC。BB&SCM包括两个阶段。第一阶段,它将结果集初始化为空集并调用TGRA来削减原始时序图的规模。第二阶段,调用B&B算法并基于四个高效的剪枝技术(基于距离、基于界、排除-节点和包含-节点的剪枝技术)来缩小搜索空间或提前终止搜索任务。具体而言,B&B是一个递归调用的算法,其首先调用基于距离的剪枝技术来剪掉一些不合格的顶点,然后调用基于上下界的剪枝技术来确定任务是否继续。算法将对上界满足δ要求的连通时序子图C进行稳定性检查。如果稳定性满足要求则将其加入最终的结果社区,否则,B&B算法重新在当前社区C之外随机选择一个节点,并将任务分为两个子任务继续执行排除-节点剪枝和包含-节点剪枝策略。其中,子任务一在当前的连通时序社区C上继续执行,而子任务二在社区C之外的顶点集上进行。如此,B&B算法递归地将原问题不断划分为更小的子问题,再辅以高效的剪枝策略提高子任务的搜索效率,这为处理大规模复杂时序网络提供了可靠的技术支撑。同时,被划分的两个子任务覆盖了原任务所有可能的情况。因此,当 BB&SCM的枚举搜索过程结束,算法便可以正确地找出所有SQC。图2.1(a-b)展示了BB&SCM的搜索过程,其首先调用TGRA算法来做初步剪枝。然后根据排除-节点和包含-节点剪枝之后得到了四个小的子图。接着,对这四个小的子图采用基于距离剪枝、包含-节点剪枝以及排除-节点剪枝。此时,对剩下的两个子图(图2.1(a))进行稳定性检查,并被确认为稳定社区(图2.1(b))。

(a)调用TGRA划分子任务

(b)稳定性检查

图2.1 BB&SCM的搜索过程


实验结果

本文在七个真实的时序图上做实验来评估提出的算法的效率和有效性。实验结果表明剪枝策略TGRA能削减原始时序图的98%以上的节点(图3.1(a-c))。同时,所提出的BB&SCM算法比基线算法快2个数量级以上(图3.2(a-c))。例如,在一个百万个顶点和千万条边的时序图上,其花费了大约600秒来找出所有的SQC。然而,基线算法不能在一天内得到结果。

图3.1  时序图削减算法TGRA的性能测试

图3.2 各种算法在不同数据集上的运行时间

此外,本文还通过和三个最先进的基线模型(Quick、DClique、PCore)进行定性分析来验证了SQC模型的有效性。各模型所发现社区质量示于表3.1(表中的每个数字是知名公用指标TD质量的平均值标准差)。从表3.1中可以看到SQC除Chess数据集外,在其他所有数据集上都取得了最好的成绩,这表明SQC在时间特征方面比基线模型质量更高。

表3.1  不同模型的质量评估

此外,图3.3展示了Quick、Pcore和SQC在DBLP上所搜索到的关于Maurizio Lenzerini教授的社区的案例分析结果。如图3.3(c)所示,本文提出的模型得到的Maurizio Lenzerini教授的社区是一个更具有现实意义的极大稳定社区,因为这个社区中的所有研究人员在1999年至2016年同Maurizio Lenzerini教授有紧密且稳定的合作。相比之下,Quick找到的社区中的作者(图3.3(a))并没有同Maurizio Lenzerini教授一起频繁工作(不是稳定的合作者)。PCore(图3.3(b))挖掘到的作者较少,因为它要求结果社区中的任何(用户设置的参数)长度的子时间区间内都满足k-核条件,这种强约束导致其无法发现一些潜在的稳定社区。

图3.3  DBLP的案例分析


详细内容请参见:

Longlong Lin, Pingpeng Yuan, Rong-Hua Li, Jifei Wang, Ling Liu and Hai Jin, "Mining Stable Quasi-Cliques on Temporal Networks," in IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 52, no. 6, pp. 3731-3745, June 2022, doi: 10.1109/TSMC.2021.3071721. 

https://ieeexplore.ieee.org/document/9424972



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复