知识卡片

普通读书笔记卡 · 3734.a.3

节点层迭代更新社区标签

理解等级:中级

节点层学习是多层局部搜索的最底层,直接改单个节点的社区标签:

  1. 把 N 个节点随机排成一个序列 R。
  2. 按 R 的顺序逐个取节点,用标签传播规则或其他融合策略更新它的标签。
  3. 重复整轮扫描,直到所有节点的标签都不再改变。

“标签传播”一般指让节点改用邻居中最常见的标签,使连得紧的节点逐渐同号;书中此处没有展开具体规则,这是该术语的通用含义。随机顺序可避免每次都按固定次序更新。它能让解快速收敛到局部最优;但标签停止变化只说明在这套规则下稳定,不能证明全局最优,原书正是让遗传算法帮它跳出局部最优。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 3 . 3 . 2 局 部 搜 索 · 查看原书依据

      给定一个N节点的网络G,节点层学习策略如下:首先生成一个随机序列R({r,r,…,rN}),然后根据序列中的顺序选择节点,利用标签传播规则或其他融合策略更新该节点的标签。重复上述过程直到每个节点的社区标签都不改变为止。

    参考来源

    - 位置:《智能算法导论》第 3 章 3.3.2 节“局部搜索”(`EPUB/xhtml/chapter3_0008.xhtml`);表 3.2。 - 结论依据:正文和流程表均给出随机节点顺序、逐个更新标签以及无变化时停止的步骤。“标签传播”取邻居多数标签的说法是该术语的通用解释,为补充铺垫,原书此处未定义具体规则。 - 原始内容:首先生成一个随机序列 R ({ r , r ,…, r N }),然后根据序列中的顺序选择节点,利用标签传播规则或其他融合策略更新该节点的标签。