复杂网络中基于WCC的并行可扩展社团挖掘算法  

WCC-BASED PARALLEL AND SCALABLE COMMUNITY MINING ALGORITHM IN COMPLEX NETWORKS

作　　者：亚森.艾则孜 李卫平[2] 郭文强[3] Yasen ·Aizezi;Li Weiping;Guo Wenqiang(Department of Information Security and Engineering, Xinjiang Police College, Urumqi 830013 , Xinjiang, China;Department of Police Technology,Railway Police College,Zhengzhou 450053 ,Henan,China;School of Computer Science and Engineering, Xinjiang University of Finance and Economic, Urumqi 830013 , Xinjiang, China)

机构地区：[1]新疆警察学院信息安全工程系,新疆乌鲁木齐830013 [2]铁道警察学院公安技术系,河南郑州450053 [3]新疆财经大学计算机科学与工程学院,新疆乌鲁木齐830013

出　　处：《计算机应用与软件》2016年第6期37-39,43,共4页Computer Applications and Software

基　　金：国家自然科学基金项目(61163066;60902074);新疆维吾尔自治区高校科研计划科学研究重点项目(XJEDU2013134);国家社会科学基金项目(13CFX055);河南省教育厅科学技术研究重点项目(14A520011)

摘　　要：WCC(Weighted Community Clustering)通过复杂网络中社团含有的三角数量来评价社团挖掘算法的性能。在原始的WCC算法中,需要在每次迭代中对所有的社团变化计算WCC值,因而计算量非常大。为了减小社团变化带来的WCC计算量,提出一种并行可扩展的社团挖掘算法。对应用WCC进行社团评价的方法进行分析,提出一种包含预处理、初始划分和划分改进三个阶段的并行社团挖掘算法。在划分改进中,由于每次社团变化都需要计算大量的WCC提升,基于社团的统计量提出一种WCC近似计算方法。大量的真实数据集实验表明,提出的社团挖掘算法与相关算法相比较,不仅社团检测的准确性更高,而且具有更好的并行可扩展性。Weighted community clustering ( WCC) evaluates the performance of community mining algorithms according to triangles number of a community in complex networks. In primitive WCC algorithm it has the need to compute WCC scores for all community changes in each iteration, therefore the computation burden is very heavy. In order to minimise WCC computation brought about by communities change, this paper proposes a parallel and scalable community mining algorithm. We analysed the methods of community evaluation using WCC, and proposed a parallel community mining algorithm including three stages of preprocessing, initial partitioning and partition refinement. During the process of partition refinement, since every change in community needs much computation for WCC improvements, so we proposed a WCC approximated computation algorithm based on the statistics of community. Massive experiments on real datasets show that, the proposed community mining algorithm is more accurate and has better scalability than related works.

关 键 词：复杂网络 社团挖掘 并行算法 可扩展性 

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