python-louvain_louvin算法

本发明涉及数据挖掘技术领域，尤其涉及一种基于Louvain算法的社区发现方法及一种基于Louvain算法的社区发现系统

背景技术：

随着信息化技术的发展，信息系统中保存着大量用户的信息特征，用户与用户之间也存在着某种关联性。用户的特征具有多维度，且多关联性。社区发现能帮助人们更有效地了解网络的结构特征，从而提供更有效、更具个性化的服务。

当前，许多研究通过分析网络的结构来发现社区。其中，Blondel等人基于现实中的大规模网络的社区结构都具有层次性，提出了一种迭代的两阶段模块度最大化的快速算法(BGL算法)用于发现社区。该算法分为两步：第一步、通过社区之间局部交换节点使得社区划分的模块度最大化。第二步、将前一步网络划分产生的社区作为新的网络中的一个节点，节点之间边的权值为其代表的两个社区之间的边的权值之和。反复迭代以上两个步骤，直到模块度的大小不再可能增加。BGL算法所使用的模块度度量标准如下式所定义，该定义适用于加权网络：

其中，Aij表示节点i和节点j之间的边的权重；ki＝∑jAij表示与节点i相连的所有边的权值之和；ci表示节点i所在的(所属的)社区；δ函数δ(u，v)表示当u与v相等时为1，而其余情况下为0；表示网络中所有边的权值之和。

然而，BGL算法没有涉及到网络节点的属性信息。而研究表明，在真实的在线社交网络中，节点的属性信息可以是判断的标准之一，在结构紧密的前提下，同一社区内的节点属性越相似越好。除此之外，虽然现有的很多聚类方法已将网络的结构和节点的属性特征(或称节点属性或节点属性信息)结合起来考虑(例如，通过对属性和结构进行加权的方法构造新的网络，并在新的网络上进行社区划分)，但是这些聚类的结果往往存在结构上并不紧密或者不关联的社区，从而导致社区发现的结果不准确；而且，这些方法的时间复杂度较高，不适于处理大规模的数据。

技术实现要素：

本发明所要解决的技术问题在于，提供一种基于Louvain算法的社区发现方法及系统，可将网络中的每个节点当作社区，并针对社区的模块度和边权重分析，从而可以得到更加精准的社区发现。

为了解决上述技术问题，本发明提供了一种基于Louvain算法的社区发现方法，包括：

S1，初始化社区，把每个节点作为一个社区；

S2，将每个节点依次分配到每个邻居节点所在社区以构建社区图形；

S3，根据社区图形把社区看作一个节点，重新构建社区图形；

S4，重复步骤S3，直到所有状态稳定，则输出结果。

作为上述方案的改进，所述步骤S2包括：将每个节点，依次尝试分配到每个邻居节点所在社区；计算分配前与分配后的模块度变化量；提取模块度变化量的最大值；若模块度变化量的最大值大于0，则将节点分配到该社区，一直重复这个步骤，直到所有节点不再变化，形成社区图形。

作为上述方案的改进，所述重新构建社区图形的方法包括：把社区内节点度数和，转化为新节点到自己的环路的权重；把社区间的边权重转化为新节点间的边权重；重复步骤S2。

作为上述方案的改进，所述步骤S3之前还包括：压缩社区图形。

作为上述方案的改进，通过Python压缩社区图形。

相应地，本发明还提供了一种基于Louvain算法的社区发现系统，包括：初始化模块，用于初始化社区，把每个节点作为一个社区；第一构建模块，用于将每个节点依次分配到每个邻居节点所在社区以构建社区图形；第二构建模块，用于根据社区图形把社区看作一个节点，重新构建社区图形；输出模块，用于当所有状态稳定时，输出结果。

作为上述方案的改进，所述第一构建模块包括：分配单元，用于将每个节点，依次尝试分配到每个邻居节点所在社区；计算单元，用于计算分配前与分配后的模块度变化量；提取单元，用于提取模块度变化量的最大值；图形单元，用于若模块度变化量的最大值大于0，则将节点分配到该社区，直到所有节点不再变化，形成社区图形。

作为上述方案的改进，所述第二构建模块包括：第一转化单元，用于把社区内节点度数和，转化为新节点到自己的环路的权重；第二转化单元，把社区间的边权重转化为新节点间的边权重。

