面向二部图的极大缺陷二团高效枚举算法

1

作者 代强强 于瀚文 +2 位作者 李荣华 李振军 王国仁 《软件学报》 北大核心 2025年第4期1796-1810,共15页

极大二团枚举问题是二部图分析中的一个基本研究问题.然而,在实际应用中,传统二团模型要求子图必须为完全二部图的约束往往过于严格,因此需要一些更为宽松的二团模型作为代替.为此,提出一种新的称之为k-缺陷二团的松弛二团模型.该模型... 极大二团枚举问题是二部图分析中的一个基本研究问题.然而,在实际应用中,传统二团模型要求子图必须为完全二部图的约束往往过于严格,因此需要一些更为宽松的二团模型作为代替.为此,提出一种新的称之为k-缺陷二团的松弛二团模型.该模型允许二部图子图与完全子图二团最多相差k条边.由于极大k-缺陷二团枚举问题属于NP-难问题,设计高效的枚举算法是一项极具挑战性的任务.为解决此问题,提出一种基于对称集合枚举的算法.该算法的思想是通过k-缺陷二团中缺失边的数量约束来控制子分支的数量.为进一步提高计算效率,还提出一系列优化技术,包括基于排序的子图划分方法、基于上界的剪枝方法、基于线性时间的更新技术以及分支的优化方法.此外,提出的优化算法的时间复杂度与量的实验结果表明,在大部分参数条件下所提方法的效率相较于传统分支定界方法提高了100倍以上. 展开更多

关键词 二部图 稠密子图挖掘 k-缺陷二团

在线阅读 下载PDF 职称材料

不确定图上的kNN查询处理 被引量：7

2

作者 张应龙 李翠平 +1 位作者 陈红 杜凌霞 《计算机研究与发展》 EI CSCD 北大核心 2011年第10期1850-1858,共9页

在现实中的许多领域产生大量不确定的图结构的数据,例如分子化合物、蛋白质交互网络等.同时现实中有很多应用例如推荐系统中的推荐过滤、欺诈检测和社会网络的链接预测等,需要查询给定节点的k个最相似节点,针对这一问题,提出了用基于Sim... 在现实中的许多领域产生大量不确定的图结构的数据,例如分子化合物、蛋白质交互网络等.同时现实中有很多应用例如推荐系统中的推荐过滤、欺诈检测和社会网络的链接预测等,需要查询给定节点的k个最相似节点,针对这一问题,提出了用基于SimRank度量的方法来求解.由于图的动态演变和不确定性导致用现有的SimRank计算方法求k个最近邻的代价昂贵,因此提出一个有效算法,在保证一定准确性的前提下,通过引入路径阈值,算法只需考虑查询点的邻居区域无需考虑整个图从而达到明显的剪枝效果,该方法在确定图和不确定图上都可以适用.在此基础上为了进一步提高效率,算法在不确定图上引入采样技术.最后从理论、实验说明验证了算法的高效性和有效性. 展开更多

关键词 不确定图 可能世界 SIMRANK KNN 子图

在线阅读 下载PDF 职称材料

基于d-邻域子图匿名的社会网络隐私保护 被引量：2

3

作者 金华 张志祥 +1 位作者 刘善成 鞠时光 《计算机应用研究》 CSCD 北大核心 2011年第11期4322-4325,共4页

社会网络分析可能会侵害到个体的隐私信息,需要在发布的同时进行隐私保护。针对社会网络发布中存在的邻域攻击问题,提出了基于超边矩阵表示的d-邻域子图k-匿名模型。该模型采用矩阵表示顶点的d-邻域子图,通过矩阵的匹配来实现子图的k-匿... 社会网络分析可能会侵害到个体的隐私信息,需要在发布的同时进行隐私保护。针对社会网络发布中存在的邻域攻击问题,提出了基于超边矩阵表示的d-邻域子图k-匿名模型。该模型采用矩阵表示顶点的d-邻域子图,通过矩阵的匹配来实现子图的k-匿名,使得匿名化网络中的每个节点都拥有不少于k个同构的d-邻域子图。实验结果表明该模型能够有效地抵制邻域攻击,保护隐私信息。 展开更多

关键词 社会网络 隐私保护 d-邻域子图 K-匿名

在线阅读 下载PDF 职称材料

邻居子图扰动下的k-度匿名隐私保护模型 被引量：1

4

作者 丁红发 唐明丽 +3 位作者 刘海 蒋合领 傅培旺 于莹莹 《西安电子科技大学学报》 EI CAS CSCD 北大核心 2023年第4期180-193,共14页

