louvain算法实现与可视化,louvain算法python

　　奇技指南

　　在海量的信息流中，通过精准的算法向用户推荐其感兴趣的内容，已经成为一个产品吸引用户、获取利润的极其重要的方式。

　　本文是算法系列文章，将与大家分享360的算法团队在实践中积累的算法知识和经验。欢迎交流分享~

　　Louvain算法是一种基于多级子优化模块化的算法，具有快速、准确的优点，在效率和效果上都有很好的表现，能够发现层次化的社区结构。它被认为是最好的社区发现算法之一。

　　模块度

　　Louvain算法是一种基于图数据的社区发现算法。

　　原文是：

　　《Fast unfolding of communities in large networks》 。

　　Louvain算法的优化目标是最大化整个数据的模块性，

　　该模块的计算如下：

　　其中m是图中边的总数，k_i是指向节点I的所有连通边权重之和，k_j相同。A_{i，j}表示节点I，J之间的边权重.

　　有一点需要明确的是，模块性的概念并不是Louvain算法发明的，Louvain算法只是优化关系图模块性这一目标的一种实现。

　　Louvain算法的两步迭代设计

　　最初，每个原始节点被视为一个独立的社区，社区中的边权重为0。

　　步骤1

　　该算法扫描数据中的所有节点，为每个节点遍历该节点的所有邻居节点，并衡量将该节点添加到其邻居节点所在的社区中所带来的模块化收益。并选择利润最大对应的邻居节点，加入其社区。重复该过程以引导每个节点的社区归属不改变。

　　步骤2

　　将步骤1中形成的社区折叠起来，将每个社区折叠成一个点，计算这些新生成的“社区点”的边权重和社区中所有点的边权重之和。为下一轮做准备。

　　这个算法最大的优点就是速度快。步骤1中每次迭代的时间复杂度为O(N)，其中N是输入数据中的边数。步骤2的时间复杂度为O(M ^ N)，M为本次迭代的点数。

　　算法实现

　　数据结构设计

　　在数据结构的设计中有两个主要的考虑因素：

　　如何高效的存储图中的节点以及节点之间的关系？

　　如何在设计好的数据结构上高效的扫描数据和迭代算法。

　　目前一些开源算法主要是通过哈希表或者集合结构来存储节点之间的关系。

　　有两个主要缺点：

　　维护散列或集合结构本身需要大量的内存开销。

　　在遍历过程中，需要不断地创建、销毁和清空相应的Hash或Set结构，尤其是在遍历不同节点的邻居节点和社区时。

　　而且在遍历的过程中，结构对元素的访问并不是严格的O(1)。

　　出于上述考虑，我们设计了一种更高效的数据结构来存储图中的节点和边，避免使用复杂的数据结构，并且在算法的迭代过程中不应用冗余空间和空间破坏操作，具体如下：

　　节点字段描述：

　　count:团体中的节点数

　　clsid:节点所属社区的代表节点ID

　　next:步骤1迭代中属于同一临时社区的下一个节点

　　prev:属于步骤1迭代中的同一临时社区的前一个节点

　　first:属于除代表节点之外的同一社区的第一个节点，代表节点是在步骤2中社区折叠时生成的。

　　kin:稳定社区中节点之间的互连权重之和。

　　kout:稳定社群外部，指向自己社群的权重之和

　　clskin:临时社区中节点之间的互连权重之和

　　clstot:稳定社区所有指向自己的内外连接权重之和。

　　eindex:一个节点的邻居链表的第一个指针，链表下面剩下的都是节点本身。

　　关于edge数据结构的字段，顾名思义。

　　基于上述结构设计，给定M个节点，N-修剪图所需空间为：60 * m 24 * n。

　　例如，给定1000万个点，2000万条边的数据，所需空间约为：10，000，000 * 60，20，000，000 * 24=1，080m，整个迭代过程中内存环境保持不变。

　　迭代过程

　　1.假设我们一开始有五个点，它们之间有一定的关系(至于什么关系，姑且不论)，如下：

　　2.假设第一步完全迭代后找到了节点2，它应该加入了节点1所在的社区(一开始每个节点都是一个社区，它本身就是这个社区的代表)。新社区由节点1表示，如下所示：

　　此时，在节点3、4、5和节点1、2之间没有归属关系。

　　3.此时，应该执行步骤2来折叠由节点1和2组成的新社区。折叠社区被视为单个点，由节点1表示，如下所示：

　　此时，数据中有四个节点(或四个社区)，其中一个包含两个节点，而社区3、4、5都只包含一个节点，即它们自己。

　　4.重新执行步骤1，扫描社区1、3、4和5，假设完全迭代后，节点5、4和3都加入了节点1所在的社区，如下：

　　5.第二步：折叠新生成的社区。新折叠的社区被视为单个点，由节点1表示，其结构如下：

　　此时整个数据只剩下一个社区，即节点1代表的社区。

　　再次执行步骤1时，任何节点的社区归属都不会改变，此时不需要执行步骤2。此时，迭代结束。

　　代码实现及测试

　　基于上述结构设计的代码实现如所示：

　　https://github . com/liuzhiqiangruc/DML/blob/master/cls/louvain . c

　　在一个实际的图(70万个点，200万条边)上测试，迭代完成收敛所需的时间为：1.77秒。

　　实际中往往不需要迭代到每个点都不变，或者整个图中有多少比例的节点退出不变。

　　本文是算法系列的第三篇，分享Louvain算法的原理和设计。

　　本文由360视频信息流算法团队供稿。我们每周都会为你推送一篇算法相关的文章。欢迎大家一起交流学习。

　　相关推荐

　　深度剩余网络的曲折

　　梯度下降法/梯度下降

　　世界当你没有？

　　做你的肩膀就好。

　　没有

　　60官方科技微信官方账号

　　干货一手资讯精彩活动

　　空的

　　注意~

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。