欢迎访问一起赢论文辅导网
机械论文
当前位置:首页 > 机械论文
一种大规模双网络中k_连通Truss子图发现算法_李源
来源:一起赢论文网     日期:2021-02-27     浏览数:2864     【 字体:

 一种大规模双网络中 k-连通Truss 子图发现算法李 源 1) 盛 飞 2) 孙 晶 1) 赵宇海 3) 王国仁 4)1)(北方工业大学信息学院北京 100144)2)(北京邮电大学计算机学院北京 100876)3)(东北大学计算机科学与工程学院计算机科学系沈阳 110169)4)(北京理工大学计算机学院北京 100081)摘 要双网络由具有相同顶点集合但不同边集合的物理图和概念图构成,能够反映顶点间不同层面的交互关系. 双网络中稠密子图发现问题旨在发现物理图中连通而概念图中稠密的子图,在协作者网络分析、社区发现和疾病功能团检测等方面具有广泛应用. 但现有稠密子图模型存在以下问题:(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 DOI 10.11897/SP.J.1016.2020.01721A k-Connected TrussSubgraph Discovery Algorithm inLarge Scale Dual NetworksLI Yuan1) SHENG Fei2) SUN Jing1) ZHAO Yu-Hai3) WANG Guo-Ren4)1)(School of Information Science and Technology, NorthChina University of Technology, Beijing 100144)2)(School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876)3)(School of Computer Science and Engineering(Department of Computer Science), Northeastern University, Shenyang 110169)4)(School of Computer Science and Technology, Beijing Institute of Technology University, Beijing 100081)Abstract Dual network is composed of physical and conceptual graphs with the same set of verticeswhile different sets of edges, which reflects different interactions between vertices. Cohesive subgraphdiscovery in dual network, aiming to find the subgraph connected in physical graph and cohesive inconceptual graph with a wide range of applications. e.g., co-author network analysis, community discoveryand disease function cluster detection. Yet, existing models mainly have the following two limitations: (1)the cohesive subgraph discovery problem based on densest subgraph model is NP-hard in essence, whichleads to low efficiency of accurate discovery algorithm; (2) although the k-core based model solves theefficiency problem, the cohesive subgraphs found are not really cohesive. To overcome above limitations,1722 计算 机 学 报 2020in this paper, (1) the k-connected truss (k-CT) model is proposed, which is more cohesive and allowsoverlapping; (2) an efficient accurate sublinear algorithm is proposed to find all k-CTs; (3) the concept ofmaximum-connected truss (MCT) model is proposed, requiring no non-empty (k+1)-CTs in the dualnetwork; (4) three algorithms based on strategies of up-down, bottom-up and binary search are proposed tofind the MCTs. Extensive experiments conducted on real and synthetic large dual networks demonstrate theefficiency and effectiveness of our approaches.Keywords dual network; cohesive subgraph discovery; k-connected truss model; maximum-connectedtruss model; k-class index1 引言真实世界中,图模型经常被用来表示实体之间的关系,例如社交网络、万维网络、作者协作网络以及生物网络等[1,2]. 给定一个图, 集合中的顶点表示实体,集合中的边表示实体间的关系. 在分析大规模网络时,由于网络规模具有巨大性,研究者通常聚焦于网络中很小但是更重要的区域,这对网络性质的研究更有成效也更加可行[3]. 因此,近年来,稠密子图发现逐渐成为图数据管理和分析领域的热点研究问题,并受到研究者们的广泛关注[4-10].目前为止,许多稠密子图模型已经被提出. 例如,团(clique)或极大团[4]表示一组顶点的子集构成的一个完全子图(即子图内部任意顶点间都存在边). 但是,团的定义过于严格,以至于许多不同松弛条件的稠密子图定义被相继提出. 其中,nclique[5]把团中任意两点间的距离从1 放松到nk-plex[6,7]把大小为c 的团中每个节点的度数从(c-1)放松到(c-k);n-clan[9]n-clique 类似,只是从图直径上对n-clique 加以约束;类团(quasi-clique[9,10]既可以看作从密度上也可以看作从度上对团进行放松. 但是,计算上述稠密子图都是NP-难问题,以至于精确算法很难被扩展到规模更大的图中的稠密子图发现问题,而且当前大多数算法都仅局限于单个图中的稠密子图发现.随着图模型的应用场景越来越复杂,单个简单图已经不能满足表达实体间复杂关系的需要. 在此背景下,双网络模型走入了研究者们的视野. 双网络包含两个具有相同顶点集,但是不同边集的图,其中一个网络表示顶点间物理层面上的交互,体现了顶点间现实中真实存在的联系,称为物理图;另一个网络表示顶点间概念层面的交互,也就是说顶点间具有相似性,但现实中可能不存在联系,该网络称为概念图. 本文聚焦于发现双网络中概念图内稠密,物理图内连通的子图. 该问题在相同研究兴趣小组发现、生物网络内疾病通路识别以及利用社交网络进行精准营销等实际场景中具有广泛应用.例如,图1 展示了利用双网络进行商品推荐的案例. 1(a)为用户的物理图,边表示用户之间真实存在的朋友关系;图1(b)为用户的概念图,边表示用户之间购买商品兴趣相似度. 用户间的相似度可以根据用户-商品打分矩阵中,两个用户对相同商品集合的打分相关性度量而得. 值得注意的是,两个具有相似兴趣的用户可能并不存在直接的现实联系. 但是,如果一组具有很高相似性的用户,如图1(b)所示,在物理图中具有连通性,如图1(a)所示,那么在这组用户中间就可以进行商品推荐. 原因是该组用户中一旦有人购买了某件商品,组内其他用户很有可能对该商品同样感兴趣,且能够根据物理图中的连通性获得该商品的推荐信息.1 朋友关系与购买商品兴趣相似度双网络为了发现双网络中在概念图中稠密而物理图中连通的子图,Wu 等人[11]最先提出了一种DCS(概念图中最密集而物理图中连通)子图模型. 但是,发现DCS 子图为NP-难问题,即使采用近似算法,其发现结果质量不高并且计算效率较低,不能扩展到大图计算. 随后,Cui 等人[12]提出了一种k 连通核(k-connected core, k-CCO)子图模型,该模型要求子图在概念图中为k-[13],而在物理图中连通. k 连通核模型解决了计算效率问题,因为k-核能够在O(n+m)的线性时间复杂度内求出,其中n 表示顶点数,m 表示边数,但是k-核要求每个顶点至少有k个邻居的约束并不强,以至于发现的“稠密子图”9 期李 源等:一种大规模双网络中k-连通Truss 子图发现算法 1723并不真的稠密. 很多稠密子图发现算法都先用k-核进行过滤,正如Seidman[14]所描述,k-核为稠密子图存在的温床.针对现有模型存在的问题,本文提出一种双网络中k-连通trussk-connected trussk-CT)子图模型. 给定一个双网络G(V, Ea, Eb)和正整数kk-CT为双网络中的子图g,并且满足如下三个条件:(1) 在概念图Gb 中,g 内任意一条边至少被k-2 个三角形包含;(2) 在概念图Gb 中,g 内任意两个顶点间都存在一条三角形连通路径,即两个顶点所在的三角形由一系列的三角形连接,其中每两个相邻三角形都共享一条边;(3) 在物理图Ga 中,g 是连通子图.使用k-CT 定义双网络中的稠密子图具有如下优点:(1) k-truss 不但保持了k-核根据k 值变化的子图间具有层次的特性,而且k-truss 子图定义在结构上更加严格(基于三角形),因此也更稠密. 例如,k-truss一定包含于(k-1-核中,但是反之并不成立;(2) 在单一简单图中的k-truss 发现算法,虽然时间复杂度稍微高于k-核,但是仍然是亚线性多项式时间复杂度,同样可以扩展到大图计算中;(3) k-CT 的三角形连通性条件允许不同的k-CT 之间存在交叠,而k-核不支持子图间存在重叠.接下来,给出k-CT 子图模型在双网络中的示例.如图2 所示,图2(a)为物理图Ga,图2(b)为概念图Gb. 从该图中可以看出顶点集合{3, 4, 5, 6}{6, 8,10, 11, 12}分别构成两个4-CT,而且顶点6 可以同时属于两个不同的子图. 相反,根据k-CCO 子图模型,顶点集合{3, 4, 5, 6, 7, 8, 9, 10, 11, 12}整体构成一个3-CCO 子图,几乎覆盖图中所有顶点,未能有效刻画图中的稠密部分.2 双网络示例针对 k-连通truss 子图模型,本文重点解决如下两个问题. 给定双网络G 和正整数k,第一个问题是发现G 中所有的k-连通truss 子图,根据k 值的不同,用户可以得到不同粒度的结果;第二个问题是,在k 值未知的情况下,从双网络中发现最大连通trussMaximum-connected truss, MCT)子图,即对于一个k-CT,不存在任何包含该子图的(k+1)-CT.2 中发现的两个4-CT 均为MCT 子图,因为不被任何5-CT 包含.本文的主要贡献点如下:(1) 提出了双网络中k-CT 子图模型,该模型既能保证发现子图的稠密性,又能保证子图发现的高效性,而且支持子图间存在重叠;(2) 提出了高效的KCT-FIND 算法,用于发现双网络中所有的k-CT 子图;(3) 提出了基于自顶向下、自底向上以及二分法三种不同搜索策略的算法UB-MCTBU-MCT BIN-MCT 以及对上述算法的优化策略,从而实现高效的MCT 子图发现;(4) 在多个真实和合成数据集上的大量实验证明本文提出算法的高效性和有效性.本文的剩余部分组织如下,第2 节阐述和分析了目前单个网络和双网络中稠密子图发现相关工作;第3 节给出相关概念和所要解决问题的定义;第4 节详细阐述k-CT 子图发现算法KCT-FIND;在此基础上,在第5 节中详细介绍本研究中提出的MCT子图发现算法UB-MCTBU-MCT BIN- MCT;第6 节通过在多个真实和合成数据集上的对比实验分析算法的效率和有效性;第7 节对全文进行总结.2 相关工作当前单个简单图中的稠密子图发现算法大致可分为基于团的算法[2]和基于团放松的算法. 团是一种最直观并且最紧密的稠密子图模型,定义为子图中任意两个节点都相邻,图论中被称为完全子图.发现极大团是NP 完全问题,Eppstein D 等人[5]提出的BK 改进算法是当前已知最高效的极大团枚举算法. 在现实应用场景中,由于团的定义过于严格,导致很难发现有效的稠密子图. 为此,诸如n-cliquen-clank-core 等对于团约束更放松的稠密子图定义被接连提出. 接下来分别介绍基于距离、度和三角形约束放松的稠密子图定义和相应的稠密子图模型的特点.(1) 基于距离放松的稠密子图. n-clique 是一个极大子图,要求在整个图中子图中任意两个顶点间的距离不大于n[6]. 由于发现n-clique NP-难问题,文献[6]分别提出基于分支限界技术的精确算法和近似比为2 的近似算法来发现所有结果. n-clan 为一个子图的直径不大于n n-clique,而n-club 则为直径不大于n 的极大子图[9].(2) 基于度放松的稠密子图. k-plex 是一个子图中任意顶点在子图中最多有k 个顶点不相邻的极大1724 计算 机 学 报 2020年子图[7, 8],所以团可以看成是一个1-plex. 文献[7]提出了一种k-plex 枚举算法. k 为常数时,该算法以多项式延迟时间运行. 虽然该算法相对高效,但是对于大图来讲计算效率依然很低. 为此,文献[8]提出了一种发现规模较大的k-plex 算法,该算法通过将大图分解为更小的块,并且过滤掉规模较小的k-plex,从而加速发现满足规模阈值的k-plex. 与之相似的是,k-core 为一个要求子图中每个顶点至少有k 个邻居的极大子图[13,15,16]. 文献[17]最先提出一种与图中边数成线性时间复杂度的核分解算法. 随后,Cheng J 等人[13]提出了一种基于外存的核分解算法,用于发现对于不同k 值的k-. Khaouid W 等人[18]通过分析不同的k-核分解算法,提出了能够在单机上完成的大图-核分解优化算法. 最近Bonchi F 等人[19]k-核的定义一般化,即认为与顶点距离小于等于h 则为该顶点邻居,并提出基于距离泛化的核分解算法. 类团(quasi-clique)则可以看作具有n 个顶点以及γ2æ nö´ç ÷è ø条边[10,20].(3) 基于三角形放松的稠密子图. DN-graph[21]为一个连通子图,并且要求任意连通顶点的公共邻居的下界为局部最大. k-truss 则是一个极大子图,并要求子图中的每一条边的两个顶点都有至少k-2 个共同邻居,与该边共同形成k-2 个三角形[22]. CohenJ[22]最先提出k-truss 定义并给出多项式时间复杂度算法. 随后Wang J 等人[3]提出一种改进的捆分解算法,通过对边进行排序加速算法效率. 在图中关系不确定的情况下,Huang X 等人[23]提出了不确定图上的truss 分解算法. Zheng Z 等人[24]通过设计KEP-索引实现了在边权重图上的高效top-r 权重k-truss子图发现. 另外,文献[25][26]k-truss 应用到社交网络的加固中,分别通过固定某些点和边使得网络中的k-truss 子图结构更加稳定.上述稠密子图模型中,只有k-core k-truss子图能够在多项式时间内求出. 其中核分解问题能够在线性时间复杂度内完成[17]而且高效的全局和局部搜索算法已经被提出用来发现k-core 社区[27-29]truss 分解问题能够在亚线性时间复杂度内完成[3,22],而且已经存在关于k-truss 的社区发现问题的研究[30-31]. 然而,发现其他稠密子图则都是NP-难问题,很难应用到大规模图计算中.近年来,随着图模型应用场景越来越复杂,双网络逐渐受到研究者的关注[11]. 双网络G(V,Ea , Eb ) 包含两个具有相同顶点集,但是不同边集的图,其中一个图表示顶点间的物理交互关系,另一个图表示顶点间的概念交互关系. Wu 等人[11]提出了双网络中的DCS 问题,即发现概念图中密集,物理图中连通的子图,但是该问题为NP-难的. 为此作者提出两种基于不同删除顶点策略的贪婪算法来近似发现最终结果. 由于提出的近似算法没有常数的近似比,所以发现子图的精度无法保证. 随后,Cui 等人[12]提出了k 连通核子图模型,并且提出了高效精确的子图发现算法. 但是k-core 约束较松,所发现子图可能并不稠密且子图间不允许存在重叠.k-truss 基于三角形划分的定义对图中边被三角形包含的数量加以约束,与k-core 对图中顶点度数的约束相比更加严格. 因此,利用k-truss 更能够表征图中的稠密区域,而且k-truss 允许子图结构间存在重叠. 例如在合作者网络中,存在三角形结构表示作者间拥有非常紧密的合作关系,而不是简单的边连接,而且对于同一作者还可以属于多个研究兴趣小组. 针对k-truss 模型,本文提出了双网络中的k-连通truss 子图模型并设计了双网络中高效的子图发现算法,可以在多项式时间内精确发现所有k-连通truss 稠密子图.3 基本概念及问题定义本节主要介绍一些基本概念及其符号表达,阐述了k-连通truss 子图相关定义,并对要解决的主要问题给出具体定义.3.1 基本概念给定一个双网络G(V,Ea , Eb ) ,两个图Ga (V, Ea )Gb (V, Eb )分别表示表示物理图和概念图,其中使用V = {v1, v2 , v3 ,K,vn-1, vn}表示点集,n = V 表示顶点个数. 边集E 中每条边ei, j 表示顶点vi vj 之间存在边. m = E 表示边的个数. m+n 表示图的规模.给定单个图GD 中的顶点u,使用( ) NGD u 表示GD 中顶点u 的邻居集合,用( ) degGD u 表示GD 中顶点u的度数,并且( ) ( ) degGD u NGD u = . 给定一个顶点集合 S(S ÍV ) ,使用GD[S] =|{S,E(S)}表示顶点集 S关于图 GD的诱导子图,对于任意的顶点vi ,v j ÎS ,如果(vi ,v j )Î E ,那么(vi ,v j )Î E(S) .将一个长度为3,顶点分别用u, v, w 表示的环状结构称为三角形结构,记为Duvw,满足u,v,wÎV ,在三角形结构的基础上定义支持度.定义1 (支持度). GD 中的一条边e=(u, v)ÎEGD的支持度用sup(GD, e)表示,其定义为包含e 的三角形的个数,记为sup(GD ,e) = {Duvw |Duvw Î GD} .简而言之,边e 的支持度为图GD 中包含边e9 期李 源等:一种大规模双网络中k-连通Truss 子图发现算法 1725的三角形的个数. 如果边e 被一个三角形D包含,记为e Î D . 接下来,给出k-truss 子图的定义.3 2 4-CT 子图示例定义 2(k-truss 子图). GD k-truss 子图( k2 ),记为 Tk(GD),定义为 GD的极大子图且满足 , sup( ( ), ) 2 e ETk Tk GD e k " Î ≥ - .一条边e 在图GD 中的truss 数表示e 所在的最大非空 k-truss 中的 k 值,记为f (e) = max{k | eÎ( )} ETk GD . 给定f (e) = k ( ) e ETk GD Î 但是e ETk 1 (GD ) .同时使用kmax(GD)表示图GD 任意边中最大的truss. 根据truss 数的定义能够得到边集合k-类的定义.定义3 (k-). GD k-类,记为Φk ,定义为{ | , ( ) } e e EGD e k Î f = .由于k-truss 子图可能不连通[30],所以还不能直接用其表示稠密子图. 接下来,给出三角形邻接和三角形连通的定义.定义4(三角形邻接). 给定图G中的两个三角形结构D1 和D2,如果D1 和D2 共享一条相同的边,则称这两个三角形邻接,表示为D1 ÇD2 ¹ Æ .定义5(三角形连通). 给定图G中的两个三角形Ds 和Dt,Ds 和Dt 三角形连通,当且仅当存在一系列图 G 中的三角形D1¼Dn,其中n2,使得D1=Ds,Dn=Dt并且对于1i < n,Di ÇDi+1 ¹ Æ .k-truss 子图和三角形连通定义的基础上,双网络中的k-连通trussk-connected trussk-CT)子图正式定义如下:定义 6k-CT 子图). 给定一个双网络G(V, Ea,Eb)和正整数k(k2),那么 g 称为 k-CT 子图,需要满足如下条件:(1) g 在概念图中为k-truss 子图;(2) g 在概念图中满足三角连通,即"e1, e2 ÎEb (g),其中e1 ÎD1e2 ÎD2,那么D1=D2 或者D1与D2 g 内三角形连通;(3) g 在物理图中连通;(4) g 为满足条件(1)(2)(3)的极大子图,也就是不存在 g¢ÎG 使得 g Í g¢并且 g¢满足条件(1)(2) (3).有时在k 没有给定的情况下,需要发现双网络G 中使k 值最大的非空k-CT 子图. 根据定义5,给出最大连通trussMaximum-Connected TrussMCT)子图的定义.定义7MCT 子图). 给定一个双网络G,子图g MCT 子图,当且仅当g 为一个k-CT 子图并且G 中不存在非空的(k+1)-CT.定义8(最大CT 数). 给定一个双网络GG的最大CT 数,记为kCTmax(G),是使得k-CT 子图不为空的最大k .例如,图3 展示了图2 中的两个4-CT 子图,分别有顶点集合{3, 4, 5, 6}{6, 8, 10, 11, 12}构成,并且这两个4-CT 子图同样为MCT 子图,因为不存在一个非空的5-CT 子图,所以图2 中双网络的最大CT 数值为4.3.2 问题定义问题 1. 给定双网络G(V, Ea , Eb )和正整数k(k2) ,从G 发现所有的k-CT 子图结构.随着k 值增加,结构内部顶点之间的联系愈加紧密,第二个要解决的问题就是发现双网络中的MCT 子图.问题 2. 给定双网络G(V, Ea , Eb ),从 G 中发现所有的MCT 子图结构.解决上述两个问题主要存在如下两个挑战:(1) k-CT 子图结构需要同时满足物理图和概念图中的约束,比如概念图中的k-truss 子图在物理图中并不连通,或者在物理图中连通的子图并不满足概念图中k 值的约束;(2)在双网络中没有给定k 值的情况下,为了求得所有MCT 子图,需要能够较快地确定kCTmax(G).4 双网络中 k-CT 子图发现算法本节主要研究双网络中k-CT 子图发现问题,给定正整数k(k2),从双网络中发现所有的 k-CT 子图. 通过分析传统单一网络中的k-truss 发现算法以及双网络中其它稠密子图算法,提出了双网络下的k-CT 子图发现算法KCT-FIND. 该算法的主要思想是从物理图出发高效地计算双网络中k-CT 子图. 接下来,首先分析KCT-FIND 算法思想,然后给出算法描述,最后分析KCT-FIND 算法的复杂性.4.1 KCT-FIND算法思想现有单网络中k-truss 发现算法虽然能够准确查1726 计算 机 学 报 2020年找到需要的结果,但在双网络中,k-truss 结构的发现存在着困难,原因是传统单网络中的发现算法在双网络中运行存在一定的局限性.k-CT 子图结构要求在概念图子图中要满足k-truss 结构的定义;在物理图中,要求相应的顶点处于同一连通分量中. 一般的思路是从概念图入手,首先从概念图中寻找满足k-truss 定义的子图,然后在物理图中判断对应的顶点是否在同一个连通分量中,若属于同一连通分量,则将该结构纳入结果集合.若不属于同一连通分量,在对结果精确度要求不高的情况下,可以通过补点或补边的方式使物理图中相应的顶点连通,如图4 所示的社交双网络和k=4 作为输入,查找符合k-truss 结构的子图.4 社交双网络如图 5 所示,经过计算,查找出两个4-truss 子图结构,第一个由顶点abfdg 组成的4-truss在物理图中连通,而由顶点mklj 组成4-truss在物理图中分属两个连通分量,此时可以通过添加边(l, j)使结构满足k-CT 子图的定义,但这样做会对结果的准确性产生影响,因为边(l, j)在最先输入双网络中并不存在. 若对于结果精确度要求较高,仅从概念图中发现k-truss 的策略并不可行,只有在确保连通性的前提下才能继续后面概念图中的k-truss发现工作. 通过上述分析发现,需要对概念图和物理图交替进行处理.5 社交双网络中发现结果本节提出KCT-FIND 算法从物理图入手:(1) 在物理图中查找所有的连通分量. (2) 在得到所有连通分量后,计算每个连通分量内的点集关于概念图的诱导子图中每条边的支持度,并初始化. (3) 遍历概念图中的边,删除支持度不满足条件的边,若有顶点因此孤立,则在物理图和概念图中删除该顶点.值得注意的是,顶点的删除可能会造成物理图中连通分量变为不连通,也可能会影响其它边的支持度,在删除边时要及时更新邻居边的支持度,在第三步中已经完成了概念图中k-truss 的发现. 对于每个概念图中的k-truss 子图来说,物理图中的节点应该是连通的,由于可能出现删除顶点的情况,物理图中节点的连通性可能遭到了破坏. (4) 检查每个概念图中的k-truss 子图的顶点集合在物理图中的连通性,如果连通则符合k-CT 定义,若出现因删除节点造成的断裂,则可以将k-truss 子图和k-truss 子图顶点集合关于物理图的诱导子图作为输入,不断分解双网络. 接下来给出KCT-FIND 具体的描述.4.2 KCT-FIND算法描述KCT-FIND 算法是第一个双网络中k-CT 子图结构发现算法,根据4.1 节讨论的从物理图出发,保证连通性的查找策略,本节给出KCT-FIND 算法的具体描述,如算法1 所示.首先KCT-FIND 算法对结果集合T 初始化为空集(第1 行). 其次,该算法在物理图中寻找所有连通分量,此工作可用广度优先算法实现,这里用C表示连通分量包含的顶点集合,计算物理图中的连通分量的点集在概念图内的诱导子图Gb[C]中所有边的支持度,并做初始化. 如果概念图Gb[C]中所有边均满足支持度要求并且三角连通,则将Ga[C]Gb[C]加入结果集合T 中(第2-4 行). 否则,迭代移除Gb[C]中未满足支持度大于k-2 的边,同时更新边两端顶点的邻居节点的支持度. 若有顶点因此孤立,则将该顶点从物理图和概念图中删除(第5 行).接下来,KCT-FIND 算法对概念图中的每一个三角连通分量,记为H,将Ga[H]Gb[H]作为新的双网络递归调用KCT-FIND 算法,不断进行分解直到发现最终结果(第6-7 行). 最终,算法返回结果集合T(第8 行).算法1. KCT-FIND.输入:G(V,Ea ,Eb )和正整数 k输出:所有k-CT 子图结构T1. T ÜÆ ;2. FOR 每个Ga 中连通分量Ga[C]do3. IFGb[C]中所有边支持度≥k-2 并且Gb[C]三角形连通4. Ga[C]Gb[C]纳入结果集T5. ELSE 迭代将Gb[C]中所有支持度小于k-2 的边删除,9 期李 源等:一种大规模双网络中k-连通Truss 子图发现算法 1727同时删除孤立顶点;6. FORGb[C]中每个三角形连通分量Gb[H] do7. T ÜT ÈKCT-FIND(Ga[H], Gb[H], k)8 返回T;以图 3 中的双网络为例,给定正整数k=4,求出该双网络中所有k-CT 子图结构. 使用KCT-FIND算法执行效果如下. 按照算法第2-4 行计算物理图中的所有连通分量,图4 物理图中存在两个连通分量,分别是由顶点abcdefghij组成的连通分量,和顶点kml 组成的连通分量.计算概念图中所有边的支持度,并做初始化. 初始化结果如图6 所示.6 4 中概念图每条边包含三角形数接下来,根据算法第5 行,移除概念图中支持度不足k-2 的边,在图中5 中分别移除边(ac)(bc)(ef)(gh)(hi)(ij)(li)(dk)(di),并且在双网络中移除孤立顶点cehi,同时更新边的支持度. 根据算法(6-7 )传入概念图中的诱导子图以及在物理图中的连通分量,由顶点集合{a, b, d, f, g}诱导的双网络子图,通过验证满足k-CT 子图结构约束,将其加入结果集T. 由顶点集{m, k, l, j}诱导的双网络子图则在物理图中不连通,存在两个连通分量,其顶点集分别为{k, m, l}{j},将该双网络和k=4 再次调用KCT-FIND 算法.最终结果如图7 所示,结果集T 中只包含一个4-CT子图.7 4 双网络中发现的4-CT 子图算法 1 的执行过程可以用一个图8 中给出的深度优先搜索树来表示,该树的每一个节点代表一次k-CT 调用过程,h 代表树的高度.8 深度优先搜索树4.3 KCT-FIND算法复杂度分析时间复杂度:算法1 中获取所有连通分量花费O( Ea )的时间,检查所有边的支持度和连通性花费O( Eb 1.5)的时间,移除支持度不足的边和孤立顶点花费 O( Eb )的时间,在一般情况下, Eb > Ea ,所以深度优先搜索树中的每个节点的复杂度为 O( Eb 1.5).树的高度为h 时,( , a , b ) lG V E E G b b E E ¢ ¢ ¢ ¢ Îå ¢ ≤ ,所以算法1 的总体时间复杂度为O( 1.5Eb ´ h ).空间复杂度:算法使用O(V + Ea + Eb ) 空间来存储双网络,O( Ea + Eb )空间存放边序列和结果集合.因此最终空间复杂度为O(V + Ea + Eb ) .5 双网络中 MCT 子图发现算法上节处理的是k-CT 子图发现问题,本节试图在双网络中发现最大连通truss 子图,具体描述见定义7. MCT 作为双网络中阶数最高的k-CT 结构,拥有着最高的紧密程度,在双网络中寻找MCT 结构,因为k 值较大,寻找到符合条件的结构中每条边的支持度也较大,代表该边两端顶点的公共邻居也较多,同时符合条件的节点数量会随着k 值的增大而减少,这种高密度的稠密子图是复杂网络研究的关键.例如,在合作者双网络中寻找MCT 结构,MCT 在概念图中是最大k-truss 结构,代表着MCT 子图内顶点作者之间的研究方向非常近似,同时MCT 结构在物理图中连通,代表作者之间都有现实世界中的联系,发现MCT,有助于挖掘出一个研究方向相似、现实之间有联系的研究小组.kCTmax MCT 中使k-CT 结构存在的最大的k 值,如果kCTmax 已知,则可以通过k-CT 发现算法计算获得所有的解, 即可以获得双网络中的kCTmax-CT 子图. 因此,主要的挑战是计算kCTmax.MCT 计算问题可在多项式时间内解决,本节详细介绍双网络中最大连通truss(MCT)子图的计算策略,并根据自底向上、自顶向下和二分查找三种计算策1728 计算 机 学 报 2020年略,提出了 BU-MCTUB-MCT BIN-MCT 三种MCT 子图发现算法,并且分析了各个算法的复杂度,最后对上述MCT 子图发现算法做进一步优化.5.1 自底向上MCT发现算法BU-MCT5.1.1 BU-MCT 算法思想本小节提出一种直接的MCT 发现算法,如算法2 所示,第一步,将k 初始化为3,因为k-truss的定义限制k 的最小值为3,第二步,初始化后将目标双网络和k=3 传入KCT-FIND 算法,若结果集合T 为空,说明3-CT 在目标双网络中不存在并返回NULL. 第三步,若集合T 不为空则将k 1,再作为参数传入KCT-FIND 算法,直到集合T 为空,并将k-1 作为kCTmax 返回.MCT发现算法中调用KCT-FIND 算法时需要等待遍历完双网络才能开始下一次调用,而MCT 发现过程在出现第一个k-CT 后就可以中断. 对此本节更新了KCT-FIND 算法,具体执行过程如过程1 所示.过程1 改进了KCT-FIND 算法,其中一旦发现存在k-CT 子图后不再进行后续搜索,极大地节省了发现MCT 子图算法的运行时间.算法2. BU-MCT.输入:G(V, Ea , Eb )输出:所有 MCT 子图结构T1. T 初始化为空集;2. T Ü KCT-FIND-NEW(G3)3. k Ü34. WHILET 不为空集do5. k Ük +16. T Ü KCT-FIND-NEW (Gk)7. T Ü KCT-FIND (Gk-1)8. 返回T;过程 1. KCT-FIND-NEW输入:G(V, Ea , Eb ) 和正整数 k输出:某个 k-CT 子图T1. T Ü Æ ;2. FOR 每个连通分量Ga[C] in Gado3. IFGa[C]中所有边支持度≥k-2 并且Gb[C]三角连通do4. Ga[C]Gb[C]纳入结果集T5. 返回T6. ELSE 迭代将Gb[C]中所有支持度小于k-2 的边删除,同时删除孤立顶点;7. FORGb[C]中每个三角连通分量Gb[H] do8. T ÜT ÈKCT-FIND-NEW(Ga[H]Gb[H]k)9. 返回T5.1.2 BU-MCT 算法描述根据 5.1.1 节的算法思想,本小节提出了完整的自底向上的MCT 发现算法,算法完整过程如算法2所示. BU-MCT 算法(第1-3 行)对结果集合T k初始化,算法(第4-6 行)检查当前k 值在双网络中是否存在k-CT 结构,若存在k=k+1,否则跳出循环,算法(第7 行)确认kCTmax,调用KCT-FINDGk-1),返回结果T.5.1.3 BU-MCT 算法复杂度分析算法 2 中(第6 行)获取k-CT 结构最多花费O( | Eb |1.5 ´ h )的时间,外循环最多循环 kCTmax次,所以时间复杂度最坏情况为 O( | Eb |1.5 ´ h´ kmax ).影响该算法时间复杂度的主要分为两个方面,第一个方面是k-CT 的查找,详细分析见4.2 节,第二个方面是kCTmax 的大小,因为k 的初始值是3,若kCTmax 很大,会导致k-CT 发现算法被多次调用.因此,此算法适合应用于小规模数据集或者kCTmax值较小的数据集当中.5.2 自顶向下MCT发现算法UB-MCT5.2.1 UB-MCT 算法思想在上一节中提出了自底向上的算法BU-MCT,鉴于在复杂网络中,kCTmax 可能会很大,导致该算法的复杂度较高,本节提出了一种自顶向下的算法UB-MCT. 该算法首先根据定理5.1,找出kCTmax 可能的最大值,该值可以通过分解双网络,找到概念图中顶点的最大核数[13]从而确定kCTmax. 概念图Gb的最大核数用bmax(Gb)表示,然后将k 初始化为bmax(Gb)+1,接下来将目标双网络和k 值传入KCTFIND-NEW 算法,如果结果集合T 不为空,说明bmax(Gb)-CT-CT 在目标双网络中存在, kCTmax=bmax(Gb)+1;否则,更新k=k-1,重复调用KCTFIND-NEW 算法,直到结果集合T 不为空.定理1. G 中每一个k-truss 都是一个(k-1)-core的子图.证明:令T 为图G 的一个k-trussT 中一条边为e=(uv),顶点u v 包含至少k-2 个共同邻居,因为e 的存在,k-truss 每个顶点度至少为k-1,满足(k-1)-core 定义. 证毕.算法3. UB-MCT.输入:G(V, Ea , Eb )输出:所有 MCT 子图T1. T Ü Æ ;2. core-number(Gb)//计算Gb 中顶点的核数3. k = maxuÎV (b (u)) +19 期李 源等:一种大规模双网络中k-连通Truss 子图发现算法 17294. WHILET 为空集并且k3do5. TÜKCT-FIND (Gk)6. kÜk-17. 返回T;通过对概念图进行k-核分解,可以获取每个顶点的核数,并且得到bmax(Gb)值,为计算kCTmax 上界做好准备,core-number 算法的具体过程见文献[13].5.2.2 UB-MCT 算法描述根据 5.2.1 节的算法思想,本小节给出了自顶向下UB-MCT 发现算法完整的执行过程,如算法3 所示. UB-MCT 发现算法首先将结果集合T 初始化为空集(1 ). 然后,通过调用core-number 核分解算法对双网络中概念图Gb 进行核分解,返回每个顶点的核数,并将所有顶点中最大的核数加1 赋值给k(第2-3 行). 接下来,算法在结果集合为空集的条件下,循环调用KCT-FIND 算法,并使k=k-1,直到结果集合T 不为空跳出循环,或者k>3 时为止(第4-6 行). 最后UB-MCT 算法返回结果集合T.5.2.3 UB-MCT 算法复杂度分析算法 3 中,获取k-CT 结构最多花费1.5 O( Eb ´ h)的运行时间,外循环最多循环次 maxuÎV (b (u))次,因此最坏时间复杂度为1.5 O( Eb ´ h´maxuÎV (b (u))) .影响该算法复杂度的主要分为两个方面,第一个方面是 k-CT 的查找,第二个方面是maxuÎV (b (u))kCTmax 值之间的差距. 在两者相距较近时,时间复杂度可以逼近1.5 O( Eb ´ h) .5.3 基于二分法的BIN-MCT算法5.3.1 BIN-MCT 算法思想前两节提出了两种不同方向的算法,鉴于在复杂网络中,kCTmax 的上下限已知,故能够采用二分法思想加速MCT 子图发现过程. 本节提出了一种基于二分法的算法BIN-MCT. 首先,根据定理5.1,找出kCTmax 可能的最大值和最小值,分别记为maxminmax 初始化为maxuÎV (b (u))min 初始化 3.然后,将k=min+(max-min)/2 和双网络G 作为参数输入KCT-FIND-NEW 算法中,如果结果集合T 为不为空,则说明k-CT 在目标双网络中存在,将k作为min max 作为参数输入BIN-MCT 算法,否则将k 作为max min 作为参数输入BIN-MCT,直到结果max-min1 时,返回max .算法4. BIN-MCT.输入:G(V, Ea , Eb )输出:所有 MCT 子图T1. T Ü Æ ;2. core-number(Gb)3. max = maxuÎV (b (u)) +1min= 34. k=BIN-Search(G, min, max)5. 返回 KCT-FIND(G, k);过程 2.BIN-Search(G, min, max)1. T Ü Æ ;2. k = min + (max -min) / 2 3. IF max -min1do4. 返回max5. T Ü KCT-FIND-NEW(G, k)6. IFT 为空do7. 返回 BIN-Search(G, min, k)8. ELSE do9. 返回 BIN-Search(G, k, max)5.3.2 BIN-MCT 算法描述算法 4 给出了基于二分查找的算法BIN-MCT.首先,算法对结果集合T 进行初始化(第1 行). 然后,算法对双网络概念图进行核分解,找到kCTmax的上限,同时下限初始化为3(第2-3 行). 接下来,调用BIN-Search 函数求得kCTmax,在得到kCTmax 后调用KCT-FIND 算法发现所有MCT 子图(第4-5 行).BIN-Search 函数中,如果max-min1,则返回max(第1-4 行),并且将上下限的平均值作为参数传入KCT-FIND-NEW 函数;如果结果集为空,将上下限更新为min k,否则更新为k max,并递归调用BIN-Search 函数(第5-9 行).5.3.3 BIN-MCT 算法复杂度分析算法 4 计算 k-CT 子图最多花费O(| Eb |1.5 ´h)的运行时间,而且该过程最多被调用log2 maxuÎV (b (u))次,因此最坏时间复杂度为1.5O( Eb ´h´log2 maxuÎV(b (u))) . 该算法复杂度主要受以下两方面影响,一是k-CT 子图查找的时间,二是kCTmax 值相对于上下限的位置.5.4 算法优化从前面提出的三种MCT 子图发现算法中能够看出,BIN-MCT 算法主要从降低调用KCT-FINDNEW函数的次数来提高MCT 子图发现的效率. 但是,在多次调用函数的过程中依然会产生冗余计算.例如,在计算是否存在5-CT 6-CT 的过程中,需要重复删除仅属于3-CT 4-CT 的边. 为此,本小节算法优化的主要思想是,在计算是否存在k-CT 的过程中仅依赖于概念图中的k-truss 子图Tk(Gb),而不是整个双网络. 定理2 给出该思想的理论保证.定理 2. 给定双网络G(V, Ea , Eb )和正整数 k,那么V (k -CT(G)) ÍV (Tk (Gb )) .证明:Tk(Gb)表示概念图Gb 中的k-truss 子图,1730 计算 机 学 报 2020年由于 k-CT(G)同时要求在物理图中连通,约束更加严格,因此k-CT(G)的顶点集合一定被Tk(Gb)的顶点集合所包含,即V(k -CT(G)) ÍV (Tk (Gb )) . 证毕.从定理 2 能够轻松得出,如果Tk (Gb ) = Æ,那么k-CT(G)必然为空集. 因此,为了找到双网络中MCT子图,可以从概念图中非空k-truss 子图Tk(Gb)的顶点集合在双网络的诱导子图G[V(Tk(Gb))]中得到正确结果. 具体做法是,首先通过对概念图Gb 进行truss 分解,得到该图的k-类(定义3)索引. k-类索引的实质是按照每条边的truss 值对图中边进行划分,根据已知的 k-类,可以容易得到 ( ) UkmaxTk Gb = k Φk .然后以算法2 为例,BU-MCT 算法根据定理2 k-类索引可以优化为算法5,记为BU-MCT-OPT 算法. 同理,可以得到UB-MCT-OPT BIN-MCTOPT算法.算法5. BU-MCT-OPT.输入:G(V, Ea , Eb )输出:所有 MCT 子图结构T1. T 初始化为空集;2. Gb 进行truss 分解,求出{ Fk }3. kÜ34. ( ) UkmaxTk Gb = k Φk5. TÜKCT-FIND-NEW(G[V(Tk(Gb))], k)6. WHILET 不为空集do7. kÜk+18. TÜKCT-FIND-NEW ( G[V (Tk (Gb ) k )], k) 9. TÜKCT-FIND( G[V (Tk (Gb ) k -1)], k -1) 10. 返回T;下面通过一个示例解释算法5 的运行过程,如图9 所示. 首先图9(a)中给出了图4 中概念图的k-类索引,由图可知kmax=5. 首先,在53[ (Uk )]G V k Fk == 中计算3-CT. 如果3-CT 存在,则继续在5[ (U 4 )] kG V k Fk ==中计算4-CT,直到发现最大的MCT. 从图9(b)中可见虚线框内重复计算皆可省去,因此UB-MCT- OPT算法相较UB-MCT 算法能够在更小的子图空间中发现结果. 另外,值得注意的是,由于kCTmaxkmax,因此不能够直接在max G[V (Fk )]中发现 MCT.9 4 双网络k-类索引和BU-MCT-OPT 算法示例6 实验结果与分析6.1 实验环境配置本文分别用真实数据集和合成数据集对算法进行了测试,评估的算法包括k-CT 子图发现算法KCT-FINDMCT 子图发现算法BU-MCTUB-MCTBIN-MCT 以及其优化算法BU-MCT-OPT UB-MCT-OPT BIN-MCT-OPT. 本实验所用的软硬件环境如下:Windows 10 家庭版操作系统,Intel(R) Core(TM) i7-6700HQ CPU,主频2.6GHz8G 内存,1T 硬盘. 开发平台为JetBrains PyCharm2017,开发语言为Python 3.7.6.2 实验数据集实验一共采用了8 个数据集,4 个真实数据集和4 个合成数据集. 其中真实数据集包括:DBLPProteinEmail Facebook. 接下来介绍使用真实数据集构建的双网络,数据集统计信息如表1 所示.1 真实数据集双网络 顶点 V 物理边 Ea 概念边 Eb kCTmaxDBLP 20080 9342 140083 13Protein 8341 24392 58771 10Email 1005 16064 23544 101Facebook 4039 88243 109053 13(1) DBLP 双网络[12]:从DBLP 数据集中抽取SIGMODVLDBICDECIKMEDBTDASFAAKDDICDMSDMWSDM PAKDD 11 个数据库和数据挖掘领域著名国际会议近十年的发表的文章. 每篇文章可能存在多个作者,每个作者作为双网络中的一个顶点,在物理图中,将一篇文章内的所有作者两两建边,代表两者共同发表过论文,有现实联系. 概念图通过使用余弦函数度量两个作者论文关键字的相似程度,若相似度超过阈值则在概念图中两个作者之间建立边,代表两个作者有着相似的研究方向.(2) Protein 双网络[11]:蛋白质网络就是蛋白质之间的相互作用构成的. 每个蛋白质作为双网络中的顶点. 物理图中蛋白质之间的关系来自于蛋白质交互网络,表示两个蛋白质之间真实存在的物理关系.概念图中蛋白质之间的关系来自于高血压疾病遗传交互网络,如果两个蛋白质与高血压疾病具有显著的统计关联关系,则这两个蛋白质在概念图中存在边.(3) Email 双网络①:该双网络是由欧洲大型研究机构的电子邮件数据形成的,顶点代表电子邮件① http://snap.stanford.edu/data/index.html.9 期李 源等:一种大规模双网络中k-连通Truss 子图发现算法 1731用户,如两位用户之间发送过至少一封邮件,则在物理图中建边. 每位用户属于42 个部门之一,在概念图中将属于同一部门的任意两个用户之间建边.(4) Facebook 双网络[32]:通过分析Facebook 社交数据,双网络顶点代表用户,若两个用户相互关注,则在概念图中建边,若两个用户拥有相同的政治背景则在物理图中建边.合成数据集使用文献[10]中的算法生成,具体使用图生成器GTgraph(http://www.cse.psu.edu/~kxm85/software/GTgraph)生成物理图和概念图. 合成数据集统计信息如表2 所示.2 合成数据集图名称 顶点 V Ea EbSYN1 2´215 1´106SYN2 4´215 2´106SYN3 8´215 4´106SYN4 16´215 8´1066.3 算法性能分析本节主要评估本文提出的双网络中 k-CT 子图发现算法和不同MCT 子图发现算法在真实数据集和合成数据集中的运行效率和扩展性.6.3.1 k-CT 子图发现算法效率图 10 展示了k-CT 子图发现算法KCT-FIND 4 个真实数据集上的运行时间. 对于每个数据集,输入k 值分别取20%´kCTmax40%´kCTmax60%´kCTmax80%´kCTmax 以及kCTmax,其中kCTmax 为数据集的最大CT 数,如定义8 所示. 从图10 中可以看出随着k 值的不断增大,KCT-FIND 算法的运行时间不断变快. 分析原因主要是因为当k 值增大时,要求每条边被不同三角形包含的个数约束增加,从而导致满足条件边的数量大大降低,结果子图的规模也变小. 另外,由于k 值增大引起的约束变强,KCT-FIND 算法迭代的次数减少,这也导致算法能够更快终止.10 KCT-FIND 算法在不同数据集中运行时间6.3.2 MCT 子图发现算法效率本小节主要测试了 BU-MCTUB-MCT BINMCT算法以及其对应优化算法BU-MCT-OPTUBMCT-OPT BIN-MCT-OPT 在发现MCT 子图时的效率. 从图11(a)中可以看出,BIN-MCT 算法几乎在所有的真实数据集中运行速度最快,其次是UB-MCT 算法,运行速度最慢的是BU-MCT 算法. 但是,这里有一个特例,在Email 双网络中UB-MCT 算法的运行速度要快于BIN-MCT 算法,原因是UB-MCT 算法采用自顶向下策略,如果k 值上界与kCTmax 值相距非常近,UB-MCT 算法会在非常短的时间内结束,在这种情况下会优于BIN-MCT 算法. 从图11(b)展示的优化算法运行时间同样可以观察到类似结果. 另外,从图11(b)中还可以看出,优化后算法的运行时间要大大快于其对应的原始算法,原因是在使用了k-类索引后,可以从当前概念图中的k-truss 子图求出诱导子图,而不是每次都从整个双网络中搜索结果,大大降低了算法的搜索空间. 例如,BU-MCT-OPT 算法在DBLP 数据集上比优化前算法BU-MCT 快将近1 个数量级.11 在不同真实数据集中MCT 算法运行时间6.3.3 MCT 子图发现算法扩展性本小节主要评估BU-MCTUB-MCT 以及BINMCT算法的可扩展性. 在不同的真实双网络中,分别随机采样概念图中边 Eb 20%40%60%80%100%组成新的双网络,然后测试在不同网络上的运行时间.1732 计算 机 学 报 2020年图 12 不同真实数据集上的扩展性图 12 给出了BU-MCT-OPTUB-MCT-OPT BIN-MCT-OPT 算法在不同双网络中的运行时间.从结果中可以看出,当概念图中边数较少时,BUMCT-OPT 算法运行最快,原因是这时图中kCTmax值非常小. 然后随着边数的不断增加,BU-MCTOPT算法的运行时间增长很快,并且逐渐超过UBMCT-OPT BIN-MCT-OPT 算法. 当采样边数量的百分比变得更大时,BIN-MCT-OPT 算法运行速度优于其他两种算法,而且该算法随边数增加运行时间增加的速率不大,表现非常稳定,具良好可扩展性.为了分析BU-MCT-OPTUB-MCT-OPT BINMCT-OPT 算法在更大规模双网络上的可扩展性,这里采用表2 中列出的合成数据集进行测试.13 给出了在合成数据集上不同算法的运行效率. BIN-MCT-OPT 算法在不同顶点数量的双网络中的运行速度均为最快,其次是UB-MCT-OPT 算法,但是随着顶点数量的增加,BU-MCT-OPT 算法运行时间增长的更慢,并且最终几乎接近UB-MCT算法. 这种现象反映了虽然网络中边的数量也在增加,但是网络实际边数与完全图中边数的比值更低,说明图变得更加稀疏,因此kCTmax 值与其上界的距离更大,造成UB-MCT 算法运行时间增长速率更大.另外,从图中还能够看出,优化后的算法在一万秒的时间内能够处理顶点规模几十万,边规模几百万量级的双网络.13 合成数据集上MCT 算法运行时间为了进一步分析MCT 子图发现算法的可扩展性,本小节将BIN-MCT-OPT 算法与文献[12]中发现最大连通核子图MCCO 的算法BIN-MCCO 的运行效率进行比较.从图14 显示的结果可以看出,BIN-MCCO 算法的运行时间要略优于BIN-MCT-OPT 算法,这是因为发现kmax-核子图的时间复杂度要低于发现kmax-truss 子图的时间复杂度. 但是,BIN-MCT-OPT算法的运行时间为亚线性算法,在大图计算中也可以接受. 另外,从下节中有效性分析可以看出MCT子图要比MCCO 更加紧密,有效性也更高.9 期李 源等:一种大规模双网络中k-连通Truss 子图发现算法 173314 BIN-MCT-OPT BIN-MCCO 运行时间比较6.4 算法有效性分析从k-CT 子图定义可以看出使用k-truss 模型定义的双网络中子图相较于k-核模型定义的子图更加稠密. 本节使用经典的图密度和直径两种度量方法来比较本文提出的k-CT 子图模型和k-CCO子图[12]的稠密性. 图密度定义为图中出现边的数量与图中可能存在的所有边数量的比值,而图直径的定义为图中任意两个顶点间最短距离中的最大值[32]. 给定概念图中的诱导子图Gb[S],则Gb[S]的密度和直径分别表示为2[( )( ])( 1)bbE Sdens G SS S=-和 diam(Gb[S]) = maxu,vÎS dist(u,v),其中 dist(u, v)表示顶点之间的最短距离. 从上述定义可以看出子图密度越大,或是直径越小,都说明子图越稠密.15 不同真实数据集上的密度图 15 分别给出了MCCO 子图和MCT 子图在不同真实双网络中子图密度大小的比较. 这里将k-CCO 子图中k 值最大的子图记为MCCO 子图. 在不同的真实双网络中,分别随机采样概念图中边 Eb20%40%60%80%100%组成新的双网络,然后计算在不同网络上发现子图的密度. 从实验结果可以看出,MCT 子图在所有双网络的概念图中的密度都要大于MCCO 子图,原因是MCT 子图的定义要比MCCO 子图约束要更强,因此更加稠密.16 分别给出了MCCO 子图和MCT 子图在不同真实双网络中子图直径大小的比较. 在不同的真实双网络中,采用与密度实验相同的方法对概念图边进行采样,组成新的双网络,然后计算在不同网络上发现子图的直径. 从实验结果可以看出,从不同双网络中发现的MCCO MCT 子图,MCT 子图的直径都要小于MCCO 子图的直径,尤其在比较稀疏的双网络中,结果更加明显. 原因是MCT 子图要求子图中任意两条边之间都是三角形连通,因此也更加紧密. 综上可见,k-CT 子图具有更高的稠密程度,也证明了该子图模型的有效性.1734 计算 机 学 报 2020年图 16 不同真实数据集上的直径6.5 案例分析首先,图17 给出了DBLP 双网络中发现的真实k-CT 子图(8-CT. 概念图中,包括美国亚利桑那州立大学Huan Liu 教授在内的8 名学者都是在社交图 17 DBLP 双网络中发现的k-CT 子图媒体挖掘和机器学习领域非常知名的学者. 图中可以看出,这些学者具有相同的研究兴趣,因此在概念图中稠密;从物理图中能够看出,这8 名学者分别来自两个研究团队,其中Alok N. ChoudharyAnkit Agrawal Wei-keng Liao 来自于美国西北大学,而Jiliang TangSuhasRanganathSuhang WangXia Hu 都来自于Huan Liu 教授的研究团队. 而且这两个团队可以通过Huan Liu 教授而彼此认识. 如果需要举行一个小型的关于社交媒体挖掘的研讨会,该双网络中的学者是非常合适的.接下来,图18 给出了从蛋白质双网络中发现的k-CT 子图(7-CT). 在该图中,概念图表示与高血压疾病密切相关的遗传交互网络,物理图表示两个基因在蛋白质交互网络中实际存在的关联. 在结果显示的MCT 子图中,发现了4 个当前已知的与高血压疾病相关的基因,分别为MYO6GSTM3POU2F1 以及TP73,在图中已圈出. 例如,MYO6编码一种肌动蛋白的分子运动细胞,参与细胞内内小泡和细胞器的运输,显示与高血压有关[33]Tp73 编码肿瘤蛋白p53,它对不同的细胞压力做出反应,调节诱导细胞周期停滞、凋亡、衰老、DNA 修复和代谢改变的靶基因,在文献[34]中证明与高血压有关. 通过在蛋白质双网络中发现k-CT 子图,能够有效帮助致病基因检测和疾病通路发现.9 期李 源等:一种大规模双网络中k-连通Truss 子图发现算法 1735(a) 物理图(b) 概念图图 18 蛋白质双网络中发现的k-CT 子图7 总结与展望稠密子图发现是双网络分析中的重要问题并且受到广泛关注. 针对现有稠密子图模型发现效率低和稠密度差的问题,本文提出一种k-连通truss 子图模型,该模型不仅更加稠密而且允许子图间的重叠,同时能够在亚线性时间内发现子图. 首先,本文提出了高效的KCT-FIND 算法来发现指定k k-CT子图. 接下来,分别提出了三种不同策略的算法来发现双网络中最大连通truss(MCT)子图,并进行了相应优化. 最后,大量在真实和合成数据集上的实验验证了本文提出模型和算法的高效性和有效性.未来还需要设计更加通用的算法来满足各种稠密子

[返回]
上一篇:一种面向安全关键软件的AADL模型组合验证方法_张博林
下一篇:用于去除随机脉冲噪声的两阶段盲卷积降噪模型_徐少平