-
题名一种大规模双网络中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
[自动化与计算机技术—控制理论与控制工程]
-
-
题名双网络中影响力凝聚子图发现算法
- 2
-
-
作者
李源
杨森
孙晶
赵会群
王国仁
-
机构
北方工业大学信息学院
北京理工大学计算机学院
-
出处
《计算机研究与发展》
EI
CSCD
北大核心
2023年第9期2096-2114,共19页
-
基金
国家重点研发计划项目(2018YFB1004402)
国家自然科学基金青年科学基金项目(61902004)
+1 种基金
国家自然科学基金面上项目(61672041,61772124,61977001)
北京市教委科技项目(KM202010009009)。
-
文摘
双网络由物理图和概念图构成,其中物理图和概念图共享网络结点集合而具有不同边集合.物理图中边表示结点间实际存在的关系;概念图中边表示结点间的相似程度,通常由计算得出.最近,从双网络中发现凝聚子图,即物理图中连通且概念图中稠密的子图受到研究者的广泛关注,在研讨会筹备、商品推荐和致病基因发现等真实场景中具有广泛应用.但现有研究鲜有考虑双网络中凝聚子图的影响力.为此:1)提出一种基于最小边权重定义的影响力凝聚子图,即影响力k-连通truss(k-ICT)子图模型.k-ICT子图模型能够有效刻画子图在双网络中的重要性且对低影响力边鲁棒.2)由证明可知,发现影响力最大的k-ICT子图是NP-难的,因此提出一种基于概念图边等价类划分的CT索引结构.利用索引的概要图,能够根据不同的k值,快速发现包含所有k-ICT子图的候选子图.3)提出了基于全局枚举删除和局部子图扩展的精确算法Exact-G kICT和Exact-LkICT,用于发现top-r具有最大影响力的k-ICT子图.通过大量在真实数据集上的实验,验证算法的高效性和有效性.
-
关键词
影响力凝聚子图发现
影响力k-连通truss子图模型
CT索引
双网络
图数据挖掘
-
Keywords
influential cohesive subgraph discovery
influential k-connected truss subgraph model
CT index
dual networks
graph data mining
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
