| 时序图中Top-k稠密子图查询算法研究 |
| |
| 引用本文： | 穆聪聪,王一舒,袁野,乔百友,马玉亮.时序图中Top-k稠密子图查询算法研究[J].计算机科学,2021,48(10):152-159. |
| |
| 作者姓名： | 穆聪聪 王一舒 袁野 乔百友 马玉亮 |
| |
| 作者单位： | 东北大学计算机科学与工程学院 沈阳 110000 |
| |
| 摘 要： | 稠密子图的查询是图分析领域的重要研究问题之一,在社交用户相关性分析、Web中社群分析等方面都有着广泛的应用.目前,关于稠密子图查询的研究工作主要基于静态图.而在实际应用中,时序信息会对稠密子图查询产生重要的影响,使得图拓扑结构随时间序列不断发生变化,包含的信息量也不断增加,使得已有的针对静态图的查找方法不再适用于时序图.因此,如何高效地在时序图上查找稠密子图仍然是一个挑战.为了解决上述挑战,首先规范化地定义了基于时序图的稠密子图查找问题;然后,根据图的拓扑结构和包含时间标签的边之间的相似度,提出一种基于阈值的近似查找算法DTS-base.为了加快算法的收敛速度,提出了一个基于快速计算最大相似度时间片的优化算法DTS-opt.最后,通过在真实数据集上的实验,证明了所提算法的高效性和可扩展性.
|
| 关 键 词： | 稠密子图 时序图 Top-k查询 |
Top-k Densest Subgraphs Search in Temporal Graphs |
| |
| MU Cong-cong,WANG Yi-shu,YUAN Ye,QIAO Bai-you,MA Yu-liang.Top-k Densest Subgraphs Search in Temporal Graphs[J].Computer Science,2021,48(10):152-159. |
| |
| Authors: | MU Cong-cong WANG Yi-shu YUAN Ye QIAO Bai-you MA Yu-liang |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