作为上述方案的改进，所述基于Louvain算法的社区发现系统还包括压缩模块，用于压缩社区图形。

作为上述方案的改进，所述压缩模块通过Python压缩社区图形。

实施本发明，具有如下有益效果：

本发明利用大数据中的聚类算法技术，实现复杂网络中的社区发现。将网络中的每个节点当作社区，并针对社区的模块度和边权重分析，从而可以得到更加精准的社区发现，具体地：

1、本发明采用基于Louvain算法实现社区发现，针对社区中的节点进行模块度的关联分析；

2、本发明采用两层计算。开始通过模块度变化量对每个节点进行社区划分，然后针对划分后形成的社区，做图形压缩，从而再次进行社区的模块度和边权重分析并进行社区划分，直到所有状态稳定，再输出结果，对社区的发现更加深入。

3、由于节点具有随机性，本发明没有使用节点的特征向量对节点进行相似度判断，而是直接对节点进行向量及模块度的关联，更为准确。

附图说明

图1是社区节点示意图；

图2是本发明基于Louvain算法的社区发现方法的第一实施例流程；

图3是本发明基于Louvain算法的社区发现方法的第二实施例流程；

图4是本发明基于Louvain算法的社区发现系统的第一实施例结构示意图；

图5是本发明中第一构建模块的结构示意图；

图6是本发明中第二构建模块的结构示意图；

图7是本发明基于Louvain算法的社区发现系统的第二实施例结构示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述。仅此声明，本发明在文中出现或即将出现的上、下、左、右、前、后、内、外等方位用词，仅以本发明的附图为基准，其并不是对本发明的具体限定。

复杂网络是一个复杂系统的抽象，网络中的节点表示个体，边表示个体间的关系。社区结构是复杂网络中的一个普通特征，整个网络是由多个社区组成。社区发现(Community Detection)算法用来发现网络中的社区结构，也可以看作是一种聚类算法。该算法是一个复杂而有意义的过程，它对研究复杂网络特征具有重要作用。算法试图归纳各个节点为社区，使得同一个社区内节点连接紧密，而社区间连接比较稀疏(参见图1)。本发明选用基于模块度评估的Louvain算法实现社区发现过程。

参见图2，图2显示了本发明一种基于Louvain算法的社区发现方法的第一实施例流程图，其包括：

S101，初始化社区，把每个节点作为一个社区；

S102，将每个节点依次分配到每个邻居节点所在社区以构建社区图形；

具体地，所述步骤S102包括：

(1)将每个节点，依次尝试分配到每个邻居节点所在社区；优选地，采用轮询方式进行分配。

(2)计算分配前与分配后的模块度变化量；其中，分配前与分配后的模块度变化量是指分配前模块度与分配后模块度之差。

(3)提取模块度变化量的最大值；

(4)若模块度变化量的最大值大于0，则将节点分配到该社区，一直重复这个步骤，直到所有节点不再变化，形成社区图形。

具体地，与模块度变化量相关统计指标如下：

节点的度：与节点相连的边的权和(无权图则＝边数)，对于有向图，度可以分为入度及出度，分别对应以该节点为终点的权和与起点的权和，入度+出度＝度

节点聚类系数：节点与其邻居实际存在的边数与可能存在的边数之比聚类系数越大，节点与周围连接越密切。

图的平均聚类系数：节点聚类系数平均值，越大则图形中的点的关系越密切，更容易成团。

最短路径长度：图中指定节点有任意路径相连，经过路径最短的长度为最短路径长度。

模块度：评估一个社区网络划分好坏的度量方法，它的物理含义是社区内节点的连边数与随机情况下的边数之差：其中Aij为边ij的权重，ki＝∑j，iAij表示节点i的度，ci表示i所属社区，表示图的总度数。以上社区划分方法基于模块度计算。

S103，根据社区图形把社区看作一个节点，重新构建社区图形；

具体地，所述重新构建社区图形的方法包括：

(1)把社区内节点度数和，转化为新节点到自己的环路的权重；

(2)把社区间的边权重转化为新节点间的边权重；

(3)重复步骤S102。

S104，重复步骤S103，直到所有状态稳定，则输出结果。

