网络节点度、H指数与核数之间的优美关系
周涛  |  2016-01-15  |  科学网  |  526次阅读

 

网络是由节点和链路组成的系统,刻画网络节点重要性对于理解网络结构、演化和其上的动力学过程非常重要[1]。刻画网络节点重要性的指标很多很多[1]。先考虑一个无向简单图。最简单的就是节点的度,等于节点直接邻居的个数。一般而言,我们认为度越大的节点越重要,例如在疾病流行过程和信息传播过程中,如果初始患病者/传播者在网络中度很大,那么疾病或者信息有更大可能在网络中扩散开来。

 

但是,衡量一个节点的重要性,远远不止那么简单。例如,Kitsak等人认为,节点度只能刻画节点周围很局部的特征,远远不能描述一个节点在传播动力学中的重要性[2]。Kitsak等人提出可以用节点的核数(coreness)来更好度量节点的重要性[2]。一个节点的核数,就是网络在进行k核分解(k-core decomposition)是的k-shell指数。对于一个网络,0核是原图;1核就是去掉所有孤立点的图;2核就是先去掉所有度小于2的点,然后再剩下的图中再去掉度小于2的点,依次类推,直到不能去掉为止;3核就是先去掉所有度小于3的点,然后再剩下的图中再去掉度小于3的点,依次类推,直到不能去掉为止……一个节点的核数定义为这个节点所在的最大核的阶数——比如一个节点最多在5核而不在6核中,就说这个节点的核数=5。

 

另外一个学者耳熟能详但是在网络科学中应用较少的指标,就是H指数[3],它度量一个科学家有最多有多少篇论文每篇被引用的次数都不少于这个篇数。我们把H指数引进网络中,认为一个节点的H指数如果是h,就说明这个节点有h个邻居,它们的度都不小于h。我们注意到,H指数也是一个很好的度量网络节点重要性的指标(而且很简单直观),综合表现比度和核数似乎都好。

 

我们可以自然地定义一个算子H,它作用在一组实数上,返回一个非负整数,就是这组实数的H指数(有多少数不小于多少)。这个算子H作用在一个节点所有邻居的度上,就得到了这个节点的H指数。让人惊讶的是,我们发现了一个网络中非常基本的定律,就是把这个H算子继续作用在节点邻居的H指数上,得到H2指数;再作用在H2 指数上,得到H3指数,依次类推。最后,这个值会收敛到核数。换句话说,原来非常非常重要(可能最重要将来也最常用),但是看起来各自独立的三个节点度量指标:度、H指数和核数,可以通过一个简单的算子H连接起来,而度、H指数和核数只是一连串作用的初态、中间态和稳态。我们进一步证明,在异步更新的条件下,H算子也会驱动导致这个值唯一收敛到核数,这就使得分布式地计算动态增长网络的核数变得可能。

 

通过对大量真实网络上各种动力学(SIR传播、SIS传播、Percolation等等)的实验表明,H指数,包括H2、H3指数、……、核数(H-family indices)等等,都能够很好地刻画网络的重要性,其中H指数综合表现最佳,应该可以说性价比很好。

 

这个工作也是很少见以两个定理的发现和证明为主的综合性期刊论文[4],是我最近最喜欢的一个工作,非常非常有趣,也希望大家喜欢!

 

[1] 任晓龙,吕琳媛,网络重要节点排序方法综述,科学通报 59 (2014) 1175-1197.

[2] Kitsak, M., Gallos, L. K., Havlin, S.,Liljeros, F., Muchnik, L., Stanley, H. E., & Makse, H. A. (2010).Identification of influential spreaders in complex networks. Nature Physics, 6(11),888-893.

[3] Hirsch, J. E. (2005). An index toquantify an individual's scientific research output. Proceedings of theNational academy of Sciences of the United States of America, 102(46),16569-16572.

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

 

全文免费下载链接:

http://www.nature.com/ncomms/2016/160112/ncomms10168/full/ncomms10168.html  





文章原载于作者的科学网文章,所述内容属作者个人观点,不代表本平台立场。
本文经过系统重新排版,阅读原内容可点击 阅读原文