一种高效的大规模网络k团挖掘算法  

Efficient k-Clique Mining Algorithm in Large-scale Networks

作　　者：柴旭清[1] 董永亮[1] 

机构地区：[1]河南师范大学,新乡453000

出　　处：《计算机科学》2016年第5期265-268,共4页Computer Science

基　　金：河南省科技厅资助性项目(9412012Y0004;9412012Y0005);河南省教育厅项目(13A510520;2013-gh-12;14A520053;SKL-2014-795)资助

摘　　要：网络结构中的k团挖掘是各种基于网络的应用的基础问题之一。针对大规模网络k团挖掘效率低的问题,提出了一种高效的大规模网络k团挖掘算法。首先,将寻找最大密度的k团问题进一步转化为寻找超过给定密度值k团的问题。然后,以网络中的顶点和k-1团顶点为两类顶点构建二部图,并证明应用二部图可以在多项式时间内求解k团问题。在稀疏网络中,提出的算法的时间和空间复杂度分别为O(c2k)和O(ck)。实验表明,提出的算法与目前最优的算法相比能更准确地挖掘大规模网络中的k团,并且具有更高的运行效率。此外,提出的算法可应用于不完全网络中的k团挖掘。k-clique mining in networks is a basis for most network-based applications.Concerning the problem of low efficiency for mining k-cliques,this paper proposed an efficient k-clique mining algorithm for large-scale networks.Firstly,the problem of finding k-clique with maximal density is transformed to the problem of finding a k-clique whose density is larger than a given density value.Next,a bipartite network,whose left nodes are nodes in the original network and right nodes are k-1cliques,is constructed,and the k-cliques problem can be solved within polynomial time applying it.In sparse networks,the time and space complexities of the proposed algorithm are O（c2k）and O（ck）respectively.The experiments show that,the proposed algorithm is more accurate and efficient than the best algorithm at present.Moreover,the proposed algorithm can be also applied to mine k-cliques in incomplete networks.

关 键 词：社团挖掘 社会网络 k团 不完全网络 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]