大规模图数据在商业和学术研究中应用广泛,在其共享发布场景中隐私保护极为重要。现有的匿名隐私保护模型难以有效解决图数据隐私保护和数据效用间的冲突问题。针对此问题,基于邻居子图扰动提出一种增强隐私保护程度和数据效用水平的k... 大规模图数据在商业和学术研究中应用广泛,在其共享发布场景中隐私保护极为重要。现有的匿名隐私保护模型难以有效解决图数据隐私保护和数据效用间的冲突问题。针对此问题,基于邻居子图扰动提出一种增强隐私保护程度和数据效用水平的k度匿名隐私保护模型。首先,该模型利用邻居子图扰动机制优化扰动图数据节点的1-邻居子图,提高扰动效率并减少数据效用损失;其次,利用分治策略并依据节点度序列实现对节点匿名组的优化划分,提高匿名图数据的效用;最后,采用边修改和子图边缘修改的策略重构匿名图数据,实现图数据k度匿名隐私保护。对比和实验结果表明,所提出模型比现有模型在计算开销和安全性方面有了较大提升,能够同时抗节点度攻击和邻居子图攻击,在边变化比例、信息损失、平均节点度变化和聚类系数等指标方面数据效用显著提升。 展开更多

关键词 隐私保护技术 图结构 匿名 k-度匿名 邻居子图

在线阅读 下载PDF 职称材料

关于k-消去图的若干新结果 被引量：1

5

作者 汪长平 《数学物理学报（A辑）》 CSCD 北大核心 1998年第3期302-309,共8页

设G是一个图．k是自然数．图G的一个k-正则支撑子图称为G的一个k-因子．若对于G的每条边e．G—e都存在一个k-因子，则称G是一个k-消去图．该文得到了一个图是k-消去图的若干充分条件，推广了文［2—4］中有关结论．

关键词 图 支撑子图 K-因子 K-消去图

在线阅读 下载PDF 职称材料

基于图模式的犯罪情报数据集挖掘算法 被引量：1

6

作者 唐德权 史伟奇 刘绪崇 《中国人民公安大学学报（自然科学版）》 2021年第3期74-78,共5页

从图模式中挖掘频繁子图的最大挑战是候选模式的大量产生,特别在大型图模式的情报数据集中,以至于合理的计算资源无法完整枚举频繁子图的总数。文中提出一种基于图模式的犯罪情报数据集挖掘k-频繁子图算法。首先,将图模式进行预处理得到... 从图模式中挖掘频繁子图的最大挑战是候选模式的大量产生,特别在大型图模式的情报数据集中,以至于合理的计算资源无法完整枚举频繁子图的总数。文中提出一种基于图模式的犯罪情报数据集挖掘k-频繁子图算法。首先,将图模式进行预处理得到k个顶点子图的新数据集;然后,从新图模式集中获得所有k个顶点的生成子图;最后,通过k顶点的生成子模式得到k-频繁子图,在真实犯罪情报数据集上验证了算法的有效性。 展开更多

关键词 图模式 数据挖掘 生成子图 k-频繁子图

在线阅读 下载PDF 职称材料

带权不确定图的K最近邻查询算法 被引量：3

7

作者 黄冬梅 邓斌 赵丹枫 《计算机应用与软件》 CSCD 2016年第2期212-216,263,共6页

社交、移动等复杂网络节点接入的不确定性给数据查询处理带来了新的挑战。K最近邻查询是社交、移动网络中经常用到的操作。已有的方法首先将网络映射为不确定图,然后,考虑边只含有概率信息的情况。讨论了K最近邻查询方法,没有考虑权重信... 社交、移动等复杂网络节点接入的不确定性给数据查询处理带来了新的挑战。K最近邻查询是社交、移动网络中经常用到的操作。已有的方法首先将网络映射为不确定图,然后,考虑边只含有概率信息的情况。讨论了K最近邻查询方法,没有考虑权重信息,具有局限性。针对这个问题,定义了带权不确定子图和Pro Wei Dist距离,兼顾权重和概率两个要素,提出了针对带权不确定图的K最近邻查询算法,并对算法进行优化。实验结果表明,Sub Dist K算法能有效地解决K最近邻查询问题。 展开更多

关键词 复杂网络 不确定数据 K最近邻查询 带权不确定图 子图

在线阅读 下载PDF 职称材料

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

8

