一种高效的概率图上Top-K极大团枚举算法  

An Efficient TOP-K Maximal Clique Enumeration Algorithm on Uncertain Graphs

作　　者：王恒 周军锋 杜明[1] WANG Heng;ZHOU Junfeng;DU Ming(Donghua University,Songjiang,Shanghai 201620,China)

机构地区：[1]东华大学,上海201620

出　　处：《新一代信息技术》2021年第8期1-10,共10页New Generation of Information Technology

摘　　要：极大团是稠密子图的一种,概率图上的Top-K极大团枚举用于从给定图中挖掘团概率最大的前K个团,对社交网络、蛋白质作用网络等方面的研究有重大意义。然而,由于极大团的概率会随着顶点规模的变大而不断减小,现有概率图上Top-K极大团枚举算法会丢失顶点规模大而概率较小的极大团,这些丢失的极大团规模较大,在实际中具有重要的应用价值。本文重新定义了概率图上的Top-K极大团枚举问题,用于返回团概率大于给定阈值的前K个规模最大的极大团。在此基础上,提出了一种在概率图上枚举Top-K极大团的算法Top-KC。本文还针对Top-KC算法提出了两种优化策略。基于多个真实数据集的实验结果表明,两种优化策略都能够有效地提高枚举效率。The maximal clique is a kind of dense subgraph.The Top-K maximal clique enumeration on the uncertain graph is used to mine the top K cliques with the highest probability from a given graph,which is useful for social networks,protein interaction networks,etc.The research is of great significance.However,since the probability of maximal clique will continue to decrease as the size of the vertices becomes larger,the Top-K maximal clique enumeration algorithm on the existing uncertain graph will lose the maximal cliques with large scale and small probabilities.The lost maximal cliques are larger in scale and have important application value in practice.This paper redefines the Top-K maximal clique enumeration problem on the uncertain graph,which is used to return the top K maximal cliques with the largest scale whose probability value is greater than a given threshold.On this basis,an algorithm Top-KC that enumerates Top-K maximal cliques on the uncertain graph is proposed.The article also proposes two optimization strategies for the Top-KC algorithm.Experimental results based on multiple real data sets show that both optimization strategies can improve the enumeration efficiency.

关 键 词：概率图 Top-K极大团枚举 顶点规模 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]