大规模网络子图模式快速挖掘方法研究

Exploring statistics of locally connected subgraph patterns (also known as network motifs) has helped researchers better understand the structure and function of biological and online social networks (OSNs). In practice, issues such as the unavailable topology of the network of interest, the large size of the network, the large number of subgraphs, and the intensive computation of listing all subgraphs make it a challenge to accurately discover subgraph statistics. In this project, we will propose crawling and sampling methods to efficiently collect data from the network of interest. We will build models to analyze and correct the errors introduced by the data collection methods. When the network is given, we will develop sampling methods that efficiently and accurately estimate subgraph characteristics of large static graphs and dynamic streaming graphs. Moreover, we will develop subgraph sampling systems based on the current popular graph computing platforms. The methods and systems developed in this project will strongly support many applications such as network traffic monitoring, online social network analysis, and biological network mining.

挖掘大规模网络中局部连接的子图模式（或称为网络模体）对于理解生物网络和在线社会网络的结构和功能有着重要的意义。实际应用中，存在网络结构未知、网络规模大、子图数目海量、子图模式分析运算大等问题和挑战，这使得准确快速的分析大规模网络图的子图模式变得相当困难。本项目针对此问题展开研究：拟设计网络爬虫和采样的方法来获取未知网络的拓扑结构，同时对数据获取过程中引入的偏差进行建模分析，进而得以补偿修正；拟分别设计适用于大规模静态图和高速动态流图的子图采样无偏估计方法，并研究算法的并行化技术；拟研究的子图采样估计方法采用目前流行图计算系统平台的计算范式，研发基于各流行图计算系统平台的子图采样估计系统。本项目的研究成果能够用来准确快速的挖掘估计子图模式的特征值（如某种子图模式出现的次数），为计算机网络流量监控、在线社会网络分析和生物分子网络信息挖掘提供重要技术手段。

针对大规模网络中局部连接的子图模式的挖掘，项目组展开了一系列的研究。在网络数据收集发现方面，提出基于随机游走的网络数据快速获取技术，基于马尔可夫模型对由数据采集过程中引入的偏差进行建模分析，进而给出了有效的偏差修正模型，解决了深网子图模式难以准确获取的难题，为深网用户画像和行为监控奠定了基础。提出的深网数据采集方法利用马尔科夫模型对数据采集引入的测量误差进行精确的建模分析，进而制定快速且偏差可计算修正的采样策略，在原图上随机游走实现对节点或者子图的快速采集，进而通过对深网小规模的数据获取即可实现对深网节点属性和用户群体知识的准确获取，在同等实验对比条件下，数十倍的减小了已有方法的估计误差。在大图子图挖掘方面，提出基于采样技术的子图挖掘分析方法，解决了现有子图挖掘方法计算量大、分析时间和精度不可控的问题，为复杂网络高阶结构特征分析奠定了基础。针对具有数亿条边的静态大图，提出的基于路径采样和T型树采样的子图频数估计方法，将3至5节点全局和局部子图频数计算时间从数十天降为数分钟，估计误差小于1%。针对大规模高速流图的挖掘分析，提出的基于随机边采样的数据稀疏采样技术，可以有效控制计算和存储上的代价。该技术实现了在数十倍数百倍缩减原流图规模的同时，仍可以准确估计原图子图频数的良好效果。. 基于上述研究，项目组在IEEE TKDE、IEEE TPDS、IEEE Internet Computing、ACM TKDD、Information Sciences等高水平国际期刊，以及SIGKDD、VLDB、ICDE、INFOCOM、WWW、IJCAI等高水平会议上发表论文23篇，其中SCI论文13篇，CCF A类会议或期刊论文13篇，IEEE期刊论文5篇，申请国家发明专利4项（其中3项已授权），获得软件著作权1项。培养研究生8人，4人已毕业，指导学生发表论文10余篇。项目研究内容同时获得2017年CCF-腾讯犀牛鸟创意基金，研究内容和方向得到专家的认可，研究成果落地应用与腾讯公司。