结合节点属性的大规模图数据划分方法及其在社会网络上的应用研究

Large-scale Social Network Analysis becomes an important field of big-data research. It's a big challenge to support it efficiently for system software, since Hadoop has its inner limit for processing graph data and at the same time general graph processing systems are far from being perfect. One big problem is graph partitioning in distributed storage. However, present graph partitioning leads to high communiation overhead and low efficiency. This project mainly studies graph partitioning method and strategy in the context of Social Network Analysis. First, it will learn the similarity model between social network nodes with consideration of both node attributes information and graph structure information. Then, it will develop an ensemble learning-based graph coarsening algorithm under multi-level graph partitioning frame. Finally, it will implement the whole graph partitioning strategy of social network in parallel. This project not only supports the fulfillment of Large-scale Social Network Analysis directly by implementing more efficient graph partitioning strategy, but also has significant impact on fulfillment of large-scale graph data analysis and improvement of distributed computing infrastructure.

随着互联网的发展，大规模社会网络分析研究成为大数据研究的一个重要方面，也对分布式系统软件提出了新的要求。Hadoop系统处理图结构数据存在固有局限，而通用分布式图处理系统尚不完善，其中一个关键就是大规模图分布式存储中的图数据划分问题。目前通用图处理系统中的图数据划分方案导致了计算节点间巨大的通信开销，严重影响了数据处理效率，成为制约上层应用的障碍。本项目针对这一现状，结合社会网络分析应用对分布式图处理系统中的大规模图数据划分方法进行研究，首先通过结合社会网络节点的属性信息和图的结构信息学习得到合理的节点相似性度量模型；然后在多层图划分框架下开发设计一个基于集成学习思想的图粗糙化算法；最后并行实现整个大规模图数据划分方案。本项目研究不仅对大规模社会网络分析的高效实现提供了直接的系统软件支持，而且对通用大规模图数据分析的实现以及分布式计算基础设施的完善均具有重要的意义。

如何将大规模的图数据在分布式环境下进行合理划分和部署，是大规模图数据处理与应用的一个共同问题。当图处理面向一个特定应用领域时，其计算效率不仅与图本身的结构有关，同时还与数据在该领域的解释有关，因此应用领域所包含的语义信息也是针对该领域图数据进行有效划分的重要依据。本项目研究主要从两个方面进行，在理论与算法研究方面，主要集中在优化问题求解包括优化算法的收敛性、概率度量空间理论、贝叶斯统计，以及对一些行之有效的优化算法进行研究；在应用方面结合社会网络这一应用领域的特点，分别从文本信息处理、图像分析、知识图谱等角度对社会网络节点所包含的语义信息进行研究与综合，为进一步高效实现大规模社会网络分析提供有效的依据。.围绕本项目研究内容，项目组发表论文23篇，申请发明专利1项。其中国际期刊论文3篇、国际会议论文13篇和国家A类学术期刊论文3篇，成功组织承办第五届全国社会媒体处理大会（SMP2016）、第十四届自然语言处理青年学者研讨会(YSSNLP2017)和第十五届全国机器翻译大会（CCMT2019）。培养统招硕士毕业生11人，完成了项目计划书中预定的各项任务。