软件学报

作者：张千桢，郭得科，赵翔

单位：张千桢，国防科技大学 系统工程学院, 湖南 长沙 41007311,郭得科，国防科技大学 系统工程学院, 湖南 长沙 41007302,赵翔，国防科技大学 系统工程学院, 湖南 长沙 41007303

关键词：时序图;稠密子图;季节突发性;子图挖掘;时间段

基金：国防基础科研计划(WDZC20235250412); 国家自然科学基金(U19B2024, 62272469)

时序图是一类边上带有时间戳信息的图. 在时序图中, 季节突发性子图是在多个时间周期内具有突发性特征的稠密子图, 它可以用于社交网络中的活动发现和群体关系分析. 然而以前大多数的研究主要集中在识别没有时间信息的网络中的稠密子图. 为此, 提出一种极大(ω,θ)-稠密子图模型对时序图中的季节突发性子图进行建模. 所提模型表示时序图中在至少ω个长度不小于θ的时间段内快速累积密度的子图. 为了挖掘出时序图中所有的极大(ω,θ)-稠密子图, 将该类挖掘问题转化为一个混合的整数规划问题, 包括挖掘最稠密子图和寻找突发值最大化时间段集合两个子问题, 并给出有效的解决方案. 进一步基于key-核模型和动态规划思想设计两种优化策略来提升算法的性能. 实验表明所提模型能够真实地反映现实世界中具有季节突发性的行为模式. 同时在5个真实时序网络中验证了所提算法的有效性、效率和可扩展性.

来源：2024年第12期

《软件学报》期刊编辑部

查看软件学报杂志2024年第12期