知识卡片
模块度密度化为双目标
模块度密度 D 用来给一个社区划分 S = (V1, …, Vs) 打分(式 5-7):
D = Σi [L(Vi, Vi) − L(Vi, V̄i)] ÷ |Vi|
- L(V1, V2) = Σ Aij(i ∈ V1,j ∈ V2),Aij 为邻接矩阵元素,有边为 1。
- L(Vi, Vi):社区内部节点的内度之和,社区内每条边计两次。
- L(Vi, V̄i):社区节点连向外部的边数(外度之和),V̄i 指 Vi 以外的节点。
- |Vi|:社区的节点数,用于按规模归一化。
示例(补充演算):4 个节点,边为 1–2、3–4、2–3,划分 V1 = {1, 2},V2 = {3, 4}。V1 的内度和为 2、外度和为 1,得 (2 − 1)/2 = 0.5;V2 同理为 0.5,所以 D = 1。
最大化 D 偏向内部连接密、外部连接少的划分。原书随后把它拆成 NRA 与 RC 两个最小化目标:RC = Σ L(Vi, V̄i)/|Vi|,最小化它就是减少社区间连边。但式(5-8)把 NRA 写成内部连边的正和 Σ L(Vi, Vi)/|Vi|,最小化它会压低社区内部连接,与最大化 D 的方向相反;只有把 NRA 取为负号,即 −Σ L(Vi, Vi)/|Vi|,才有 D = −(NRA + RC)。应用该双目标式前需自行核对符号,不能视作已证实的等价变换。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 5 . 4 基 于 蚁 群 算 法 的 社 区 检 测 · 查看原书依据
模块度密度D的定义为 1212 式(5-7)中,每一个求和项的分子表示的是子图节点的内度之和减去其节点的外度之和,分母表示该子图的节点数目。社区检测问题就可以看作是找到一个划分,使得模块度密度D的值最大的优化问题。
参考来源
- 位置:《智能算法导论》第 5 章“5.4 基于蚁群算法的社区检测”(源文件:`_epub-src/EPUB/xhtml/chapter5_0008.xhtml`);式(5-7)–(5-10),`EPUB/images/image_205.svg`、`image_208.svg`–`image_211.svg`。
- 结论依据:式(5-7)定义 D 为归一化的社区内连边减外连边;已回看原 EPUB 的公式 SVG,式(5-8)将 NRA 写成内部连边的正和,而式(5-10)要求最小化 NRA,方向冲突。4 节点网络的 D 值演算为依据式(5-7)补充的教学示例,非书中数据;“NRA 取负号才满足 D = −(NRA + RC)”是依据原书推导式整理的结论。
- 原始内容:式(5-7)中,每一个求和项的分子表示的是子图节点的内度之和减去其节点的外度之和,分母表示该子图的节点数目。社区检测问题就可以看作是找到一个划分,使得模块度密度 D 的值最大的优化问题。