封面图

说明：网络信息挖掘，或称图挖掘，是数学中的图论、物理中的统计力学和计算机科学中的离散数学与算法等方向共同感兴趣的一个研究领域，致力于从网络中挖掘有重要价值的信息，狭义而言可以看作数据挖掘面对网络对象的一个分支！

我最近受汪秉宏老师和《科技成果管理与研究》杂志社要求，简要总结近年来在网络信息挖掘方面的相关工作。

下面主要分为识别网络中起关键作用的节点，预测网络中缺失的链路和向用户进行个性化推荐三个方面进行介绍。

第一部分：关键节点挖掘

由于真实网络的异质性，节点在网络结构和功能上发挥的作用差异巨大。关键节点就是那些能够在更大程度上影响网络的结构与功能的一些特殊节点。

准确发掘出网络中的关键节点，可以帮助我们更好地控制信息的传播、抑制疫情的爆发、精准投放商品广告、预测热门研究成果、发现重要致病基因等等[1]。

我们在这方面的工作可以粗糙地分成以下四个方面。

一是改进经典的PageRank算法，使之能够更快速、更准确的发现社会网络中的意见领袖。

Google最初用于网页排序的著名的PageRank算法，也可以应用于挖掘社会网络中的意见领袖，但该算法无法在一个统一的数学框架下处理出度为零的节点，其性能受到一个名为“跳转概率”的参数的影响——如何确定该参数的取值是一个很头痛的问题，因为这个值可能会随着网络的演化而不断变化。

我们提出了一种名为LeaderRank的新算法[2]，该算法引入一个“超级节点”，与每个节点都有双向边相连，从而把整个网络连接成一体，保证每个节点的出度都至少为1，并且可以保证算法的收敛性。

特别重要的是，该算法是一个无参数的算法，所以对数据的变化具有天然的适应性。以著名社会书签网站delicious.com的数据为对象，我们比较了PageRank选出来的意见领袖和本文所提算法的意见领袖在传播能力上的差异。

结果显示，LeaderRank明显优于PageRank。另外，LeaderRank在面对随机噪音和蓄意恶意攻击时的鲁棒性也优于PageRank。我们还给出了包含一个参数（类似于PageRank）的含权的LeaderRank[3]，可以进一步提高甄别意见领袖的准确度。

二是提出若干评价网络中节点中心性（重要性）的指标。

节点的度和核数是最常见的刻画节点影响力的中心性指标。我们指出了节点度在刻画影响力方面存在局域化程度过高的缺陷，并据此提出了基于多阶邻居[4]和考虑局部集聚特性[5]和邻居连接模式[6]的新的中心性指标，在预测传播影响力的精确度方面获得了显著提升。

进一步地，我们还分析了核数存在分辨率过低和识别不了并没有真正位于网络中心地位的“假核团”的缺陷，并提出了通过度量各壳层间连接的多样性来排除“假核团”的算法[7]。

我们指出网络中存在冗余边，它们具有相对低的传播重要性但却导致了“假核团”的形成。通过过滤网络中的冗余边，并在剩余图上实施k核分解算法，核数在度量节点传播影响力的准确性明显大幅度提升[8]。

三是发现节点中心性重要指标之间的数学关系。

刚才我已经介绍了，节点的度和核数是最常见的刻画节点影响力的中心性指标。另外一个学者耳熟能详但是在网络科学中应用较少的指标，就是H指数，它度量一个科学家有最多有多少篇论文每篇被引用的次数都不少于这个篇数。我们把H指数引进网络中，认为一个节点的H指数如果是h，就说明这个节点有h个邻居，它们的度都不小于h。我们可以自然地定义一个算子H，它作用在一组实数上，返回一个非负整数，就是这组实数的H指数h（至多有h个数不小于h）。这个算子H作用在一个节点所有邻居的度上，就得到了这个节点的H指数。

让人惊讶的是，我们发现了一个网络中非常基本的定律，就是把这个H算子继续作用在节点邻居的H指数上，得到二阶H指数；再作用在二阶H 指数上，得到三阶H指数，依次类推。最后，这个值会收敛到核数。

