大规模不确定图上的Top-k极大团挖掘算法  

Mining Top-k Maximal Cliques from Large Uncertain Graphs

作　　者：邹兆年[1] 朱鎔 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机学报》2013年第10期2146-2155,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(61173023);中央高校基本科研业务费专项资金(HIT.NSRIF.201180)资助~~

摘　　要：该文研究了从不确定图中挖掘出前k个出现概率最高的极大团的问题,提出了一种基于划分的高效并行算法.在该算法中,输入的大规模不确定图首先被划分为若干互不重叠的规模较小的子图,每个子图通过扩展邻居结点信息成为扩展子图.而后,应用改进后的分支界限搜索策略,并行挖掘各个扩展子图,以得到局部top-k结果.最后,归并所有的局部top-k结果,得到全局top-k极大团.同时,该文还提出了两种预处理策略,以提高算法效率.并且严格证明了算法的正确性.在多组不确定图数据集上的实验结果表明,算法具有很高的效率和很好的实用性.This paper investigates the problem of mining k top-ranked vertex subsets in an uncertain graph which have the highest probabilities of being maximal cliques in practice. A decomposition-based algorithm taking advantage of parallelism is proposed to solve the problem on large uncertain graphs. In the algorithm, the input large uncertain graph is firstly decomposed into some disjoint subgraphs in much smaller scale by an efficient graph division algorithm, and subgraphs are then extended to be extension subgraphs by bringing some adjacent vertices in. Then, local top-k results of maximal cliques are obtained on each extension subgraph in parallel by a mining algorithm adopting branch and bound search method. Finally, the local results are merged together to get the final top-k maximal cliques in the global input uncertain graph. Moreover, we provide two preprocessing methods to improve the algorithm＇s efficiency by decreasing the input graph size. It is proved that the algorithm could guarantee the completeness and correctness of the final mining results. Also, extensive experiments are made across several uncertain graph datasets to evaluate our algorithm. It＇s shown that the algorithm is both effective and efficient. Experiment results verify that this algorithm is of great significance in real applications.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]