| 摘要: |
| 动态信息网(DIN)包含了真实世界中随时间推移不断发生变化的对象以及对象间的联系, 常常被刻画为一系列静态无向图快照. 社区, 由信息网中一些内部联系紧密的对象组成. 动态信息网中常常存在这样的社区: 在一段时间内, 随着时间的推移, 社区成员规模不断扩大, 并且社区内部成员间始终保持紧密的联系. 这样的社区在相应时间段内的演化轨迹在动态信息网的多张图快照上形成了一个社区序列, 称为持续扩展社区序列. 在动态信息网中查找持续扩展社区序列有重要的实用价值, 但是以前的工作并未对此进行研究. 结合集合的包含关系和三角连通$k$-truss模型, 提出动态信息网中基于查询点$q$的持续扩展社区序列(qLEC)模型, 设计了一个正向计算社区候选顶点集-反向回溯查找社区序列的持续扩展社区序列两阶段查找算法, 并给出基于提早终止策略的时间优化和基于TCP索引压缩技术的空间优化方法. 通过充分的实验证明: 相比于现有动态社区模型, qLEC模型具有特定的实际意义; 两阶段查找算法能够有效找到qLEC模型所刻画的持续扩展社区序列; 优化策略显著降低了两阶段查找算法的时间和空间开销. |
| 关键词: 动态图 三角连通k-truss 持续扩展社区序列 基于DFS的回溯算法 剪枝 |
| DOI：10.13328/j.cnki.jos.007243 |
| 分类号: |
| 基金项目:国家自然科学基金(62202277, U22A2025) |
|
| Lasting Enlarging k-truss Community Sequence Search in Dynamic Information Networks |
|
WANG Xin-Rui1, YAO Yue1, YU Dong-Xiao1, GAO Hong2, CHENG Xiu-Zhen1
|
|
1.School of Computer Science and Technology, Shandong University, Qingdao 266237, China;2.School of Computer Science and Technology, Zhejiang Normal University, Jinhua 321004, China
|
| Abstract: |
| Dynamic information networks (DIN), which contain evolving objects in the real world and the links among them, are often modeled as a series of static undirected graph snapshots. A community consists of a group of well-connected objects in an information network. In a DIN, there is often a community whose size increases over time but its members always keep well-connected during that period of time. The evolving trajectory of such a community over time forms a sequence of the community on several snapshots of the DIN, which is termed a lasting enlarging community sequence in this study. It is meaningful to search for lasting enlarging community sequences in a DIN. However, no previous research has paid attention to such community sequences. This study formally defines the q-based lasting enlarging community sequence (qLEC) in a DIN by combining set inclusion with the triangle-connected k-truss model. A two-phase search algorithm is developed, which includes computing candidate vertex sets of communities from the beginning to the end of the time window and performing community sequence search from the end to the beginning of the time window. This study also provides optimization strategies based on early termination and TCP index compression to reduce time and space costs. Sufficient experiments demonstrate that the qLEC model has specific practical significance compared to existing dynamic community models. The two-phase search algorithm effectively finds qLEC-based lasting enlarging community sequences. The proposed optimization strategies significantly reduce the spatiotemporal cost of the two-phase algorithm. |
| Key words: dynamic graph triangle-connected k-truss lasting enlarging community sequence DFS-based backtracking algorithm pruning |