作者 李源 盛飞 +2 位作者 孙晶 赵宇海 王国仁 《计算机学报》 EI CSCD 北大核心 2020年第9期1721-1736,共16页

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

在线阅读 下载PDF 职称材料

大规模不确定图上的Top-k极大团挖掘算法 被引量：4

9

作者 邹兆年 朱鎔 《计算机学报》 EI CSCD 北大核心 2013年第10期2146-2155,共10页

该文研究了从不确定图中挖掘出前k个出现概率最高的极大团的问题,提出了一种基于划分的高效并行算法.在该算法中,输入的大规模不确定图首先被划分为若干互不重叠的规模较小的子图,每个子图通过扩展邻居结点信息成为扩展子图.而后,应用... 该文研究了从不确定图中挖掘出前k个出现概率最高的极大团的问题,提出了一种基于划分的高效并行算法.在该算法中,输入的大规模不确定图首先被划分为若干互不重叠的规模较小的子图,每个子图通过扩展邻居结点信息成为扩展子图.而后,应用改进后的分支界限搜索策略,并行挖掘各个扩展子图,以得到局部top-k结果.最后,归并所有的局部top-k结果,得到全局top-k极大团.同时,该文还提出了两种预处理策略,以提高算法效率.并且严格证明了算法的正确性.在多组不确定图数据集上的实验结果表明,算法具有很高的效率和很好的实用性. 展开更多

关键词 不确定图 top—k极大团 图划分算法 扩展子图

在线阅读 下载PDF 职称材料

以子图为根的k距局部子图的可重构性

10

作者 谢力同 宋慧敏 刘桂真 《应用数学》 CSCD 北大核心 2002年第4期114-119,共6页

本文定义了图中以某个图为根的k距局部子图 ,证明了图中同构于上述k距局部子图的子图的数目是可重构的 ,从而给出了一个新结果并推广了文献[5] 中的定理 .

关键词 可重构性 核子图 k距局部子图

在线阅读 下载PDF 职称材料

基于贪婪策略的紧密k核子图查询 被引量：1

11

作者 赵丹枫 姚贤标 +2 位作者 包晓光 黄冬梅 郭伟其 《计算机工程》 CAS CSCD 北大核心 2022年第10期55-66,共12页

k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k... k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询(CRKSQ)问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8%以内。 展开更多

关键词 社团检测 k核 加权图 紧密子图 贪婪策略

在线阅读 下载PDF 职称材料

稠密k-子图问题的双非负松弛

12

作者 郭传好 单而芳 《运筹与管理》 CSSCI CSCD 北大核心 2015年第5期144-150,共7页

稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模... 稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。 展开更多

关键词 组合优化 双非负松弛 半定松弛 稠密k-子图

在线阅读 下载PDF 职称材料

基于k-频繁子图聚类的二分图匿名方法

13

作者 吴宏伟 张健沛 杨静 《计算机工程与应用》 CSCD 2013年第17期18-23,37,共7页

针对以二分图形式发布的社会网络隐私泄露问题,提出了一种面向敏感边识别攻击的社会网络二分图匿名方法。在已有k-安全分组的理论基础上,结合二分图的稀疏性和敏感边识别攻击形式,分别提出了正单向、逆单向以及完全(c1,c2)-安全性原则,... 针对以二分图形式发布的社会网络隐私泄露问题,提出了一种面向敏感边识别攻击的社会网络二分图匿名方法。在已有k-安全分组的理论基础上,结合二分图的稀疏性和敏感边识别攻击形式,分别提出了正单向、逆单向以及完全(c1,c2)-安全性原则,并在此基础上,形式化地定义了一类抗敏感边识别攻击的社会网络二分图安全匿名问题;同时,还提出了一种基于k-频繁子图聚类的二分图划分算法和一种基于二分图(c1,c2)-安全性的匿名算法来保证发布二分图的安全性。实验结果表明,该算法在与已有方法相当时间开销的前提下,能产生更小的信息损失度,有效地抵制了敏感边识别攻击,实现了二分图的安全发布。 展开更多

关键词 社会网络 隐私匿名 聚类 敏感边识别攻击 k-频繁子图

在线阅读 下载PDF 职称材料

顶点距离大于2的局部化条件与ham iltonian图

14

作者 毛林繁 刘峰 《河南师范大学学报（自然科学版）》 CAS CSCD 2003年第1期17-21,共5页

