网络重要节点及链路挖掘方法研究

Studies on complex networks become one of the most exciting domains of interdisciplinary researches. Identifying influential nodes and important links of networks attracts much attention, since it has both theoretical and practical significance. Research on this area can not only help to reveal microscopic structures of nerworks, but also provide assistant tools on analyzing network dynamics. Meanwhile, it can find real applications with great social and economic values. In this project, we will apply perspectives, theories and methods in statistical physics to find out the important nodes and links on networks, and further analyze their effects on network dynamics. With different ranking purposes, the corresponding algorithms will be designed based on the network structure. Especially, we will focus on the problem on multi-level networks, distinguish the different roles of nodes and links, and discuss how to utilize the features of network functions to identify the important nodes and links. Finally, we will conduct real experiments on WWW and mobile networks to test the algorithms. By analyzing the real behavior data, we can further improve the algorithms and develop applications in real systems.

复杂网络是交叉科学研究的重大热点，其中如何挖掘网络中的重要节点和链路受到越来越广泛的关注。这方面的研究不仅能够在微观层面上更加细致的剖析网络的结构特征，而且能够作为研究和分析网络动力学的辅助工具。同时，重要节点和链路的挖掘还能够产生直接的社会经济价值。本项目拟将统计物理的思路、理论和方法引入来解决节点和链路挖掘的问题，并利用相关结果分析网络动力学，实现从理论、算法、应用三个层面全方位推动相关研究。本项目将利用网络结构信息设计快速有效的重要节点/链路挖掘方法，针对不同的网络形式和排序目标讨论不同算法挖掘出的节点/链路对网络特定结构和功能的影响。特别关注多层网络上关键节点/链路的挖掘，区分链路的不同角色的方法，以及利用功能表征挖掘重要节点的反问题。本项目拟利用现有互联网和手机运营平台，设计和实现真实实验，获取无控制的真实行为数据，进行实验分析，检验和丰富理论研究的结果，并指导应用开发。

近年来，网络科学研究的热点逐渐从发现不同网络在宏观上的普适规律（小世界、无标度等）转变为着眼于从介观（社团结构、层级）和微观层面（节点、链路）去解释不同网络所具有的不同特征。节点和链路作为网络组成的最小单元对网络的结构和功能起到重要影响。特别是针对网络重要节点和链路的挖掘方法研究不仅能够在微观层面上更加细致的剖析网络的结构特征，还能够作为研究和分析网络动力学的辅助工具。本项目力图通过节点和链路重要性挖掘的深入研究解剖网络微观组织并籍此对网络宏观结构和宏观功能进行分析。本项目借鉴统计物理理论和方法解决节点和链路挖掘的问题，并利用相关结果分析网络动力学。代表成果：（1）首次揭示度中心性，H-指数和核数的内在联系，提出有效挖掘网络中高影响力节点的新算法，解决大规模演化网络的重要节点识别难题[Nature Communications 7:106168, 2016]；（2）首次提出网络链路可预测性的概念，并利用矩阵微扰理论给出定量化的刻画指标[PNAS 112(8):2325,2015]。. 本项目顺利完成预期目标：发表学术论文16篇，其中SCI论文12篇，EI论文4篇，发表期刊包括PNAS，Nature Communications，New Journal of Physics等。论文总引用152次，其中SCI引用66次，另有4篇在审。出版学术专著《链路预测》获得第四届中国大学出版社图书奖一等奖。在《科学通报》发表论文《网络重要节点排序方法综述》。申请发明专利6项。参与国内外学术会议20人次，其中邀请报告11次。培养博士研究生2名，硕士研究生4名。举办国内外学术会议和研讨会3次，总人数超过1500人，包括第九届全国复杂网络大会（>600），首届阿里巴巴复杂科学论坛（>700）和第十届网络科学论坛青年论坛（>200）。邀请国内外专家访问交流6人次。此外，建立学术交流网站（www.linkprediction.org），提供免费数据和相关资源。. 本项目不仅具有重要的理论研究意义，还具有直接的社会经济价值，部分成果已应用于电子商务服务、运营商流量管理、App和游戏推送等实际系统中。例如，本项目利用手机运营平台开发的短信高转发用户识别系统帮助运营商识别高转发率用户，提高短信收入；应用网络重要节点识别技术开发的基于社交网络的达人营销系统帮助淘宝中小卖家低成本引流。