Louvain算法的并行化处理  

Parallel Processingof the Louvain Algorithm

作　　者：吴卫江[1] 李沐南 李国和[1] 

机构地区：[1]中国石油大学(北京)地球物理与信息工程学院,北京102200

出　　处：《计算机与数字工程》2016年第8期1402-1406,共5页Computer & Digital Engineering

基　　金：国家自然基金项目(编号:60473125)资助

摘　　要：社团结构作为复杂网络的一个重要特征,被广泛应用到物理、生物、计算机以及社会学等领域。在实际应用中,社团发现算法的效率与社团划分结果的准确性对挖掘网络特性十分关键。Louvain算法是一种基于模块度的快速凝聚算法,能够准确划分出层次社团。在研究Louvain算法的基础上,针对算法主要耗时在计算模块度与遍历模块度增量上的问题,提出并行化的处理方法改进算法的运算效率,并应用改进后的算法在分布式系统上处理包含上千节点的Facebook数据集,通过对比原算法的运行结果,发现在社团划分效果准确的基础上,改进的并行化算法效率更优。Community structure is an important property of complex networks, which is widely used in the fields of physics, biology, computer and sociology. In a practical application, the efficiency of the community detect algorithm and the accuracy of the results are very important. The Louvain algorithm is a clustering algorithm finding hierarchical community structure based on the modularity function, which has good efficiency and accuracy. Based on the research of the Louvain al-gorithm, the parallel processing method is used to find a more efficient algorithm. And the data set is processed with thou-sands of nodes by using the Louvain algorithm and the improved algorithm on the distributed system, it is found that the im-proved algorithm is more efficient by comparing the running results.

关 键 词：社团发现 Louvain 并行化 效率 分布式系统 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]