对任意正整数 i,若图 G的导出子图 L的顶点满足 : x,y∈ V(L ) ,d L(x,y) =i m ax{ d G(x) ,d G(y) } |G|/ 2 ,则称 L具有性质 DL(i) .设 C(G)为图 G的闭包 ,本文证明了下述结果 :任意一个 C(G) =G且边连通度≥3的 2 -连通图 ,若存在正... 对任意正整数 i,若图 G的导出子图 L的顶点满足 : x,y∈ V(L ) ,d L(x,y) =i m ax{ d G(x) ,d G(y) } |G|/ 2 ,则称 L具有性质 DL(i) .设 C(G)为图 G的闭包 ,本文证明了下述结果 :任意一个 C(G) =G且边连通度≥3的 2 -连通图 ,若存在正整数 s使得 G中的导出子图 L满足 :(i) L K1 .3 有性质 DL(2 ) ;(ii)任意正整数 i,1 i s,L Bi 有性质 DL(i) ;(iii) L Zs+ 2 有性质 DL(s+2 ) ,则 G为 hamiltonian图 .由此得到 :每个边连通度≥ 3的 2 -连通 { K1 .3;Bi,1 i s} - f ree图 ,若 C(G) =G且 max{ d G(x) ,d G(y)对任意导出子图 L Zs+ 2 ,d L(x,y) =s+2 } |G|/ 2 ,则 G一定是 hamiltonian图 .从而 展开更多

关键词 顶点距离 局部化条件 HAMILTONIAN图 性质DL(κ) 导出子图 最长圈 连通图

在线阅读 下载PDF 职称材料

双网络中影响力凝聚子图发现算法

15

作者 李源 杨森 +2 位作者 孙晶 赵会群 王国仁 《计算机研究与发展》 EI CSCD 北大核心 2023年第9期2096-2114,共19页

双网络由物理图和概念图构成,其中物理图和概念图共享网络结点集合而具有不同边集合.物理图中边表示结点间实际存在的关系;概念图中边表示结点间的相似程度,通常由计算得出.最近,从双网络中发现凝聚子图,即物理图中连通且概念图中稠密... 双网络由物理图和概念图构成,其中物理图和概念图共享网络结点集合而具有不同边集合.物理图中边表示结点间实际存在的关系;概念图中边表示结点间的相似程度,通常由计算得出.最近,从双网络中发现凝聚子图,即物理图中连通且概念图中稠密的子图受到研究者的广泛关注,在研讨会筹备、商品推荐和致病基因发现等真实场景中具有广泛应用.但现有研究鲜有考虑双网络中凝聚子图的影响力.为此: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索引 双网络 图数据挖掘

在线阅读 下载PDF 职称材料

大规模标签图中的动态Top-K兴趣子图查询

16

作者 宋宝燕 贾春杰 +2 位作者 单晓欢 丁琳琳 丁兴艳 《计算机应用》 CSCD 北大核心 2018年第2期471-477,共7页

针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法 DISQtop-K。该方法建立了包括节点拓扑结构特性(NTF)索引和边特性(EF)索引... 针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法 DISQtop-K。该方法建立了包括节点拓扑结构特性(NTF)索引和边特性(EF)索引的图拓扑结构特性(GTSF)索引,利用该索引可有效剪枝过滤不满足限制条件的无效节点及边;基于GTSF索引提出了多因素候选集过滤策略,通过对查询图候选集进一步剪枝以获得较少的候选集;考虑到图的动态变化可能对匹配结果产生影响,提出了Top-K兴趣子图匹配验证方法——DISQtop-K,将匹配验证过程分为初始匹配和动态修正两个阶段,以尽可能保证查询结果的实时、准确。大量实验结果表明,相比RAM、RWM算法,DISQtop-K方法的索引创建时间较短且占用空间较少,能有效处理大规模标签图中的动态Top-K兴趣子图查询。 展开更多

关键词 大规模标签图 动态Top-K 兴趣子图 子图查询

在线阅读 下载PDF 职称材料

Duffus等人的结果的一个推广

17

作者 胡智全 郑德印 《华中师范大学学报（自然科学版）》 CAS CSCD 北大核心 1998年第1期17-19,共3页

证明了下述结果：设Ｆ是度序列为（１，１，１，３，３，３）的简单图，Ｆ中度为１的点记为ａ１，ａ２和ａ３；Ｇ为连通无爪图．若Ｇ的每一个与Ｆ同构的导出子图均满足性质（ａ１，ａ２）和（ａ１，ａ３），或（ａ１，ａ２）和... 证明了下述结果：设Ｆ是度序列为（１，１，１，３，３，３）的简单图，Ｆ中度为１的点记为ａ１，ａ２和ａ３；Ｇ为连通无爪图．若Ｇ的每一个与Ｆ同构的导出子图均满足性质（ａ１，ａ２）和（ａ１，ａ３），或（ａ１，ａ２）和（ａ２，ａ３），或（ａ１，ａ３）和（ａ２，ａ３），则Ｇ有哈密顿路． 展开更多

