← 返回刚才阅读的位置

知识卡片

结构图卡 · 3734.a.3.a.2

多层蚁群反复聚合社区

理解等级:中级

MABA 把蚁群与模拟退火、标签传播结合,并以 SABA 为子方法。局部模块度 Q 用来给当前社区划分打分:社区内连得更密、社区间连得更稀时 Q 通常更高。流程是:在当前网络上用 SABA 搜社区 → 把每个社区收成上层网络的一个点 → 再对这个更粗的网络跑 SABA → 比较 Q;Q 还在增加就把上层网络当作新的“当前网络”继续,直到 Q 不再增加。这样搜索粒度一层层变粗,原书称可以缓解模块度优化的分辨率限制,但求解精度较低。Q 停止增加只是本流程的停止条件,不能证明全局最优。与[[社区层压缩为超级节点]]相似,聚合改变了搜索粒度。

结构图:

flowchart TD
  A[当前网络] --> B[SABA 搜索社区]
  B --> C[以社区构建上层网络]
  C --> D[计算局部模块度 Q]
  D --> E{Q 继续增加}
  E -- 是 --> A2[以上层网络作为当前网络]
  A2 --> B
  E -- 否 --> F[结束本轮多层搜索]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 5 . 4 . 2 社 区 检 测 问 题 的 改 进 · 查看原书依据

      He等提出将蚁群算法与模拟退火及标签传播算法结合形成MABA算法[43],它以SABA作为子方法,通过优化局部模块度函数Q,在已获得的网络社区结构上构建一个上层网络,再将SABA作用于新的上层网络,如此迭代直到Q值不再增加。

    参考来源

    - 位置:《智能算法导论》第 5 章 5.4.2 节“社区检测问题的改进”(`_epub-src/EPUB/xhtml/chapter5_0009.xhtml`)。 - 结论依据:原文写明 MABA 以 SABA 为子方法,通过优化局部模块度 Q,在已获得的社区结构上构建上层网络,再将 SABA 作用于新的上层网络,迭代直到 Q 不再增加,并指出精度较低。结构图按“再作用于上层网络”修正回边,避免 Q 增加后仍搜旧网络。 - 原始内容:它以SABA作为子方法,通过优化局部模块度函数 Q ,在已获得的网络社区结构上构建一个上层网络,再将SABA作用于新的上层网络,如此迭代直到 Q 值不再增加。MABA虽然可以缓解模块度优化带来的分辨率限制问题,但是算法求解精度较低。