文献类型：期刊文章

作　　者：李源[1] 盛飞[2] 孙晶[1] 赵宇海[3] 王国仁[4]

LI Yuan;SHENG Fei;SUN Jing;ZHAO Yu-Hai;WANG Guo-Ren(School of Information Science and Technology,NorthChina University of Technology,Beijing 100144;School of Computer Science,Beijing University of Posts and Telecommunications,Beijing 100876;School of Computer Science and Engineering(Department of Computer Science),Northeastern University,Shenyang 110169;School of Computer Science and Technology,Beijing Institute of Technology University,Beijing 100081)

机构地区：[1]北方工业大学信息学院,北京100144 [2]北京邮电大学计算机学院,北京100876 [3]东北大学计算机科学与工程学院计算机科学系,沈阳110169 [4]北京理工大学计算机学院,北京100081

出　　处：《计算机学报》

基　　金：国家重点研发计划项目(2018YFB1004402);国家自然科学基金青年项目(61902004);国家自然科学基金面上项目(61672041,61772124,61977001);国家自然科学基金重点项目(61732003);北京市教委科技项目(KM202010009009);北方工业大学科研启动经费资助.

年　　份：2020

卷　　号：43

期　　号：9

起止页码：1721-1736

语　　种：中文

收录情况：BDHX、BDHX2017、CSCD、CSCD2019_2020、EI、IC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：双网络由具有相同顶点集合但不同边集合的物理图和概念图构成,能够反映顶点间不同层面的交互关系.双网络中稠密子图发现问题旨在发现物理图中连通而概念图中稠密的子图,在协作者网络分析、社区发现和疾病功能团检测等方面具有广泛应用.但现有稠密子图模型存在以下问题:(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-类索引  

分 类 号：TP18]