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

Efficient k-Clique Mining Algorithm in Large-scale Networks

网络结构中的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.