基于孤立节点分离策略的改进鲁汶算法

发布时间：2018-03-01 05:05

本文关键词： 复杂网络社区发现模块度模块度优化鲁汶算法　出处：《计算机应用》2017年04期 　论文类型：期刊论文

【摘要】：鲁汶算法(LM)是基于模块度优化的复杂网络社区发现算法,有关模块度的现有研究中没有计算节点离开原属社区后模块度增益的方法。针对这一不足,基于模块度的定义和节点合并后模块度增益的计算方法,推导出了节点离开原属社区后模块度增益的计算方法,完善了该领域的理论研究。针对鲁汶算法对存储空间需求高的缺点,提出了基于孤立节点分离策略的改进鲁汶算法,该算法在每次迭代中将输入网络的孤立节点提前分离出去,只令其中的连通节点实际参与迭代过程,并在存储社区发现结果时将孤立节点和非孤立节点分开存储。基于真实网络的相关实验结果表明,采用孤立节点分离策略的改进方法,使算法对存储空间的需求减少了40%以上,并进一步缩短了算法的运行时间。因此,改进后的算法在处理真实网络时更具优势。
[Abstract]:Leuven algorithm (LM) is a complex network community discovery algorithm based on modularity optimization. There is no method to calculate the modular gain after nodes leave the original community in the existing research on modularity. Based on the definition of modular degree and the calculation method of modular gain after node merging, the calculation method of modular degree gain after node leaving the original community is deduced. Aiming at the high demand for storage space of Leuven algorithm, an improved Leuven algorithm based on isolated node separation strategy is proposed, which separates the isolated nodes of the input network in advance in each iteration. Only the connected nodes are actually involved in the iterative process, and the isolated nodes and the non-isolated nodes are stored separately when the results are found in the storage community. The experimental results based on the real network show that the improved method is based on the isolated node separation strategy. The requirement of storage space is reduced by more than 40%, and the running time of the algorithm is further shortened. Therefore, the improved algorithm has more advantages in dealing with real networks.
【作者单位】：兰州交通大学电子与信息工程学院;
【基金】：国家自然科学基金资助项目(61163010) 兰州市科技计划项目(2014-1-171) 金川公司预研基金资助项目(JCYY2013012)~~
【分类号】：O157.5

【相似文献】