一种大规模双网络中k-连通Truss子图发现算法

• 作者: 孙晶 李源 王国仁 盛飞 赵宇海
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 双网络 稠密子图发现 k-连通truss子图模型 最大连通truss子图模型 k-类索引
• 年，卷（期）: 2020,（9）
• 页码范围: 1721-1736
• 页数: 16页
• 分类号: TP18
• 字数: 15644字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2020.01721

摘要

双网络由具有相同顶点集合但不同边集合的物理图和概念图构成,能够反映顶点间不同层面的交互关系.双网络中稠密子图发现问题旨在发现物理图中连通而概念图中稠密的子图,在协作者网络分析、社区发现和疾病功能团检测等方面具有广泛应用.但现有稠密子图模型存在以下问题:(1)基于最密集子图模型的稠密子图发现问题本质上是NP-难的,导致精确的子图发现算法在效率上存在很大问题;(2)基于k-核的模型虽然解决了效率问题,但是发现的稠密子图并不真正"稠密".针对以上问题,本文(1)提出了k-连通truss子图(k-CT)模型.该模型更加稠密,因此允许子图间存在重叠;(2)为了发现k-连通truss子图,提出了一种高效的精确亚线性算法用于发现双网络中所有的k-CT子图;(3)基于k-CT子图,提出了最大连通truss子图(MCT)概念,对当前k-CT子图不存在任何非空(k+1)-CT子图;(4)提出了自顶向下、自底向上和二分法三种不同策略的MCT子图发现算法.大量基于真实和合成双网络数据的实验结果证明了本文提出算法的高效性和有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙晶	北方工业大学信息学院	54	408	9.0	19.0
2	赵宇海	东北大学计算机科学与工程学院计算机科学系	30	40	4.0	5.0
3	李源	北方工业大学信息学院	2	2	1.0	1.0
4	盛飞	北京邮电大学计算机学院	1	0	0.0	0.0
5	王国仁	北京理工大学计算机学院	18	29	3.0	5.0