| 一种高效的大规模网络k团挖掘算法 |
| |
| 引用本文： | 柴旭清,董永亮. 一种高效的大规模网络k团挖掘算法[J]. 计算机科学, 2016, 43(5): 265-268 |
| |
| 作者姓名： | 柴旭清 董永亮 |
| |
| 作者单位： | 河南师范大学 新乡453000,河南师范大学 新乡453000 |
| |
| 基金项目： | 本文受河南省科技厅资助 |
| |
| 摘 要： | 网络结构中的k团挖掘是各种基于网络的应用的基础问题之一。针对大规模网络k团挖掘效率低的问题,提出了一种高效的大规模网络k团挖掘算法。首先,将寻找最大密度的k团问题进一步转化为寻找超过给定密度值k团的问题。然后,以网络中的顶点和k－1团顶点为两类顶点构建二部图,并证明应用二部图可以在多项式时间内求解k团问题。在稀疏网络中,提出的算法的时间和空间复杂度分别为O(c2k)和O(ck)。实验表明,提出的算法与目前最优的算法相比能更准确地挖掘大规模网络中的k团,并且具有更高的运行效率。此外,提出的算法可应用于不完全网络中的k团挖掘。
|
| 关 键 词： | 社团挖掘 社会网络 k团 不完全网络 |
| 收稿时间： | 2015-11-27 |
| 修稿时间： | 2015-12-21 |
Efficient k-Clique Mining Algorithm in Large-scale Networks |
| |
| CHAI Xu-qing and DONG Yong-liang. Efficient k-Clique Mining Algorithm in Large-scale Networks[J]. Computer Science, 2016, 43(5): 265-268 |
| |
| Authors: | CHAI Xu-qing and DONG Yong-liang |
| |
| Affiliation: | Henan Normal University,Xinxiang 453000,China and Henan Normal University,Xinxiang 453000,China |
| |
| Abstract: | |
| |
| Keywords: | Community mining Social networks k-clique Incomplete network |
|
|
点击此处可从《计算机科学》下载全文 |
|
