| 摘要: |
| 时序图是一类边上带有时间戳信息的图. 在时序图中, 季节突发性子图是在多个时间周期内具有突发性特征的稠密子图, 它可以用于社交网络中的活动发现和群体关系分析. 然而以前大多数的研究主要集中在识别没有时间信息的网络中的稠密子图. 为此, 提出一种极大(ω,θ)-稠密子图模型对时序图中的季节突发性子图进行建模. 所提模型表示时序图中在至少ω个长度不小于θ的时间段内快速累积密度的子图. 为了挖掘出时序图中所有的极大(ω,θ)-稠密子图, 将该类挖掘问题转化为一个混合的整数规划问题, 包括挖掘最稠密子图和寻找突发值最大化时间段集合两个子问题, 并给出有效的解决方案. 进一步基于key-核模型和动态规划思想设计两种优化策略来提升算法的性能. 实验表明所提模型能够真实地反映现实世界中具有季节突发性的行为模式. 同时在5个真实时序网络中验证了所提算法的有效性、效率和可扩展性. |
| 关键词: 时序图 稠密子图 季节突发性 子图挖掘 时间段 |
| DOI：10.13328/j.cnki.jos.007064 |
| 分类号: |
| 基金项目:国防基础科研计划(WDZC20235250412); 国家自然科学基金(U19B2024, 62272469) |
|
| Mining Method Seasonal-bursting Subgraphs in Temporal Graphs |
|
ZHANG Qian-Zhen, GUO De-Ke, ZHAO Xiang
|
|
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
|
| Abstract: |
| Temporal graph is a type of graph where each edge is associated with a timestamp. Seasonal-bursting subgraph is a dense subgraph characterized by burstiness over multiple time periods, which can applied for activity discovery and group relationship analysis in social networks. Unfortunately, most previous studies for subgraph mining in temporal networks ignore the seasonal or bursting features of subgraphs. To this end, this study proposes a maximal (ω,θ)-dense subgraph model to represent a seasonal-bursting subgraph in temporal networks. Specially, the maximal (ω,θ)-dense subgraph is a subgraph that accumulates its density at the fastest speed during at least ω particular periods of length no less than θ on the temporal graph. To compute all seasonal bursting subgraphs efficiently, the study first models the mining problem as a mixed integer programming problem, which consists of finding the densest subgraph and the maximum burstiness segment. Then corresponding solutions are given for each subproblem, respectively. The study further conceives two optimization strategies by exploiting key-core and dynamic programming algorithms to boost performance. The results of experiments show that the proposed model is indeed able to identify many seasonal-bursting subgraphs. The efficiency, scalability, and effectiveness of the proposed algorithms are also verified on five real-life datasets. |
| Key words: temporal graph dense subgraph seasonal burstiness subgraph mining time span |
