返回主题:强化学习与多智能体

此卡片不在当前主题的阅读序列中,可返回主题继续阅读。

知识卡片

普通读书笔记卡 · 3734.a

社区目标兼顾内聚分离

理解等级:中级

网络社区划分同时关心社区内连接紧密和社区间分离:书中以 NAR 衡量前者、RC 衡量后者,两者由模块密度函数拆分而来。设划分出社区 C₁…C_l,|Cᵢ| 为社区节点数,邻接矩阵 A 中两节点相连记 Aᵢⱼ=1:

  • 内部度 d_in:社区内节点之间的连接数之和;NAR = −Σ d_in/|Cᵢ|,取负号使“最小化 NAR”等于让社区内部按规模平均更密。
  • 外部度 d_out:社区内节点连到社区外的连接数之和;RC 以 d_out/|Cᵢ| 累计,反映社区间的分离程度,外连越少越分离。

两种指标分别刻画划分质量,遗传算法需按多目标方式比较候选划分,避免只优化一个指标而损害另一个。注意书中式(1-20)把 RC 也印成带负号的最小化目标,与“反映分离程度”的文义方向不一致,使用前应核对原论文。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 . 5 基 于 遗 传 算 法 的 社 区 检 测 · 查看原书依据

      对于多目标遗传算法的社区检测,其目标函数的数学模型可以表示为: 第一个目标函数NAR(NegativeRatio Association)反映了社区内节点连接的紧密程度,第二个目标函数RC(Ratio Cut)反映了社区间的分离程度。这两个目标函数是由模块密度函数D分离得到的。

    参考来源

    - 位置:《智能算法导论》第 1 章 1.5.1 节“多目标遗传算法”(`EPUB/xhtml/chapter1_0013.xhtml`)。 - 结论依据:原文将无向网络的社区检测写为 NAR 与 RC 两个目标,并说明其分别反映内部连接和外部分离。 - 原始内容:第一个目标函数NAR(NegativeRatio Association)反映了社区内节点连接的紧密程度,第二个目标函数RC(Ratio Cut)反映了社区间的分离程度。