企业官网建设流程全解析

找人做网站要密码吗,网站制作 常州,网站运营的提成方案怎么做,电商网站架构设计引言 因为有 GraphRAG 的需求#xff0c;其中涉及到了社区检测#xff0c;因此也稍微看看这一领域中常用的 Louvain 算法和 Leiden 算法。本文内容主要是对论文 From Louvain to Leiden: guaranteeing well-connected communities 的简单分析解读#xff0c;其中所提到的实…引言因为有 GraphRAG 的需求其中涉及到了社区检测因此也稍微看看这一领域中常用的 Louvain 算法和 Leiden 算法。本文内容主要是对论文 From Louvain to Leiden: guaranteeing well-connected communities 的简单分析解读其中所提到的实验数据也是来源于此论文。在复杂网络分析中社区检测是理解网络结构的关键手段。在许多复杂网络中节点会聚集并形成相对密集的群体——通常被称为社区。这种模块化结构通常事先是未知的。因此检测网络中的社区是一个重要的问题。那么如何评判社区检测结果好坏因此需要一种衡量网络特定划分质量的标准一般这个标准称为质量函数quality function**模块度Modularity和恒定波茨模型Constant Potts ModelCPM**是常用的社区质量评估函数。理解质量函数Modularity社区检测中最著名的方法之一是模块化其所使用的质量函数就是 Modularity定义如下H 1 2 m ∑ c ( e c − γ K c 2 2 m ) \mathcal{H}\frac{1}{2 m} \sum_{c}\left(e_{c}-\gamma \frac{K_{c}^{2}}{2 m}\right)H2m1​c∑​(ec​−γ2mKc2​​)其核心是通过“实际边数与随机情况下期望边数的差异”量化社区结构的优劣用来评估一个网络划分成若干社区后其内部连接是否显著强于随机预期。核心参数定义参数数学含义物理网络解释H \mathcal{H}HModularity值模块化得分衡量网络社区划分质量的指标取值范围通常为[ − 1 , 1 ] [-1,1][−1,1]值越接近1社区结构越显著。模块化方法的目标就是最大化这个值。m mm网络中总边数描述网络整体的连接密度是归一化因子避免网络规模对得分的干扰c cc单个社区网络中被划分出的一个“节点集群”所有社区构成网络的完整分区无重叠、无遗漏e c e_cec​社区c cc内部的实际边数反映社区内部的连接紧密程度e c e_cec​越大社区内部越稠密K c K_cKc​社区c cc中所有节点的度数之和描述社区c cc的“总连接能力”包含社区内部与外部的所有连接如节点v vv的度数其内部边数外部边数γ \gammaγ分辨率参数γ 0 \gamma0γ0控制社区划分的精细度γ \gammaγ越大高分辨率倾向于拆分出更多小社区γ \gammaγ越小低分辨率倾向于合并为更少大社区关键计算项简单说明这里只是简单说明下公式中的几个计算项没有深入研究细节及其推导。期望边数项K c 2 2 m \frac{K_{c}^{2}}{2m}2mKc2​​基于“配置模型”Configuration Model计算——假设网络节点度数固定边随机连接时社区c cc内部“理论上应存在的边数”。社区贡献项( e c − γ K c 2 2 m ) \left(e_{c}-\gamma \frac{K_{c}^{2}}{2m}\right)(ec​−γ2mKc2​​)单个社区c cc对整体模块化得分的“贡献值”。若e c γ K c 2 2 m e_c \gamma \frac{K_c^2}{2m}ec​γ2mKc2​​说明社区c cc内部实际边数超过随机期望该社区的“结构显著性”为正反之则为负可能是划分不合理的社区。全局归一化1 2 m \frac{1}{2m}2m1​将所有社区的贡献项求和后进行归一化确保模块化得分在统一尺度下可比不受网络规模影响。物理网络视角的本质意义从网络结构的物理含义出发Modularity本质是**“社区内部稠密连接”与“社区间稀疏连接”的量化差异**核心作用是判断“某一分区是否真实反映了网络的内在社区结构”具体可从3个维度理解1. 区分“真实社区”与“随机集群”在无真实社区结构的随机网络中任意划分的“社区”内部边数e c e_cec​会接近期望边数K c 2 2 m \frac{K_c^2}{2m}2mKc2​​此时 Modularity 值接近0而在存在真实社区的网络中如社交网络的“兴趣群组”、引文网络的“研究主题集群”社区内部边数远多于随机期望Modularity值会显著大于0得分越高说明划分越贴合真实结构越能体现社区性。2. 平衡“社区粒度”与“结构显著性”分辨率参数γ \gammaγ的物理意义是“社区密度阈值”当γ \gammaγ较小时如γ 0.1 \gamma0.1γ0.1低阈值允许更多节点被划入同一社区即使社区内部密度较低但仍高于随机期望适合检测“宏观大社区”如整个社交网络中的“地区群组”当γ \gammaγ较大时如γ 1 \gamma1γ1高阈值要求社区内部密度极高仅允许紧密连接的节点构成社区适合检测“微观小社区”如地区群组中的“家庭子群”。3. 规避“规模依赖”的公平对比通过1 2 m \frac{1}{2m}2m1​的归一化Modularity可在不同规模的网络间公平比较社区结构质量。例如小网络如100节点、200条边与大网络如10000节点、20000条边的Modularity得分可直接对比无需担心“大网络边数多导致得分偏高”的问题同一网络的不同分区方案如A方案分5个社区B方案分10个社区可通过Modularity值判断哪种方案更优。Constant Potts Model使用模块度作为质量函数时会有所谓的分辨率限制问题。由于分辨率限制也就是 Modularity 中的期望边数K c 2 2 m \frac{K_{c}^{2}}{2m}2mKc2​​依赖网络总边数m mm当社区规模远小于网络整体规模时即使该社区内部连接极稠密其对 Modularity 总分的 “贡献” 也可能被 “大社区的贡献” 淹没导致算法无法识别出小社区。换句话说模块化可能会“隐藏”较小的社区而产生包含重要子结构的社区。CPM 通过使用不同的参考基准避免了这个问题其定义如下H ∑ c [ e c − γ ( n c 2 ) ] \mathcal{H}\sum_{c}\left[e_{c}-\gamma \binom{n_c}{2}\right]Hc∑​[ec​−γ(2nc​​)]其中n c n_{c}nc​是社区c cc中的节点数量。分辨率参数γ \gammaγ起到一种阈值的作用社区的密度应至少为γ \gammaγ而社区之间的密度应低于γ \gammaγ。与模块化的分辨率参数类似较高的分辨率会产生更多的社区较低的分辨率则会产生更少的社区。可以看到CPM 的参考基准是“社区自身的最大可能边数( n c 2 ) \binom{n_c}{2}(2nc​​)”与网络整体规模总节点数、总边数无关仅依赖社区内部节点数n c n_cnc​。因此无论社区规模大小只要内部密度≥ γ ≥ \gamma≥γ就能被识别为有效社区避免了 Modularity“漏检小社区”的问题。Louvain 算法直接优化模块度或 CPM 等质量函数是NP难问题因此人们提出了许多启发式算法在这些算法中最受欢迎的算法之一就是所谓的Louvain算法其名称来源于作者所在的地点。在对比分析中该算法被发现是速度最快、性能最佳的算法之一并且是社区检测文献中被引用次数最多的研究成果之一。核心流程Louvain 算法非常简单巧妙其通过 “节点的局部移动 - 网络聚合” 的两阶段迭代来优化质量函数流程如下初始状态每个节点为独立社区单点分区局部移动阶段逐个移动节点到能使质量函数获得最大增幅的社区中直至无节点可优化移动网络聚合阶段基于局部移动阶段得到的分区创建一个聚合网络分区中的每个社区作为聚合网络中的一个节点迭代终止重复 “局部移动 - 聚合”直至质量函数无法提升。整体算法流程图和伪代码来自原论文如下所示算法缺陷虽然 Louvain 算法简单优雅但其却存在严重缺陷社区连通性差可能产生任意程度的连通性不佳的社区极端情况下甚至出现完全不连通的社区部分节点需通过社区外路径才能连通。分析显示Louvain 发现的社区中高达 25% 的社区连接不良多达 16% 实际上是断开的。迭代加剧问题迭代运行时虽能提升质量函数值但会进一步恶化社区连通性。这是因为算法仅考虑单个节点移动可能移除社区 “桥节点” 导致社区离散且无修复机制。与分辨率限制无关该缺陷独立于模块化的分辨率限制问题即使使用无分辨率限制的 CPM 函数问题仍存在。比如像下图所示的情况06 节点在同一个社区中红色表示13 节点和 46 节点仅靠 0 节点连通而 Louvain 算法运行移动网络中其余部分中的节点。可能在某个时刻算法发现将节点 0 移动到其他社区是最优的选择然后将节点 0 从红色社区中移除掉后就形成了右图所示的情况也就是得到了一个内部不连通的社区。Leiden 算法Leiden 算法正是为了解决 Louvain 算法的缺陷而提出来的一种改进的算法其能保证社区具有良好的连通性。核心流程Leiden 算法的核心流程可分为以下三个阶段以及各阶段与 Louvain 算法的比较阶段核心操作与Louvain算法的差异1. 节点局部移动采用“快速局部移动”策略用队列维护需访问的节点仅重新访问邻居结构变化的节点避免重复访问无变化节点Louvain 每一次均需遍历所有节点直至无优化空间效率低Leiden减少无效访问速度更快2. 分区细化基于阶段1的分区P PP生成细化分区P r e f i n e d P_{refined}Prefined​1. 初始为单节点分区2. 仅在P PP的社区内部合并节点且合并需满足“与原社区充分连通”3. 随机选择合并目标 使用变量θ \thetaθ控制随机性合并目标需为质量提升大于 0 的社区Louvain无细化阶段直接基于P PP聚合网络可能保留连通性差的社区3. 网络聚合基于P r e f i n e d P_{refined}Prefined​构建聚合网络且聚合网络的初始分区仍基于P PPLouvain直接基于P PP聚合无法修复已有缺陷整体算法流程图和伪代码如下所示算法性能保证Leiden算法提供了多层级的理论保证显著优于Louvain算法具体对比如下γ \gammaγ指的是待优化质量函数中的分辨率参数该质量函数可以是模块化函数或CPM。保证类型Louvain算法Leiden算法每轮迭代✅γ \gammaγ-分离无社区可合并✅γ \gammaγ-分离✅γ \gammaγ-连通社区保证连通强于普通连通性稳定迭代分区无变化✅ 节点最优无单个节点可优化移动✅ 节点最优✅ 子分区γ \gammaγ-稠密社区可拆分为连通子部分且子部分无法与原社区分离渐近收敛迭代至无优化空间❌ 无额外保证稳定后无法进一步优化✅ 均匀γ \gammaγ-稠密社区任意子集均无法与原社区分离质量接近最优✅ 子集最优社区所有子集均无法优化移动最强保证实验验证结果研究在6个真实网络DBLP、Amazon、IMDB等和基准网络上验证算法性能核心结论如下1. 连通性改善Louvain算法迭代次数增加后离散社区比例显著上升如DBLP网络迭代后离散社区达16%Amazon网络25%社区连通性差。Leiden算法保证所有社区连通迭代次数增加时连通性差的社区比例持续下降最终收敛到无连通性问题的分区。2. 速度提升基准网络节点数越多、社区划分难度越大μ \muμ越大μ \muμ为边在社区间的概率Leiden优势越明显。例如μ 0.9 \mu0.9μ0.9最难划分、节点数n 10 7 n10^7n107时Louvain需2.5天Leiden仅需10分钟。真实网络Leiden比Louvain快2-20倍大型网络如Web UK速度差距达20倍。3. 分区质量优化基准网络μ \muμ较大时Leiden生成的分区质量更高CPM质量函数值更高。真实网络所有网络中Leiden的模块度均高于Louvain如Amazon网络Louvain 模块度 0.9301Leiden 达 0.9341且迭代中持续优化而Louvain快速收敛到次优解。总结总的来说Leiden 算法通过几个关键操作避免了 Louvain 算法的社区内连通性缺陷并且极大地提升了算法效率采用“快速局部移动”策略仅需重新访问被移动节点的相关邻居节点避免重复访问无变化节点从而提高了分区优化效率对快速局部移动节点得到的分区进行细分如果原分区的社区内有连通性差的部分则会原社区会分裂为多个社区网络聚合是基于细分后的分区进行的而聚合后的网络的初始分区还是快速局部移动得到的分区这样既保证当前迭代的最优分区又使得社区内的不连通子社区聚合网络中的节点能有重新被移动的机会从而确保社区连通性。