大规模复杂网络的多元结构发现方法及应用研究

Structure discovery is a hotspot in the domains of complex network, data mining, among others, which is of fundamental importance to address the core tasks of network theory such as analyzing the composition of network systems, understanding the intrinsic relationship between structure and function, and predicting the dynamics of network systems, and has been extensively applied to different kinds of network data analysis. In spite of significant progress having been made toward structure discovery, one critical but tough issue remains unresolved, i.e. how to efficiently and effectively discovery significant structural patterns from large-scale networks with zero priori knowledge. Completely distinct from the methodologies adopted by existing works, this project aims at developing the theory of stochastic blockmodelling and then based on it proposing a method of discovering multiplex structure, from a new perspective of integrating different kinds of structures, which is able to autonomously make proper decisions about “what to discover” and “how to discover” from networks in question. The novel method models the task of structure discovery as three sub-tasks of representation, learning and extraction. Compared with the state-of-the-art methods of structure discovery, the novel method enable us to correctly detect miscellaneous structures coexisting in the same network as well as the complicated relationships among them, hence providing a more powerful way to reveal how the macroscopic functions and dynamics demonstrated by networks are synthesized by the collaboration of coexisting structures. However, the task of discovering multiplex structures from large-scale networks is much more challenging than that of discovering singleton structure mainly because it involves more structures and relationships, much more complicated description models and a much huger model searching space. Especially, the computational complexity of discovering multiplex structures can not be lowed by merely utilizing the feature of a certain singleton structure. In order to adequately address the aforementioned challenges, the project will extensively study relevant theories, models, algorithms and case studies. The implementation of this project will deepen, promote and expand the studies and applications of structure discovery, respectively.

结构发现是复杂网络和数据挖掘等领域的研究热点，对分析网络系统的组成方式、理解结构与功能的内在联系、预测网络系统的动力学行为都有十分重要的意义，在网络数据分析中有广泛应用。尽管相关研究已获重要进展，但如何从零先验知识的大规模网络中发现有意义的结构这一关键问题仍未被很好解决。本项目拟从“将多种结构统一起来研究”的新角度出发，在发展现有随机块模型的基础上，提出能够自主决策从网络中“发现什么”及“如何发现”的多元结构发现方法。该方法将结构发现建模为“表示”、“学习”和“抽取”三个过程，与现有工作相比，能够从零先验知识的网络中正确发现共存的多种结构及结构间的复杂关系，更有助于揭示出网络的宏观功能是如何由多个基本结构协同产生的。由于考虑了更多的结构和关系，描述模型更复杂，模型搜索空间更大，无法只利用某一种结构的特性降低计算复杂性，因而从大规模网络中发现多元结构面临着更大挑战。为此，本项目拟深入开展相关理论、模型、算法及应用的研究。本项目的实施将深化、拓展网络结构发现的研究与应用。

结构发现是复杂网络和数据挖掘等领域的研究热点，对分析网络系统的组成方式、理解结构与功能的内在联系、预测网络系统的动力学行为都有十分重要的意义，在网络数据分析中有广泛应用。其研究已获重要进展，但如何从零先验知识的大规模网络中发现有意义的结构这一关键问题仍未被很好解决。由于考虑了更多的结构和关系，描述模型更复杂，模型搜索空间更大，无法只利用某一种结构的特性降低计算复杂性，因而从大规模网络中发现多元结构面临着更大挑战。为此，本项目深入开展了相关理论、模型及算法的研究。本项目取得的主要创新点是：. 1）从“将多种结构统一起来研究”的新角度出发，首次提出了多元结构概念，将网络结构分析从最初的单一结构发展到多元结构，研究手段也相应地从社区发现发展到探索式结构发现； . 2）提出了能够自主决策从网络中“发现什么”及“如何发现”的多元结构发现方法。不同于现有工作，该方法能够从零先验知识的网络中正确发现共存的多种结构及结构间的复杂关系，更有助于揭示出网络的宏观功能是如何由多个基本结构协同产生的，被视为认知复杂系统微观、中观和宏观结构的代表性方法；. 3） 将网络多元结构分析方法应用于社会化信息检索和计算流行病学等领域，提出基于信任的社会化协同过滤推荐算法，基于网络多元结构分析的新型网页排名算法，更好的解决了数据稀疏和冷启动问题，提出了异构传播网络概念和基于开源异构数据挖掘的传染病追踪、主动监控和早期预警方法，对构建传染病的主动防控策略具有重要意义。. 这些工作系统解决了复杂网络多元结构分析的一些理论难题，初步建立了多元结构分析的理论框架，深化和推动了网络结构发现在社会化信息检索和计算流行病学领域中的应用。项目组在IEEE TPAMI、IEEE TKDE、AAAI等人工智能和数据挖掘领域的顶级期刊和会议上发表论文35篇，其中包括：SCI论文19篇， CCF A类论文9篇，CCF B类论文3篇，中科院一区论文2篇，中科院二区论文10篇，出版中文专著1部，英文专著章节1章，获得国家专利2项。获2017年吴文俊自然科学二等奖1项，吉林省自然科学二等奖1项，中国商业联合会一等奖1项。本项目的相关工作引起国内外同行的广泛关注，多次被国际著名学者，以及人工智能和数据挖掘领域的顶级期刊和会议论文介绍、评价和对比。