大图数据半外存最大独立集求解算法研究.pptVIP

目 录 选题背景与意义 研究现状 研究内容 研究难点与创新 研究时间安排 主要研究内容 研究时间安排 2015年1月至2015年2月 Greedy算法实现 One-k-swap算法实现 Two-k-swap算法的设计与实现 2015年2月至2015年4月 真实数据集和人工数据集整理及测试 2015年4月至2015年5月 完成毕业论文及答辩 研究时间安排 感谢各位老师指导纠正！ 　　 大图数据半外存最大独立集求解算法研究 答 辩 人 ： 杨 华 指 导 老 师： 陆嘉恒 教授 专 业： 计算机软件与理论 目 录 选题背景与意义 研究现状 研究内容 研究难点与创新 研究时间安排 目 录 选题背景与意义 研究现状 研究内容 研究难点与创新 研究时间安排 选题背景与意义 大图数据（Big Graph） Social network graph（vertices 60M, … 100M） Citational Network Graph of Literary Theory Journals Web_uK, Twitter, facebook…. 选题背景与意义 独立集（Independent Set, IS） 对图G=(V,E)，G的独立集I定义为： 1)I是V的子集； 2)任意u, v I，满足(u, v) E。 选题背景与意义 极大独立集(Maximal Independent Set)和最大独立集(Maximum Independent Set, MIS) 对图G=(V,E)的独立集I，如果不存在独立集I’，使得I I’，称I为极大独立集； G的独立集中基数(cardinality)最大的独立集称为最大独立集。（最大独立集不一定唯一，且必为极大独立集。） 独立集问题的实际意义 地图标注(Map Labeling) 地图标注为节点 标注对角线为边 最大不重叠的标记 最大容错编码 给定容错条件，求最大编码集合 每个编码为点，小于容错距离的编码差距为边 最大独立集为合理编码方案 选题背景与意义 独立集问题的实际意义 MIS在大图可达性查询中的应用 最大独立集对图进行分层 分层进行label，降低label的数量 其他应用 计算机视觉/模式识别 市场图（Market Graph） 选题背景与意义 目 录 选题背景与意义 研究现状 研究内容 研究难点与创新 研究时间安排 研究背景 近似计算最大独立集的内存算法 贪心算法 Greedy Algorithm.贪心算法每次选取图中度最小的点加入独立集，并且将其和其邻居从图中除去，在剩余的图上重复该算法直至结束。 H.Y. LAU et al, The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set, Journal of Combinatorial Optimization, 2001 研究现状 研究背景 近似计算最大独立集的内存算法 局部优化算法框架 1994年SODA的一篇文章上给出了多项式时间的近似算法，该算法通过每次考虑是否用一个较大的独立子集替换现有独立集的部分，得到更大的独立集。然而算法从理论上给出了一些替换策略，但很难实际应用。 Piotr Berman et al, Approximating maximum independent set in bounded degree graphs, SODA 1994. Swap局部优化算法 0-1-swap、1-2-swap算法。只考虑加入一个点（0-1置换）或用两个点置换一个独立集结点（1-2置换）。如果选取的独立集为极大的，则不存在0-1置换。该算法是多项式时间的，然而论文未给出实现方式和具体算法。 SANJEEV KHANNA et al, On Syntactic versus Computational Views of Approximability, SIAM Journal on Computing , 1999. 研究现状 研究背景 （近似）计算最大独立集的外存算法 遍历图G，容易得到一个极大独立集。通过维护一个外存上的优先队列（Priority Queue），该算法需要的内存空间小于|V|。该算法的主要缺点是对于求得的独立集大小没有理论保证，实际中求得的结果一般明显小于贪心算法等的结果。 N.Zeh, I/O-Efficient Algorithms for Shortest Path Related Prob