关键词 哈密顿路 导出子图 无爪图

在线阅读 下载PDF 职称材料

关于k-覆盖图的一些新结果

18

作者 汪长平 纪昌明 《应用数学》 CSCD 1998年第1期61-64,共4页

本文给出了一个图G是k-覆盖图的若干充分条件．

关键词 支撑子图 覆盖图 图 K-覆盖图 无向图

在线阅读 下载PDF 职称材料

异构属性网络中统计显著密集子图发现算法研究

19

作者 李源 范晓林 +1 位作者 孙晶 赵宇海 《小型微型计算机系统》 CSCD 北大核心 2021年第10期2203-2210,共8页

密集子图体现了大图中的稠密部分,它是图中具有最高密度的子图,这使得它在事件检测,生物分析和社区发现等方面具有广泛应用和实用价值.现有的密集子图发现方法所使用的图模型描述不够详细,并且发现的密集子图缺乏统计显著性.为了解决以... 密集子图体现了大图中的稠密部分,它是图中具有最高密度的子图,这使得它在事件检测,生物分析和社区发现等方面具有广泛应用和实用价值.现有的密集子图发现方法所使用的图模型描述不够详细,并且发现的密集子图缺乏统计显著性.为了解决以上问题,本文提出了异构属性网络这一新模型,然后在异构属性网络上通过非参数扫描统计和基于(k,Ψ)-核的方法发现高Steiner连通度的统计显著密集子图.首先构建异构属性网络,其包括类型、实体、关系和带有时序关系的属性信息;其次通过历史属性信息计算异构属性网络中每个实体的统计值,形成统计权重网络;然后利用非参数扫描统计方法测量统计权重网络中子图的统计显著性;最后由于此问题是NP-难的,于是提出了基于(k,Ψ)-核的局部扩展的近似统计显著密集子图发现算法.大量基于真实异构属性网络数据的实验结果证明了本文所提出算法的有效性和高效性. 展开更多

关键词 异构属性网络 密集子图 统计显著性 (k Ψ)-核

在线阅读 下载PDF 职称材料

异质信息网络中最大路径连通Steiner分量查询算法

20

作者 李源 范晓林 +3 位作者 孙晶 赵会群 杨森 王国仁 《软件学报》 EI CSCD 北大核心 2023年第2期655-675,共21页

异质信息网络(HINs)是包含多种类型对象(顶点)和链接(边)的有向图,能够表达丰富复杂的语义和结构信息.HINs中的稠密子图查询问题,即给定一个查询点q,在HINs中查询包含q的稠密子图,已成为该领域的热点和重点研究问题,并在活动策划、生物... 异质信息网络(HINs)是包含多种类型对象(顶点)和链接(边)的有向图,能够表达丰富复杂的语义和结构信息.HINs中的稠密子图查询问题,即给定一个查询点q,在HINs中查询包含q的稠密子图,已成为该领域的热点和重点研究问题,并在活动策划、生物分析和商品推荐等领域具有广泛应用.但现有方法主要存在以下两个问题:(1)基于模体团和关系约束查询的稠密子图具有多种类型顶点,导致其不能解决仅关注某种特定类型顶点的场景;(2)基于元路径的方法虽然可查询到某种特定类型顶点的稠密子图,但其忽略了子图中顶点之间基于元路径的连通度.为此,首先在HINs中提出了基于元路径的边不相交路径的连通度,即路径连通度;然后,基于路径连通度提出了k-路径连通分量(k-PCC)模型,该模型要求子图的路径连通度至少为k;其次,基于k-PCC模型提出了最大路径连通Steiner分量(SMPCC)概念,其为包含q的具有最大路径连通度的k-PCC;最后,提出一种高效的基于图分解的k-PCC发现算法,并在此基础上提出了优化查询SMPCC算法.大量基于真实和合成HINs数据的实验结果验证了所提出模型和算法的有效性和高效性. 展开更多

关键词 异质信息网络 稠密子图查询 k-路径连通分量 最大路径连通Steiner分量 元路径

在线阅读 下载PDF 职称材料