本文主要是介绍Newman快速算法（fast greedy），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Newman快速算法实际上是基于贪婪算法思想的一种凝聚算法【1】。贪婪算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法【2】。社区发现（Community Detection）算法用来发现网络中的社区结构，也可以视为一种广义的聚类算法【4】。基于模块度优化的社团发现算法是目前研究最多的一类算法，由Newman等首先提出模块度Q 值是目前使用最广泛的优化目标【3】。Newman算法可以用于分析节点数达100万的复杂网络【1】
Newman快速算法将每个节点看作是一个社团，每次迭代选择产生最大Q值的两个社团合并，直至整个网络融合成一个社团。整个过程可表示成一个树状图，从中选择Ｑ值最大的层次划分得到最终的社团结构。该算法的总体时间复杂度为Ｏ（ｍ（ｍ＋ｎ））【3】。
参考
- 汪小帆. 复杂网络理论及其应用[M]. 清华大学出版社, 2006. P184 ~185
- 贪心法 - 维基百科，自由的百科全书
- 骆志刚, 丁凡, 蒋晓舟,等. 复杂网络社团发现算法研究新进展[J]. 国防科技大学学报, 2011, 33(1):47-52.
- Community Detection 算法 - peghoty - CSDN博客
- 模块度(Modularity)与Fast Newman算法讲解与代码实现 - 博客频道 - CSDN.NET
- 科学网—Girvan-Newman社群发现算法 - 毛进的博文
- 模块度 - 维基百科，自由的百科全书
这篇关于Newman快速算法（fast greedy）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
