知识卡片

普通读书笔记卡 · 1779.o

随机握手匹配只证到极大

理解等级:高级

左侧请求、右侧授予、左侧接受、右侧记录,按四阶段协调未匹配端点,避免一个端点同时选择多边。Pregel原论文明确该段是随机极大匹配,原书将其称最大匹配不准确;没有增广路径等额外机制,不能保证边数最优。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 图数据库:架构与算法 · 查看原书依据

      算法运行经过以下四个阶段。 阶段一:对于二部图中左端尚未匹配的节点,向其邻接节点发出消息,要求进行匹配,之后转入非活跃状态。 阶段二:对于二部图中右端尚未匹配的节点,从接收到的请求匹配消息中随机选择一个接收,并向接收请求的左端节点发出确认信息,之后主动转入非活跃状态。 阶段三:左端尚未匹配的节点接收到确认信息后,从中选择一个节点接收,写入匹配节点ID以表明已经匹配,然后向右端对应的节点发送接收请求的消息。左端节点已经匹配的节点在本阶段不会有任何动作,因为这类节点在第一阶段中根本就没有发送任何消息。 阶段四:右端尚未匹配的节点至多选择一个阶段三发过来的请求,然后写入匹配节点ID以表明已经匹配。 通过上述类似于两次握手的四个阶段的不断迭代,即可获得一个二部图最大匹配结果。

    参考来源

    - 位置:《大数据日知录:架构与算法》第14章《图数据库:架构与算法》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00019.html) - 结论依据:原文在本章对随机握手匹配只证到极大给出的定义、机制或示例支持本卡;技术产品描述限于2014年书中版本,示例与实测区分。 - 原始内容:算法运行经过以下四个阶段。 阶段一:对于二部图中左端尚未匹配的节点,向其邻接节点发出消息,要求进行匹配,之后转入非活跃状态。 阶段二:对于二部图中右端尚未匹配的节点,从接收到的请求匹配消息中随机选择一个接收,并向接收请求的左端节点发出确认信息,之后主动转入非活跃状态。 阶段三:左端尚未匹配的节点接收到确认信息后,从中选择一个节点接收,写入匹配节点ID以表明已经匹配,然后向右端对应的节点发送接收请求的消息。左端节点已经匹配的节点在本阶段不会有任何动作,因为这类节点在第一阶段中根本就没有发送任何消息。 阶段四:右端尚未匹配的节点至多选择一个阶段三发过来的请求,然后写入匹配节点ID以表明已经匹配。 通过上述类似于两次握手的四个阶段的不断迭代,即可获得一个二部图最大匹配结果。 - 生成时核验:[Pregel原论文5.3](https://dblab.xmu.edu.cn/wp-content/uploads/old/files/SIGMOD2010-pregel-a_system_for_large-scale_graph_processing.pdf),访问2026-10-24;原论文区分randomized maximal和maximum-weight算法。