面向大规模图数据的凝聚子图搜索技术研究

With the development of social network and mobile Internet, lots of applications and services based on graph data analysis and processing appear. Among them, cohesive subgraph search based on the graph data owns important social significance and commercial value. However, in this big data era, not only the volume but also the growing velocity of graph data are big, which brings great challenges to existing technology. In order to address this problem, this project focuses on the cohesive subgraph search problem in big graph data and aims to develop effective, efficient and scalable solutions for the cohesive subgraph search problem. Specifically, regarding effectiveness, this project introduces the relevance evaluation model to refine the search result and improve user experience. Regarding efficiency, this project develops online main memory algorithm through exploring the topological structure properties of cohesive subgraphs to further improve the search efficiency. Regarding scalability, this project leverages the external memory model and investigates the external memory cohesive subgraph search algorithm. To obtain a scalable search algorithm, this project stores the graph data and intermediate results on external memory and devises compact index to achieve the efficient cohesive subgraph search solution. The project can not only address the cohesive subgraph search problem in big graphs but also benefit the related real applications.

近年来，随着社交网络，移动互联网等技术的发展，基于图数据分析的应用大量涌现。其中，图数据上的凝聚子图搜索有着重要的社会意义和商业价值。但是，随着大数据时代的到来，图数据的规模不断增大，增长速度不断加快，给传统的搜索技术带来了极大的挑战。本项目围绕着大规模图数据上的凝聚子图搜索问题，从模型有效性、算法高效性和可扩展性三个方面对该问题进行深入研究。在模型有效性方面，本项目将引入结果相关性评价模型，改善搜索结果质量，提高用户体验。在算法高效性方面，本项目将结合凝聚子图的结构特点，挖掘基于内存计算模型的在线搜索算法的潜力，提高搜索性能。在算法可扩展性方面，本项目将研究基于外存计算模型的高效凝聚子图搜索算法，通过将图数据和相关信息存放在外存中，同时设计外存索引结构来实现可扩展的高效凝聚子图搜索。本项目的研究将解决面向大规模图数据的凝聚子图搜索中存在的问题，为相关实际应用打下坚实的基础。

近年来，随着社交网络，移动互联网等技术的发展，基于图数据分析的应用大量涌现。其中，图数据上的凝聚子图搜索有着重要的社会意义和商业价值。但是，随着大数据时代的到来，图数据的规模不断增大，增长速度不断加快，给传统的搜索技术带来了极大的挑战。本项目围绕着大规模图数据上的凝聚子图搜索问题，从模型有效性、算法高效性和可扩展性等方面对该问题进行深入研究，提出了包括(k,τ)-truss模型，高效可扩展极大平衡团在线搜索方法，基于索引的(α,β)-core高效可扩展搜索方法等，有效地提高了凝聚子图的搜索效率，为面向大规模图数据的凝聚子图搜索提供有效、快速、可扩展的技术解决方案，为相关实际应用打下坚实的基础。