社区的稳定状态，是指社区号不变的状态。一开始，大家都有一个社区号，自成一个社区，然后就迭代。如果跟旁边结合，模块度会下降，就结合，然后结合在一起的就记共同一个社区号。继续迭代，同样的，一个点，如果要去旁边的社区，就必须脱离现在的社区，如果去旁边的社区模块度比脱离现在社区的模块度还要大，那就不脱离了，那就稳定下来了。当所有点都稳定了，迭代结束。社区号不变，就是一个稳定的状态。

参见图3，图3显示了本发明一种基于Louvain算法的社区发现方法的第二实施例流程图，其包括：

S201，初始化社区，把每个节点作为一个社区；

S202，将每个节点依次分配到每个邻居节点所在社区以构建社区图形；

具体地，所述步骤S202包括：

(1)将每个节点，依次尝试分配到每个邻居节点所在社区；

(2)计算分配前与分配后的模块度变化量；其中，分配前与分配后的模块度变化量是指分配前模块度与分配后模块度之差。

(3)提取模块度变化量的最大值；

(4)若模块度变化量的最大值大于0，则将节点分配到该社区，一直重复这个步骤，直到所有节点不再变化，形成社区图形。

S203，压缩社区图形。

通过Python方式实现降维及类聚，从而实现社区图形的压缩。

S204，根据社区图形把社区看作一个节点，重新构建社区图形；

具体地，所述重新构建社区图形的方法包括：

(1)把社区内节点度数和，转化为新节点到自己的环路的权重；

(2)把社区间的边权重转化为新节点间的边权重；

(3)重复步骤S202。

S205，重复步骤S204，直到所有状态稳定，则输出结果。

因此，本发明利用大数据中的聚类算法技术，实现复杂网络中的社区发现。将网络中的每个节点当作社区，并针对社区的模块度和边权重分析，从而可以得到更加精准的社区发现。相应地，通过社区发现，在教育领域中，可以发现学校内全部学生的社区关系，为学校内学生的大数据分析及服务提供帮助，如可以提供好友发现，更加精准的为学生推荐好友；图书推荐，可以利用社区中的阅读风格或者阅读内容，进行图书推荐；课程推荐，促进学生个性化学习；职业推荐，根据社区关系推进类似的工作，增加职业推荐的智能性等。

参见图4，图4显示了本发明基于Louvain算法的社区发现系统100的第一实施例，其包括：

初始化模块1，用于初始化社区，把每个节点作为一个社区；

第一构建模块2，用于将每个节点依次分配到每个邻居节点所在社区以构建社区图形；

第二构建模块3，用于根据社区图形把社区看作一个节点，重新构建社区图形；

输出模块4，用于当所有状态稳定时，输出结果。

如图5所示，所述第一构建模块2包括：

分配单元21，用于将每个节点，依次尝试分配到每个邻居节点所在社区；优选地，采用轮询方式进行分配。

计算单元22，用于计算分配前与分配后的模块度变化量；其中，分配前与分配后的模块度变化量是指分配前模块度与分配后模块度之差。

提取单元23，用于提取模块度变化量的最大值；

图形单元24，用于若模块度变化量的最大值大于0，则将节点分配到该社区，直到所有节点不再变化，形成社区图形。

如图6所示，所述第二构建模块3包括：

第一转化单元31，用于把社区内节点度数和，转化为新节点到自己的环路的权重；

第二转化单元32，把社区间的边权重转化为新节点间的边权重。

参见图7，图7显示了本发明基于Louvain算法的社区发现系统的第二实施例，与图4所示的第一实施例不同的是，本实施例中所述基于Louvain算法的社区发现系统还包括压缩模块5，所述压缩模块5用于压缩社区图形。优选地，压缩模块5通过Python方式实现降维及类聚，从而实现社区图形的压缩。

由上可知，本发明具有以下有益效果：

1、本发明采用基于Louvain算法实现社区发现，针对社区中的节点进行模块度的关联分析；

2、本发明采用两层计算。开始通过模块度变化量对每个节点进行社区划分，然后针对划分后形成的社区，做图形压缩，从而再次进行社区的模块度和边权重分析并进行社区划分，直到所有状态稳定，再输出结果，对社区的发现更加深入。

3、由于节点具有随机性，本发明没有使用节点的特征向量对节点进行相似度判断，而是直接对节点进行向量及模块度的关联，更为准确。

以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也视为本发明的保护范围。