python-louvain,Louvain算法

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

　　背景：

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

　　目前，许多研究通过分析网络结构来发现社区。其中，Blondel等人基于现实中大规模网络的层次结构，提出了一种迭代两阶段快速算法(BGL算法)用于社区发现。该算法分为两步：第一步，通过在社区间局部交换节点，最大化社区划分的模块化。其次，将上一步网络划分产生的社区视为新网络中的一个节点，节点间边的权重为其代表的两个社区间边的权重之和。重复以上两个步骤，直到模块性无法再增加。bg算法使用的模块性度量由以下公式定义，该公式适用于加权网络：

　　其中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算法的社区发现系统的第二实施例的结构示意图。

　　详细实施模式

　　为了使本发明的目的、技术方案和优点更加清楚，将参照附图进一步详细描述本发明。为了记录在案，上、下、左、右、前、后、内、外等术语。在本文中出现或将要出现的，仅基于本发明的附图，并且它们不是本发明的具体限制。

　　复杂性是复杂系统的抽象。网络中的节点代表个体，边代表个体之间的关系。社团结构是复杂网络的共同特征，整个网络由多个社团组成。社区发现算法用于发现网络中的社区结构，也可以看作是一种聚类算法。算法是一个复杂而有意义的过程，它在研究复杂网络的特性中起着重要的作用。该算法试图将所有节点归纳成社区，使得同一个社区中的节点紧密相连，而comm

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

　　具体地，步骤S102包括：

　　(1)尝试将每个节点依次分配到每个邻居节点所在的社区；优选地，通过轮询来执行分配。

　　(2)计算分布前后的模块性变化；其中，发布前后模块性的变化是指发布前后模块性的差异。

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

　　(4)如果模块性变化的最大值大于0，则将节点分配给社区，重复此步骤，直到所有节点不再变化，形成社区图。

　　具体来说，与模块化变化相关的统计指标如下：

　　节点度：与节点相连的边的权重之和(加权图=边数)。对于有向图，度可以分为入度和出度，分别对应以节点为终点和起点的权重之和，入度和出度=度。

　　节点聚集系数：节点与其邻居之间的实际边数与可能边数的比率。聚类系数越大，节点与其周围的联系越紧密。

　　图的平均聚类系数：节点的平均聚类系数。值越大，图中各点之间的关系越紧密，越容易聚类。

　　最短路径长度：图中指定的节点由任意路径连接，最短路径长度为最短路径长度。

　　模块度：评价社区网络划分的一种尺度。其物理意义是社区中节点的连通边数与随机条件下的边数之差：其中Aij是边ij的权重，Ki= J，iAij代表节点I的度，ci代表I所属的社区，代表图的总度。上面的社区划分方法是基于模块化计算的。

　　S103，根据社区图将社区视为节点，重构社区图；

　　具体地，该社区图重构方法包括以下步骤：

　　(1)将社区中节点度之和转换成新节点对其自身回路的权重；

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

　　(3)重复步骤S102。

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

　　社区的稳定状态是指社区数量不变的状态。一开始大家都有社群号，形成社群，然后迭代。如果和侧面结合，模块性会下降，所以就结合了，然后结合在一起的就记住了一个共同的社区号。继续迭代。同样，一个点。如果你想去你旁边的街区，你必须走出现在的街区。如果去旁边街区的模块性大于出当前街区的模块性，那么你就出不去了，就稳定了。当所有点稳定时，迭代结束。如果社区号不变，则是稳定状态。

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

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

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

　　具体地，步骤S202包括：

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

　　(2)计算分布前后的模块性变化；其中，发布前后模块性的变化是指发布前后模块性的差异。

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

　　(4)如果模块性变化的最大值大于0，则将节点分配给社区，重复此步骤，直到所有节点不再变化，形成社区图。

　　S203，压缩社区图形。

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

　　S204，根据社区图将社区作为节点，重构社区图；

　　具体地，该社区图重构方法包括以下步骤：

　　(1)将社区中节点度之和转换成新节点对其自身回路的权重；

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

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

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

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

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

　　第二构建模块3，用于根据社区图将社区视为节点，重构社区图；

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

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

　　分配单元21，用于将每个节点依次分配给每个邻居节点所在的社区；优选地，通过轮询来执行分配。

　　计算单元22用于计算分发前后的模块性变化；其中，发布前后模块性的变化是指发布前后模块性的差异。

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

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

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

　　第一转换单元31用于将社区中节点的度之和转换为新节点对其自身回路的权重；

　　第二转换单元32将社区之间的边权重转换成新节点之间的边权重。

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

　　从以上可以看出，本发明具有以下有益效果：

　　1 .本发明实现了基于Louvain算法的社区发现，并对社区中的节点进行模块化关联分析；

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

　　3.由于节点是随机的，本发明不使用节点的特征向量来判断节点的相似性，而是直接将向量和节点的模块度关联起来，更加准确。

　　以上是本发明的优选实施例，需要指出的是，对于本领域普通技术人员来说，在不脱离本发明原理的情况下，可以进行多种改进和修饰，这些改进和修饰也可以视为本发明的保护范围。

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