大数据研究中心周涛教授在《自然-通讯》发表论文

26.01.2016  17:55

  近日,我校大数据研究中心周涛教授在《自然-通讯》上发表题为“网络节点的H指数以及其与度和核数之间的关系”(The H-index of a network nodeand its relation to degree and coreness)的论文。该文发现了度量网络节点重要性的三个著名指标——度、H指数和核数——之间优美的数学关系。周涛教授给出了相应定理的严格证明,系文章的共同第一作者。

 

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

  最近,Kitsak等人在《自然-物理》撰文指出,度只能刻画节点周围局部的特征,远远不能描述一个节点在传播动力学中的重要性,而用节点的核数(coreness)可以更好度量节点的重要性。一个节点的核数,就是网络在进行k核分解(k-core decomposition)过程中节点所在的最大阶核的阶数。对于一个网络,0核是原图;1核就是去掉所有孤立点的图;2核就是先去掉所有度小于2的点,然后在剩下的图中再去掉度小于2的点,依次类推,直到不能去掉为止;3核就是先去掉所有度小于3的点,然后再剩下的图中再去掉度小于3的点,依次类推,直到不能去掉为止……

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

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

  《自然-通讯》(Nature Communications)是Nature Publish Group旗下的Nature子刊之一,是国际著名综合性科学期刊,报道最新的电子学、生物学、物理学、新材料、能源、医学等领域研究进展,其2015年最新影响因子为11.47。由于本定理的重要性,自然子刊罕见地在正文中刊出了证明的主体。


论文链接(可免费下载):

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