基于纯策略博弈的边流图划分研究

作     者：李阳阳 

作者单位：华中科技大学 

学位级别：硕士

导师姓名：华强胜

授予年度：2018年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：边流图划分 并行划分 纯策略博弈 纳什均衡 

摘      要：在大图上开展图计算,图划分是一个至关重要的先序步骤。已有的图划分模型包括离线图划分和流图划分。在传统的流图划分模型中,当前边(顶点)需要根据先前到达顶点的划分块选择信息帮助当前边(顶点)选择最佳划分块。因此,在传统流图的划分模型中很难并行地开展划分任务。另一方面,离线图划分模型在划分过程中需要知道图的全局信息,很难适用于大规模图。针对现有图划分模型的不足,提出了一种近似流图划分模型。并基于该模型提出了一种基于纯策略博弈的边图划分算法。具体地,通过将图的边流划分成若干个批次,在每个批次内将图划分问题转化为一个博弈过程。批次内的每条边被视为博弈的玩家,每条边的划分块选择被视为其策略。从而将原图的划分问题分解为一系列寻找纳什均衡的过程。每个批次内的边选择其最佳划分块时,只依赖该批次内其它边的划分块选择,所以各个批次内的博弈过程可以并行地寻找纳什均衡。首先通过设计适当的个体代价函数和社会福利函数构造一个博弈过程,并证明了该博弈过程是一个确切势博弈,从而一定存在纯策略纳什均衡。然后基于最佳动态响应提出了一个能快速收敛到一个纯纳什均衡的算法。最后经过实验论证,在多个真实图数据集和随机图数据集上,基于博弈的划分算法和已有的流图划分算法相比,顶点平均备份数指标下降百分比最高为31.8%,边数标准差最好情况下降44倍。