文档章节

Newman快速算法(fast greedy)

夺宝奇兵
 夺宝奇兵
发布于 2017/07/13 08:15
字数 425
阅读 171
收藏 0

    Newman快速算法实际上是基于贪婪算法思想的一种凝聚算法【1】。贪婪算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法【2】。社区发现(Community Detection)算法用来发现网络中的社区结构,也可以视为一种广义的聚类算法【4】。基于模块度优化的社团发现算法是目前研究最多的一类算法,由Newman等首先提出模块度Q 值是目前使用最广泛的优化目标【3】。Newman算法可以用于分析节点数达100万的复杂网络【1】

    Newman快速算法将每个节点看作是一个社团,每次迭代选择产生最大Q值的两个社团合并,直至整个网络融合成一个社团。整个过程可表示成一个树状图,从中选择Q值最大的层次划分得到最终的社团结构。该算法的总体时间复杂度为O(m(m+n))【3】。

 

参考

  1. 汪小帆. 复杂网络理论及其应用[M]. 清华大学出版社, 2006. P184 ~185
  2. 贪心法 - 维基百科,自由的百科全书
  3. 骆志刚, 丁凡, 蒋晓舟,等. 复杂网络社团发现算法研究新进展[J]. 国防科技大学学报, 2011, 33(1):47-52.
  4. Community Detection 算法 - peghoty - CSDN博客
  5. 模块度(Modularity)与Fast Newman算法讲解与代码实现 - 博客频道 - CSDN.NET
  6. 科学网—Girvan-Newman社群发现算法 - 毛进的博文
  7. 模块度 - 维基百科,自由的百科全书

© 著作权归作者所有

夺宝奇兵
粉丝 4
博文 73
码字总数 27286
作品 0
深圳
私信 提问
基于人工蜂群优化的帕累托前沿特征选择

引用 LaTex @article{HANCER2018462, title = “Pareto front feature selection based on artificial bee colony optimization”, journal = “Information Sciences”, volume = “422”,......

u010203404
2018/05/05
0
0
推荐系统的EE问题及Bandit算法

经常听身边的人说起使用推荐系统的感受,“某宝某东就是看什么给推什么”,使用者对推荐系统产生厌倦;也有听做推荐系统的同学抱怨推荐的冷启动问题,如何去尝试新用户的兴趣点,尝试到什么时...

fly_time2012
2018/03/09
0
0
AI学习笔记——Sarsa算法

上一篇文章介绍了强化学习中的Q-Learning算法,这篇文章介绍一个与Q-Learning十分类似的算法——Sarsa算法。 1. 回顾Q Learning 还是同样的例子,红色机器人在4x4的迷宫中寻找黄色的宝藏。找...

Hongtao洪滔
2018/08/13
0
0
Web API 持续集成:PostMan+Newman+Jenkins

上篇文章我们已经完成了API测试工具选型,接下来是一系列周期性的开发测试过程:接口开发、检出代码、运行测试、记录结果、发送报告。为了快速发现问题,并减少重复过程以节省时间、费用和工...

技术小能手
2018/11/09
0
0
Web API 持续集成:PostMan+Newman+Jenkins(图文讲解)

本文由葡萄城技术团队于OSChina原创并首发 转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具、解决方案和服务,赋能开发者。 上篇文章我们已经完成了API测试工具选型,接下来是...

葡萄城技术团队
2018/10/31
4.3K
1

没有更多内容

加载失败,请刷新页面

加载更多

iptables删除命令中的相关问题

最近在做一个中间件的配置工作,在配置iptables的时候,当用户想删除EIP(即释放当前连接),发现使用iptables的相关命令会提示错误。iptables: Bad rule (does a matching rule exist in t...

xiangyunyan
35分钟前
2
0
IT兄弟连 HTML5教程 HTML5表单 新增的表单属性1

HTML5 Input表单为<form>和<input>标签添加了几个新属性,属性如表1。 1 autocomplete属性 autocomplete属性规定form或input域应该拥有自动完成功能,当用户在自动完成域中开始输入时,浏览器...

老码农的一亩三分地
今天
7
0
OSChina 周五乱弹 —— 葛优理论+1

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @这次装个文艺青年吧 :#今日歌曲推荐# 分享米津玄師的单曲《LOSER》: mv中的舞蹈诡异却又美丽,如此随性怕是难再跳出第二次…… 《LOSER》-...

小小编辑
今天
1K
19
nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部