社区发现算法-Louvain - 简书

标签: | 发表时间:2018-04-29 10:30 | 作者:
出处:https://www.jianshu.com

简介

Louvain算法[1]是一种基于多层次优化Modularity[2]的算法,它的优点是快速、准确,被[3]认为是性能最好的社区发现算法之一。Modularity函数最初被用于衡量社区发现算法结果的质量,它能够刻画发现的社区的紧密程度。那么既然能刻画社区的紧密程度,也就能够被用来当作一个优化函数,即将结点加入它的某个邻居所在的社区中,如果能够提升当前社区结构的modularity。</br>

Modularity的定义如下:


其中,m表示网络中边的数量,A为邻接矩阵,如果ci,cj相同则$\delta(ci,cj)$=1否则为0。</br>

如果当前结点所在的社区只有它自己,那么在计算将它加入到其它社区时的modularity的变化有个技巧来加速计算,Louvain的高效性也在一定程度上受益于此,它为:


</br>

Louvain算法包括两个阶段,在步骤一它不断地遍历网络中的结点,尝试将单个结点加入能够使modularity提升最大的社区中,直到所有结点都不再变化。在步骤二,它处理第一阶段的结果,将一个个小的社区归并为一个超结点来重新构造网络,这时边的权重为两个结点内所有原始结点的边权重之和。迭代这两个步骤直至算法稳定。它的执行流程如图所示:


</br>

## ****代码实现
GraphX是Spark上的一个图处理框架,它在RDD的基础之上封装出VertexRDD以及EdgeRDD,由这两个封装出的RDD便可构成图结构,详细请见官网:

GraphX实现
Python实现参见

## ****文献
1: Fast unfolding of communities in large networks
2: Finding community structure in very large networks
3: Community detection algorithms: A comparative analysis

相关 [社区 发现 算法] 推荐:

社区发现算法-Louvain - 简书

- -
Louvain算法[1]是一种基于多层次优化Modularity[2]的算法,它的优点是快速、准确,被[3]认为是性能最好的社区发现算法之一. Modularity函数最初被用于衡量社区发现算法结果的质量,它能够刻画发现的社区的紧密程度. 那么既然能刻画社区的紧密程度,也就能够被用来当作一个优化函数,即将结点加入它的某个邻居所在的社区中,如果能够提升当前社区结构的modularity.

Wakoopa – 软件共享发现社区 | 小众软件 > 在线应用

- manabomb - 小众软件 - Appinn
Wakoopa 是软件界的豆瓣,强大的软件共享与发现社区. 它在电脑上后台运行程序,详细记录用户的电脑使用情况,包括使用了哪些软件、游戏、网络服务,每个程序使用多长时间. 再将这些信息上传到 Wakoopa 社区生成可视化信息图表,帮助你了解自己的电脑使用习惯. 既然是社区,你自然可以共享软件使用信息、评价软件、推荐软件、加入群组、广加好友、远程监视机器、窥探他人隐私等等.

算法在社区氛围的应用(三): 机器学习在答非所问识别上的运用

- - 知乎每日精选
现在,瓦力可直接识别并处理该题中的答非所问内容. 我们鼓励认真、专业的分享,期待每一次讨论都能碰撞出更多有价值的信息,并希望每一个用心的回答都能够得到好的展示,为他人带来更多帮助. 但是,我们也发现在社区中出现了答非所问类的内容,影响知友们获取有价值内容的效率. 为了更好地识别答非所问类内容,我们采用了多种模型,包括传统的机器学习模型和比较新的深度学习模型.

[转][转]基于大规模语料的新词发现算法

- - heiyeluren的blog(黑夜路人的开源世界)
对中文资料进行自然语言处理时,我们会遇到很多其他语言不会有的困难,例如分词——汉语的词与词之间没有空格,那计算机怎么才知道“已结婚的和尚未结婚的”究竟是“已/结婚/的/和/尚未/结婚/的”,还是“已/结婚/的/和尚/未/结婚/的”呢. 不过,现在很多语言模型都已能比较漂亮地解决这一问题了. 但在中文分词领域里,还有一个比分词歧义更令人头疼的东西—— 未登录词.

Community Detection 社群发现算法 - CSDN博客

- -
        社区发现(Community Detection)算法用来发现网络中的社区结构,也可以视为一种广义的. 以下是我的一个 PPT 报告,分享给大家.         从上述定义可以看出:社区是一个比较含糊的概念,只给出了一个定性的刻画. 另外需要注意的是,社区是一个子图,包含顶点和边.

社区初建十四条

- 韩叙 - 掰掰/谢谢你们给的鱼啦
我做社区最大的困难是开发工作跟不上节奏,这导致社区在去年10月份进行内测,下版本更新就接不上,当时招不到运营人员,两个月空档,捱到12月份才做了改版,社区人气就是零蛋. 这段难熬的日子过去以后,我们开始有了一批核心用户,并以此为星星之火,正在起燎原之势. 虽然我是产品出身,但是渐渐的,在资源限制的条件下,我更看重运营,我把运营看成一种无形的产品和用户体验来建设.

社区身,媒体心

- 珍珠 - 所有文章 - UCD大社区
新浪微博分明已经做成了一个社会化媒体,却一直坚持社区的商业模式. 现在推出微币不说,还顺便推出了微游戏,分明是眼红人家墙外的那个非死不可. 但新浪微博不是社区,加V和关注构不成关系,是内容在维系着新浪微博的生态,而并非人际关系. 朋友取消对你的关注,不是要和你绝交,那只是因为话痨的你打乱了他的时间轴.

从社区常识说起

- ZoOL - 设计思想 - UCD大社区
这篇文章全无深刻,只讲社区培育的一些常识. 虽说是大路货,操作的时候也可能遗漏一些东西,我最近就在自检时发现了漏洞. 先说说什么是“社区”,互联网上尚无公认的定义. 按我的看法,凡重视人际关系的内容产品,同时域内用户对整个用户群有较强的认同感,这就是社区. 它有三个典型特征,第一是用户产出内容,第二是通过用户关系来加强内容的互动与产出,第三是有着约定俗成的社区文化.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.