换句话说，原来最重要但是看起来各自独立的三个节点度量指标：度、H指数和核数，可以通过一个简单的算子H连接起来——度、H指数和核数只是一连串作用的初态、中间态和稳态。实验表明，H指数也是一个很好的度量网络节点重要性的指标，综合表现比度和核数都好[9]。

我们进一步证明，在异步更新的条件下，H算子也会驱动导致这个值唯一收敛到核数，这就使得分布式地计算动态增长网络的核数变得可能。在此基础上，我们还进一步给出了提升收敛速度的若干算法[10]。

四是设计针对网络上特定动力学过程，挖掘重要节点的方法。

上面的研究都是只需要知道网络结构就可以对节点重要性进行排序。但实际上在不同的动力学参数条件下，网络中节点重要性的排序变化非常大，这就使得如果不考虑具体动力学的性质和参数，没有办法得到具有普适性的有效排序。

我们最近尝试分析传播动力学中具有代表性的离散SIR模型，通过对其t时步后的状态进行近似解析分析，我们得到了相应的节点影响力指标，它可以看作是著名的Alpha中心性指标的一个有限时间截断[11]。该指标在挖掘重要节点方面的表现远远超过了其他知名的结构性指标。

最后，我们还探索了关键节点挖掘在一些具体场景中的应用，包括早期发现有升职潜力或者离职倾向的员工[12]，早期预测哪些青年科学家会成为明日之星[13]，等等。

参考文献

[1] Lü, L., Chen, D., Ren, X. L., Zhang, Q. M., Zhang, Y. C., & Zhou, T. (2016). Vital nodes identification in complex networks. Physics Reports, 650, 1-63.

[2] Lü, L., Zhang, Y. C., Yeung, C. H., & Zhou, T. (2011). Leaders in social networks, the delicious case. PLoS ONE, 6(6), e21202.

[3] Li, Q., Zhou, T., Lü, L., & Chen, D. (2014). Identifying influential spreaders by weighted LeaderRank. Physica A, 404, 47-55.

[4] Chen, D., Lü, L., Shang, M. S., Zhang, Y. C., & Zhou, T. (2012). Identifying influential nodes in complex networks. Physica A, 391(4), 1777-1787.

[5] Chen, D. B., Gao, H., Lü, L., & Zhou, T. (2013). Identifying influential nodes in large-scale directed networks: the role of clustering. PLoS ONE, 8(10), e77455.

[6] Liu, Y., Tang, M., Zhou, T., & Do, Y. (2016). Identify influential spreaders in complex networks, the role of neighborhood. Physica A, 452, 289-298.

[7] Liu, Y., Tang, M., Zhou, T., & Do, Y. (2015). Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition. Scientific Reports, 5, 9602.

[8] Liu, Y., Tang, M., Zhou, T., & Do, Y. (2015). Improving the accuracy of the k-shell method by removing redundant links: From a perspective of spreading dynamics. Scientific Reports, 5, 13172.

[9] Lü, L., Zhou, T., Zhang, Q. M., & Stanley, H. E. (2016). The H-index of a network node and its relation to degree and coreness. Nature Communications, 7, 10168.

[10] Lee, Y. L., & Zhou, T. (2017). Fast asynchronous updating algorithms for k-shell indices. Physica A, 482, 524-531.

[11] Liu, J. G., Lin, J. H., Guo, Q., & Zhou, T. (2016). Locating influential nodes via dynamics-sensitive centrality. Scientific Reports, 6, 21380.

[12] Yuan, J., Zhang, Q. M., Gao, J., Zhang, L., Wan, X. S., Yu, X. J., & Zhou, T. (2016). Promotion and resignation in employee networks. Physica A, 444, 442-447.

[13] Zhang, C., Liu, C., Yu, L., Zhang, Z. K., & Zhou, T. (2017). Identifying the Academic Rising Stars via Pairwise Citation Increment Ranking. In Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint Conference on Web and Big Data, Springer, pp. 475-483.

DataCastle数据城堡