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

摘要：

网络结构中的k团挖掘是各种基于网络的应用的基础问题之一.针对大规模网络k团挖掘效率低的问题,提出了一种高效的大规模网络k团挖掘算法.首先,将寻找最大密度的k团问题进一步转化为寻找超过给定密度值k团的问题.然后,以网络中的顶点和k-1团顶点为两类顶点构建二部图,并证明应用二部图可以在多项式时间内求解k团问题.在稀疏网络中,提出的算法的时间和空间复杂度分别为O(c2k)和O(ck).实验表明,提出的算法与目前最优的算法相比能更准确地挖掘大规模网络中的k团,并且具有更高的运行效率.此外,提出的算法可应用于不完全网络中的k团挖掘.

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

所属期刊栏目：43

分类号：TP391(计算技术、计算机技术)

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

在线出版日期：2016-07-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：265-268