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

发布时间：2021-12-10 04:51

　　在诸如通信网络、协作网络和社交网络的分析等应用中,边缘上通常包含时间戳。然而以前大多数的研究主要集中在识别没有时间信息的网络中的社区。大规模时序图数据管理与挖掘已经成为数据挖掘领域的一个热点问题,其应用领域十分广泛。团模型是图社区发现问题中的一个重要模型,K-truss结构是团模型的一种重要的松弛模型。对时序图中的社区挖掘问题进行研究,目标是搜索能持续存在的社区结构。由于K-团结构的搜索是一个NP难问题,采用经典的K-truss模型对社区进行建模,进而提出了一种新的适合于时序图数据的持续社区模型（k,Δ,θ）-truss。还提出了一种近似线性时间的时序图社区搜索算法,然后基于真实数据集分析算法的性能和社区挖掘的结果。实验结果表明,K-truss挖掘的效率和社区规模介于K-core与K-团之间,适合比较紧密的社区的搜索。 

【文章来源】：计算机科学与探索. 2020,14(09)北大核心CSCD

【文章页数】：8 页

【部分图文】：

子图规模比较

如图1所示，边(u,v)对于坐标轴上的4表示边(u,v)在4时间出现，记为边(u,v,4)。令Δ=3，根据定义3，边(u,w,1)的持续时间段为[-2,4]，边(u,w,1)及其持续时间段在图1中以蓝线标识；边(v,w,2)的持续时间段为[-1,5]，边(v,w,2)及其持续时间段在图1中以红线标识；边(u,v,4)的持续时间段为[1,7]，边(u,v,4)及其持续时间段在图1中以绿线标识。由边(u,w,1)、(v,w,2)、(u,v,4)三边组成的三角形的持续时间段由三边持续时间段的最晚开始点（即边(u,v,4)的开始时间1）到最早结束点（即边(u,w,1)的结束时间4），即[1,4]。同理，由边(u,w,1)、(v,w,5)、(u,v,4)三边组成的三角形的持续时间段为[2,4]，但该时间段长为2，不满足te-ts≥Δ的条件。由边(u,w,8)、(v,w,5)、(u,v,4)三边组成的三角形的持续时间段为[5,7]，不满足te-ts≥Δ的条件。由于边参与形成的三角形都有其对应的持续时间段，那么边在不同时间段的支持度也不同。边在一个时间段同时参与构成的不同的三角形个数为边在该时间段的支持度。

如图2所示，设边uy在时间6出现，除边uy以外的其他边在时间3出现。如果要在图2中查找(5,3,15)-truss结构，根据4.2节和4.3节可得边uy支持度为3，持续时长为9；边uv、vy、uw、wy、ux、xy支持度为3，持续时长为15；边vw、vx、wx支持度为3，持续时长为18。其中边uy的持续时间不足15，进入删除队列。边uy参与形成了?uvy、?uwy和?uxy。3个三角形被破坏后，边uv、vy、uw、wy、ux、xy的持续时长边为12，也要加入删除队列。进一步删除并更新边的持续时长，边vw、vx、wx也不再满足条件。因此最终结果是图2中不含(5,3,15)-truss结构。算法2主要是时序图下边的(k,Δ,θ)-truss结构的输出，要先处理所有删除队列的边，为O(m)。对于每条边，要遍历它所有参与形成的三角形并更新所有被影响边的支持度及持续时间。令边参与形成的三角形的平均个数为x，时间复杂度为O(x×m)，空间复杂度为O(m)。

【参考文献】：
期刊论文
[1]基于GAS模型的k-truss分解算法[J]. 王邠,周刚,张凤娟.  计算机应用研究. 2018(06)

博士论文
[1]时序图数据处理技术研究[D]. 韩文弢.清华大学 2015

硕士论文
[1]基于扩散K-truss分解算法识别最有影响力节点及其应用研究[D]. 杨李.南京邮电大学 2018
[2]基于k-truss的紧密社区查询算法研究[D]. 魏天柱.燕山大学 2018
[3]社会网络中社区搜索算法设计与实现[D]. 王成成.黑龙江大学 2018
[4]基于k-truss的图社区发现算法研究[D]. 王岩.燕山大学 2016
[5]面向不确定图数据的子图模式挖掘算法的研究与实现[D]. 齐宝雷.东北大学 2013



本文编号：3531939