基于贪婪优化技术的网络社区发现算法研究

摘要

In social network ,the important and crucial problem is community detection .Classical modularity function opti-mization approaches such as CNM and BGLL are widely used methods for identifying communities which are quite efficient .As we have known ,modularity function (Q) suffers from its resolution limit .Recently ,surprise function(S) was proposed and experimen-tally proved to be better than Q function .However ,up to now ,there is not any method which is based on direct surprise maximiza-tion .In this paper ,an efficient community detection algorithm which is based on greedy surprise optimization is proposed and does not suffer from a resolution limit .The new method does not need community number K .Test results on experimental networks show that our method is robust ,not sensitive to noises and has better performances .%社区发现问题是复杂网络研究的热点问题。基于优化模块度 Q 函数的方法例如 CNM ，BGLL 等是一类经典的应用广泛的网络社区发现方法。但是已有研究发现，该类方法存在分辨率的问题，即当大规模网络中存在较小社区的情况下这类方法的效果不佳。近来，针对 Q 函数存在的问题，有研究者证明了另一个有效的目标函数 surprise 不存在分辨率的问题。但是目前没有直接优化该函数的有效算法，因此，提出一种基于贪婪思想的局部优化 surprise 函数的社区发现算法，该方法同样不存在分辨率的问题，而且算法不需要指定社区的个数。实验结果表明该方法鲁棒性好，精度优于其它经典的方法例如 CNM ，BGLL 和 LPA 。