知识卡片
节点层迭代更新社区标签
节点层学习是多层局部搜索的最底层,直接改单个节点的社区标签:
- 把 N 个节点随机排成一个序列 R。
- 按 R 的顺序逐个取节点,用标签传播规则或其他融合策略更新它的标签。
- 重复整轮扫描,直到所有节点的标签都不再改变。
“标签传播”一般指让节点改用邻居中最常见的标签,使连得紧的节点逐渐同号;书中此处没有展开具体规则,这是该术语的通用含义。随机顺序可避免每次都按固定次序更新。它能让解快速收敛到局部最优;但标签停止变化只说明在这套规则下稳定,不能证明全局最优,原书正是让遗传算法帮它跳出局部最优。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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 }),然后根据序列中的顺序选择节点,利用标签传播规则或其他融合策略更新该节点的标签。