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

来源：计算机应用杂志2017年第4期北京时间：

作者：李雷, 闫光辉, 杨绍文, 张海韬

单位：兰州交通大学 电子与信息工程学院, 兰州 730070

摘要：鲁汶算法（LM）是基于模块度优化的复杂网络社区发现算法，有关模块度的现有研究中没有计算节点离开原属社区后模块度增益的方法。针对这一不足，基于模块度的定义和节点合并后模块度增益的计算方法，推导出了节点离开原属社区后模块度增益的计算方法，完善了该领域的理论研究。针对鲁汶算法对存储空间需求高的缺点，提出了基于孤立节点分离策略的改进鲁汶算法，该算法在每次迭代中将输入网络的孤立节点提前分离出去，只令其中的连通节点实际参与迭代过程，并在存储社区发现结果时将孤立节点和非孤立节点分开存储。基于真实网络的相关实验结果表明，采用孤立节点分离策略的改进方法，使算法对存储空间的需求减少了40%以上，并进一步缩短了算法的运行时间。因此，改进后的算法在处理真实网络时更具优势。

关键词：复杂网络,社区发现,模块度,模块度优化,鲁汶算法

基金资助：国家自然科学基金资助项目（61163010）；兰州市科技计划项目（2014-1-171）；金川公司预研基金资助项目（JCYY2013012）。