网站名和域名的区别,网站浏览记录怎么做,房产网签,网站建设合同交印花税吗目录 **社区检测与聚类****社区检测技术**1. Louvain 社区检测[2]2. Surprise社区检测[3]3. 莱顿社区检测[4]4. Walktrap 社区检测[5] 结论5.LPA 标签传播6.K-L算法7.GN算法8.Newman快速算法 SlashBurn: Graph Compression and Mining beyond Caveman CommunitiesReferences 摘… 目录 **社区检测与聚类****社区检测技术**1. Louvain 社区检测[2]2. Surprise社区检测[3]3. 莱顿社区检测[4]4. Walktrap 社区检测[5] 结论5.LPA 标签传播6.K-L算法7.GN算法8.Newman快速算法 SlashBurn: Graph Compression and Mining beyond Caveman CommunitiesReferences 摘抄自Community Detection Algorithms
社区检测与聚类
有人可能会争辩说社区检测类似于聚类。聚类是一种机器学习技术其中相似的数据点根据它们的属性被分组到同一个聚类中。尽管聚类可以应用于网络但它是无监督机器学习中一个更广泛的领域它处理多种属性类型。另一方面社区检测是专门为网络分析量身定做的它依赖于称为边缘的单个属性类型。此外聚类算法倾向于将单个外围节点与其应属于的社区分开。然而聚类和社区检测技术都可以应用于许多网络分析问题并且可能会根据域产生不同的优缺点。
社区检测技术
社区检测方法可以大致分为两类凝聚法和分裂法。在凝聚法中边被一条一条地添加到只包含节点的图中。边从强边添加到弱边。分裂方法遵循与凝聚方法相反的方法。在那里边从一个完整的图中被一条一条地移除。 在给定的网络中可以有任意数量的社区并且它们的大小可以不同。这些特征使得社区的检测过程非常困难。然而在社区检测领域提出了许多不同的技术。下面解释了四种流行的社区检测算法。所有这些列出的算法都可以在python cdlib 库中找到。
1. Louvain 社区检测[2]
Louvain 社区检测算法最初是在 2008 年提出的是一种针对大型网络的快速社区展开方法。这种方法基于模块化它试图最大化社区中实际边数与社区中预期边数之间的差异。然而优化网络中的模块化是 NP-hard因此必须使用启发式算法。Louvain算法分为迭代重复两个阶段 节点的本地移动 网络聚合 该算法从 N 个节点的加权网络开始。在第一阶段算法为网络的每个节点分配不同的社区。然后对于每个节点它考虑邻居并评估模块化的获得通过从当前社区中删除特定节点并将其放置在邻居的社区中。如果收益为正且最大化则该节点将被放置在邻居的社区中。如果没有正收益节点将留在同一个社区。这个过程被重复应用于所有节点直到没有进一步的改进。Louvain 算法的第一阶段在获得模块性的局部最大值时停止。在第二阶段算法将第一阶段发现的社区作为节点来构建新网络。一旦第二阶段完成算法会将第一阶段重新应用于生成的网络。重复这些步骤直到网络没有变化并获得最大的模块化。 Louvain 社区检测算法在此过程中发现社区的社区。由于易于实现以及算法的速度它非常受欢迎。然而该算法的一个主要限制是在主存储器中使用网络存储。 下面给出使用python cdlib库的Louvain社区检测算法的使用。
from cdlib import algorithms
import networkx as nx
G nx.karate_club_graph()
coms algorithms.louvain(G, weight’weight’, resolution1., randomizeFalse)2. Surprise社区检测[3]
由于模块化的限制引入了一种基于经典概率的度量称为 Surprise以评估网络划分为社区的质量。该算法几乎类似于 Louvain 社区检测算法只是它使用了惊喜而不是模块化。节点从一个社区移动到另一个社区从而贪婪地改善惊喜。此方法考虑链接位于社区内的概率。惊喜的使用在许多小 社区的限制下效果很好而模块化的使用在少数大社区的限制下效果很好。 下面给出了使用 python cdlib 库的 Surprise 社区检测算法的使用。
from cdlib import algorithms
import networkx as nx
G nx.karate_club_graph()
coms algorithms.surprise_communities(G)3. 莱顿社区检测[4]
在后来的研究2019 年中VA Traag 等人。表明Louvain 社区检测倾向于发现内部断开的社区连接不良的社区。在 Louvain 算法中将作为社区中两个组件之间桥梁的节点移动到新社区可能会断开旧社区的连接。如果旧社区进一步分裂这将不是问题。但根据 Traag 等人的说法情况并非如此。旧社区中的其他节点因其强大的联系而允许其保持为单个社区。此外据他们介绍Louvain 倾向于每周都会发现相互关联的社区。因此他们提出了更快的 Leiden 算法以保证社区之间的良好连接。 除了 Louvain 算法中使用的阶段之外Leiden 还使用了另一个阶段来尝试细化发现的分区。莱顿算法的三个阶段是
节点的本地移动分区的细化基于细化分区的网络聚合
在细化阶段算法尝试从第一阶段提出的分区中识别细化的分区。第一阶段提出的社区可能会在第二阶段进一步分裂成多个分区。细化阶段不遵循贪婪的方法并且可以将节点与随机选择的社区合并从而增加质量函数。这种随机性允许更广泛地发现分区空间。同样在第一阶段莱顿对鲁汶采用了不同的方法。莱顿不会在对所有节点的第一次访问完成后访问网络中的所有节点而是只访问那些邻域发生变化的节点。 下面给出了使用python cdlib库的Leiden社区检测算法的使用。
from cdlib import algorithms
import networkx as nx
G nx.karate_club_graph()
coms algorithms.leiden(G)4. Walktrap 社区检测[5]
Walktrap 是另一种基于随机游走的社区检测方法其中顶点之间的距离通过网络中的随机游走来测量。Walktrap 是一种有效的算法在最坏情况下以 O(mn²) 时间复杂度和 O(n²) 空间复杂度运行。但在大多数实际场景中walktrap 以 O((n²) log n) 时间复杂度和 O(n²) 空间复杂度运行。该算法的基本直觉是图/网络上的随机游走倾向于陷入与社区对应的密集连接部分. Walktrap 使用随机游走的结果以自下而上的方式合并不同的社区。可以使用任何可用的质量标准来评估分区的质量。它可以是 Louvain 社区检测中的模块化也可以是任何其他措施。 下面给出使用python cdlib库的Walktrap社区检测算法的使用。
from cdlib import algorithms
import networkx as nx
G nx.karate_club_graph()
coms algorithms.walktrap(G)结论
社区检测非常适用于理解和评估大型复杂网络的结构。这种方法使用图或网络中边的属性因此更适合网络分析而不是聚类方法。聚类算法倾向于将单个外围节点与其应该属于的社区分开。许多不同的算法已经提出并实现用于网络社区检测。根据网络的性质以及应用问题域这些中的每一个都有不同的优缺点。
5.LPA 标签传播
Label Propagation Algorithm
算法
为所有节点指定一个唯一的标签 逐轮刷新所有节点的标签直到达到收敛要求为止。 对于每一轮刷新节点标签刷新的规则如下: 对于某一个节点考察其所有邻居节点的标签并进行统计将出现个数最多的那个标签赋给当前节点。当个数最多的标签不唯一时随机选一个。 问题
随机性太大更新顺序和初次迭代的时候选择的标签很大程度影响了结果
6.K-L算法
将已知网络划分为已知大小的两个社区的二分方法它是一种贪婪算法。它的主要思想是为网络划分定义了一个函数增益QQ表示的是社区内部的边数与社区之间的边数之差根据这个方法找出使增益函数Q的值成为最大值的划分社区的方法。具体策略是将社区结构中的结点移动到其他的社区结构中或者交换不同社区结构中的结点。从初始解开始搜索直到从当前的解出发找不到更优的候选解然后停止。
K-L算法的缺陷是必须先指定了两个子图的大小不然不会得到正确的结果实际应用意义不大。
7.GN算法
Finding and evaluating community structure in networksNewman and Girvan 介数betweenness 节点介数定义为网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例 边介数定义为网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例。
GN算法的步骤如下
计算每一条边的边介数删除边界数最大的边重新计算网络中剩下的边的边阶数重复(3)和(4)步骤直到网络中的任一顶点作为一个社区为止。
GN算法的缺陷 不知道最后会有多少个社区
在计算边介数的时候可能会有很对重复计算最短路径的情况时间复杂度太高GN算法不能判断算法终止位置。
8.Newman快速算法
本算法的具体内容请参考Fast algorithm for detecting community structure in networksNewman。
GN算法通过模块度可以准确的划分网络但它只适用于中小型规模的网络。Newman提出一种基于贪心的快速社区发现算法算法的基本思想是首先将网络中的每个顶点设为一个单独社区然后选出使得模块度Q的增值最大的社区对进行合并如果网络中的顶点属于同一个社区则停止合并过程。整个过程是自底向上的过程且这个过程最终得到一个树图即树的叶子节点表示网络中的顶点树的每一层切分对应着网络的某个具体划分从树图的所有层次划分中选择模块度值最大的划分作为网络的有效划分。
设网络有n个节点m条边每一步合并对应的社区数目为r组成一个r*r矩阵e矩阵元素eij表示社区i中的节点与社区j中节点之间连边的数目在网络总变数的百分比。
主要步骤 1 初始化网络开始网络有n 个社区初始化的eij和ai为 2依次按照∆Q的最大或者最小的方向进行合并有边相连的社区对并计算合并后的模块度增量∆Q 3合并社区对以后修改对社区对称矩阵e 和社区i和j对应的行列 4重复执行步骤2和3不断合并社区直至整个网络合并成一个社区为止。
SlashBurn: Graph Compression and Mining beyond Caveman Communities
https://ieeexplore.ieee.org/abstract/document/6807798
References
[1] Girvan, Michelle Newman, Mark. (2001). “Community structure in social and biological networks,” proc natl acad sci. 99. 7821–7826. [2] Blondel, V., Guillaume, J., Lambiotte, R. and Lefebvre, E., 2008. Fast unfolding of communities in large networks. IOPscience. [3] Traag, V., Aldecoa, R. and Delvenne, J., 2015. Detecting communities using asymptotical surprise. PHYSICAL REVIEW. [4] V. A. Traag, L. Waltman, and N. J. van Eck, “From Louvain to Leiden: guaranteeing well-connected communities,” Sci. Rep., vol. 9, no. 1, pp. 1–12, 2019, doi: 10.1038/s41598–019–41695-z. [5] Pons, P. and Latapy, M., n.d. Computing communities in large networks using random walks.
摘抄自 https://www.cnblogs.com/nolonely/p/6262508.html
