-
题名一种大规模双网络中k-连通Truss子图发现算法
被引量：1
- 1
-
-
作者
李源
盛飞
孙晶
赵宇海
王国仁
-
机构
北方工业大学信息学院
北京邮电大学计算机学院
东北大学计算机科学与工程学院计算机科学系
北京理工大学计算机学院
-
出处
《计算机学报》
EI
CSCD
北大核心
2020年第9期1721-1736,共16页
-
基金
国家重点研发计划项目(2018YFB1004402)
国家自然科学基金青年项目(61902004)
+3 种基金
国家自然科学基金面上项目(61672041,61772124,61977001)
国家自然科学基金重点项目(61732003)
北京市教委科技项目(KM202010009009)
北方工业大学科研启动经费资助.
-
文摘
双网络由具有相同顶点集合但不同边集合的物理图和概念图构成,能够反映顶点间不同层面的交互关系.双网络中稠密子图发现问题旨在发现物理图中连通而概念图中稠密的子图,在协作者网络分析、社区发现和疾病功能团检测等方面具有广泛应用.但现有稠密子图模型存在以下问题:(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子图发现算法.大量基于真实和合成双网络数据的实验结果证明了本文提出算法的高效性和有效性.
-
关键词
双网络
稠密子图发现
k-连通truss子图模型
最大连通truss子图模型
k-类索引
-
Keywords
dual network
cohesive subgraph discovery
k-connected truss model
maximum-connected truss model
k-class index
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
