大规模动态图节点相似性度量方法研究

《大规模动态图节点相似性度量方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、：分类号单位代码：１０１４０密级：公开学号：４０３１５３１９１４◎ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕士学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ论文题目：大规模动态图节点相似性度量方法研究Ｒｅｓｅａｒｃｈｏｎｎｏｄｅｓｉｍｉｌａｒｉｔｍｅａｓｕｒｅｍｅｎｔｍｅｔｈｏｄｆｏｒｌａｒｅｙｇ英文题目：ｓｃａｈｌｅｄｙｎａｍｉｃｒａｇｐｔ论文作者：段锐丰指导教师：宋宝燕教授专业：计算机应用技术完成时间一：二○八年五月９申请辽宁大学硕士学位论文大规模动态图节点相似性度量方法研究Resear

2、chonnodesimilaritymeasurementmethodforlargescaledynamicgraph作者：段锐丰指导教师：宋宝燕教授专业：计算机应用技术答辩日期：2018年5月二○一八年五月·中国辽宁辽宁大学学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师的指导下独立完成的。论文中取得的研究成果除加以标注的内容外，不包含其他个人或集体己经发表或撰写过的研宄成果，不包含本人为获得其他学位而使用过的成果。对本文的研宄做出重要贡献的个人和集体均己在文中进行了标注，并表示谢意。本人完全意识到本声明的法律结果由本人承担。丨学位

3、论文作者签名：加羊支／ｇ年玄月Ｕ日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交学位论文的原件、复印件和电子版，允许学位论文被查阅和借阅。本人授权辽宁大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编学位论文。同时授权中国学术期刊（光盘版）电子杂志社将本学位论文收录到《中国博士学位论文全文数据库》和《中国优秀硕士学位论文全文数据库》并通过网络向社会公众提供信息服务。学校须按照授权对学位论文进行管理，不得超越授权对学

4、位论文进行任意处理。（）保密，在年后解密适用本授权书。（保密：请在“”括号内划Ｖ）授权人签名：指导教师签名：曰期：災／Ｓ年夯月１日日期：如尽年在月祝日摘要摘要图作为计算机学科中常用的一种数据结构，它可以有效地表达对象之间广泛存在的联系，比线性表和树更加复杂，具备更一般性的表达能力，如道路交通网问题、Web语义分析问题、社交网络分析、生物信息网、地理信息网等。越来越多的应用场景需要依靠图数据结构来处理，同时图数据规模的不断增大带来了诸多挑战和分析，对其进行相关研究有非常重要的意义。大规模动态图演化过程中节点相似度度量和聚类被作为一种图关系的基础研究

5、，该内容被众多学者进行深入研究。传统的研究大多集中静态图、累积动态图上相似子图查询和子图挖据的相关研究成果，本文研究大规模动态图演化过程中节点相似度度量和基于节点相似度的聚类。由于目前对于大规模动态图节点相似度度量和聚类研究较少，所以本文提出了大规模动态图中节点相似性分类度量方法。针对上述问题，本文提出了大规模动态图中节点相似性分类度量方法，该方法包括数据预处理处理、节点相似度计算、节点相似度分段。为了解决大规模动态图的存储和处理问题，本文采用了Spark分布式计算框架中的GraphX类库中的算子，该计算框架封装了图的基本计算类库，使得算法运行和实现较为高效。首先数据预处理阶

6、段，本文获得大规模动态图演化过程中快照的边集合和顶点集合，把边集合和顶点集合转化为两个nodes.csv、edges.csv文件，然后利用GraphX算子读取两个nodes.csv、edges.csv文件。其次节点相似度计算阶段，节点相似度计算可以分为相邻节点相似度计算和连续时间段的节点相似度计算（非相邻节点相似度计算），nodes.csv、edges.csv文件作为计算节点相似度的输入文件，根据边集合和顶点集合，利用GraphX计算相邻两个节点的相似度。在已知相邻节点相似度，利用相邻节点相似度计算连续时间段的非相邻节点相似度，该算法是一个递归算法，最终实现相邻节点相似度计算

7、和连续时间段的节点相似度计算。再次节点相似度分段阶段，根据时间序列约束的聚类方法，把节点相似度聚类为不同的簇分段，不同的聚类导致不同的段内相似度和段间相似度。对于聚类的分段结果，根据聚类结果评价公式计算Goodvalue值，选择Goodvalue值最大的聚类结果，作为最优的分段结果。I摘要最后通过在两个数据集的实验室，验证了本文算法在存储开销和执行效率上有明显的优点，然后根据不同数据集聚类产生的Goodvalue值，选择出不同数据集的最优分段。关键词：分布式,大规模图,相似度,聚类IIAbstractA