物理视角的复杂网络

物理视角的复杂网络
复杂网络观察 *
 
吕琳媛 ** 1 ,陆君安 2 ,张子柯 1 ,闫小勇 3 ,吴晔 4,5
史定华 6 ,周海平 7 ,方锦清 8 ,周涛 9,10
(1. 弗里堡大学物理系,瑞士 弗里堡 CH – 1700
2. 武汉大学数学与统计学院,武汉 430072
3. 石家庄铁道大学交通运输学院,石家庄 050043
4. 波茨坦大学复杂系统动力学交叉中心,德国 波茨坦 D-14469
5. 北京邮电大学理学院,北京 100876
6. 上海大学数学系,上海 200444
7. 贵阳学院计算机科学系,贵阳 550005
8. 中国原子能科学研究院,北京 102413
9. 电子科技大学互联网科学中心,成都 610054
10. 中国科学技术大学近代物理系,合肥 230026)
 
摘要:本文总结了几位作者对复杂网络研究中存在的重要问题和发展趋势的讨论,其中既包括了度分布和度指数的分析和计算,各种不同动力学之间的内在一致性,网络加速增长机制这样的基本问题,也包括了网络中尺度这类的细致深入的结构分析。本文还就复杂网络与其他重要研究方向深入结合的现状和未来展开了讨论,包括复杂网络中的链路预测问题,复杂网络在信息推荐系统中的引用,复杂网络与信息物理系统的可能结合,复杂网络和人类动力学的结合以及复杂网络在国家安全方面可能的重要战略地位。
关键词:复杂网络、度分布、加速增长、同步、传播、网络交通、流驱动的动力学、中尺度、链路预测、推荐系统、信息物理系统、人类动力学
中图分类号:N94
文献标识码:A
 
 
Looking into Complex Networks
 
Linyuan Lü1, Jun-An Lu2, Zi-Ke Zhang1, Xiao-Yong Yan3, Ye Wu4,5,
Ding-Hua Shi6, Hai-Ping Zhou7, Jin-Qing Fang8, Tao Zhou9,10
(1. Department of Physics, University of Fribourg, Fribourg 1700, Switzerland
2. School of Mathematics and Statistics, Wuhan University, Wuhan 430072
3. Department of Transportation Engineering, Shijiazhuang Tiedao University, Shijiazhuang 050043
4. Interdisciplinary Center for Dynamics of Complex Systems, University Potsdam, Am Neuen Palais 10, D14469, Germany
5. School of Science, Beijing University of Posts and Telecommunications, Beijing 100876
6. Department of Mathematics, Shanghai University, Shanghai 200444
7. Department of Computer Science, Guiyang College, Guiyang 550005
8. China Institute of Atomic Energy, PO Box 275-81, Beijing 102413
9. Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 610054
10. Department of Modern Physics, University of Science and Technology of China, Hefei 230026)
 
Abstract: This article summaries the discussions about the open issues and research tendency of complex networks by several active scholars. The statement covers both fundamental problems like the understanding of power-law degree distributions, the underlying connections between different flow-driven dynamics and the mechanism leading to acceleratingly growing, and the in-depth analyses like the understanding of mesoscales in complex networks. Moreover, we introduce some typical interdisciplinary studies where complex networks play a major role, including the link prediction in complex networks, recommender systems for user-object bipartite networks, the integration of cyber physical systems and complex networks, the human dynamics in the online network space, and the possibly important role of the studies of complex networks in national security.  
Keywords: complex networks, degree distribution, acceleratingly growing, synchronization, epidemic spreading, network traffic, flow-driven dynamics, mesoscales, link prediction, recommender systems, cyber physical systems, human dynamics
 
引言
如果从1998年Watts和Strogatz提出小世界网络模型[1],以及1999年Barabási和Albertt提出无标度网络[2]算起,复杂网络这个研究领域已经走过了它的第一个十年。即便去除掉开创时期的文章,仅2000-2009十年间发表的明确以“复杂网络”(complex networks)为主题(topic)的SCI论文就达到了4925篇之多,引用高达76834次,而且依旧呈现强劲的上涨势头(图1)。得益于一些研究人员早期的推动,我国学者得以较早意识到复杂网络研究的重要性。如图2所示,复杂网络在我国呈现出了类似的迅猛发展的势头,在统计的SCI论文中,有中国地址的论文共有1318篇,超过了四分之一。
 
图1 :以复杂网络为主题的SCI论文数          图2 :以复杂网络为主题的含中国地址SCI论文数
 
在欣喜之余,我们也需要警醒,这1318篇论文获得的引用仅仅是7229次,还不到总数的十分之一,说明我国学者在复杂网络方面的研究工作距离世界平均水平还有比较明显的差距。本文正是在这种冷静的兴奋,谨慎的乐观情境下对于复杂网络研究中存在的重要问题和发展趋势的一次集中讨论。从这些讨论中,可以看出,在复杂网络研究中作出真正重要的贡献,离不开“精深广”三字。
以前对于网络结构的刻画,要么很宏观,例如网络的连接密度和平均距离,要么很微观,从节点的局部性质入手,比如节点的度和簇系数。这些量都只能从比较粗糙的层面揭示网络的结构,而本文要述及的中尺度,包括模体、圈、核、群落等等,有望提供连接微观与宏观的桥梁——这类研究体现了从粗放到精细的趋势。以前对幂律度分布的拟合,往往是双对数坐标下简单的最小二乘法,拟合的好不好,也就是肉眼判断一下。如何判断一个分布是不是幂律的,幂指数如何确定,离散和连续分布的区别等等,最近又重新成为学术界争论的焦点——这类研究体现了从简浅到深刻的趋势。以前复杂网络的研究,大部分集中于网络结构分析和建模,对于网络功能的研究,也主要集中在传播、同步、交通、博弈等少数几个方面,虽然号称交叉学科,但和其他学科关系松散,基本上可以说是自娱自乐。本文介绍了复杂网络和链路预测、信息推荐、人类动力学等研究方向已经存在的深入结合,展望了其与信息物理系统的可能联姻——这类研究体现了从狭促到广阔的趋势。
本文将尽最大可能忠实于原作品的风格,希望能对我国学者在复杂网络方面的研究提供借鉴。
 
几何增长网络的度分布和度指数
自从Barabási等人[3] 利用模块增长构造出第一个确定性的层次网络起,层次网络 [4-6] 、伪分形图[7-9]、阿波罗网[10-13]等几何增长网络的度分布和度指数就一直是颇有争议的问题。 [3] 首先得到了第一个确定性的层次网络度概率的尾部呈现幂律,度指数是 3 的对数与 2 的对数之比。后来觉得不妥,他们在 [4] 中又给出了该层次网络度概率密度的尾部,也呈现幂律, 度 指数是 1 加上 3 的对数与 2 的对数之比 。 [7] 采用补分布方法,首先求出了 伪分形图的 补分布,然而表达式是一个离散的幂律, 得到了 伪分形图 的度指数为 1 加上 3 的对数与 2 的对数之比。 [10] 引入了阿波罗网络, 用补分布方法求出了 阿波罗网络度的 补分布也是一个离散的幂律, 度指数为 1 加上 3 的对数与 2 的对数之比 。不知何故,然后 [10] 的作者 在 [13] 中又将度指数更改为 3 的对数与 2 的对数之比 。
由于几何增长网络不仅突破了每次只增加一个结点的限制,而且因其特殊的拓扑性质 ( 自相似和高群集 ) ,以及便于精确解析广泛受到网络界的青睐。然而,几何增长网络的正确度分布 ( 概率、密度、补分布 ) 是什么?正确的度指数需不需要在两个对数之比基础上 加 1 。 文献上对这个问题的认识就像过山车一样,迄今没有一个令人信服的说法。 因为这类网络度的非零概率一般都是幂律,但其中存在几何增长的度概率为零的区间,使得网络是否无标度和度指数难于决断。而且这种现象在实际网络统计和模型网络模拟中也经常会遇到。这就引发了如何准确判断一个网络的度分布是否为无标度,以及如何确定其度指数的重要问题。我觉得这或许会是 “ 复杂网络圈 ” 的一个好论题。
首先关于幂律和标度要有一个正确的定义,文献 [14] 对确定的和随机的两种情况都有详尽的论述。如果确定的单调递减序列或随机的补分布函数存在一个常数使得序列值或函数值能够表示为正比于幂律的形式,那么就称为 无标度的, 幂律指数,即那个常数除掉负号就称为标度指数。对随机的情况,如果存在密度函数,密度函数也是幂律,但标度指数需要加 1 。不过要注意,在 复杂网络里, 无标度网络的度指数都是指概率密度的 标度指数,因此需要加 1 。 这可能是 Barabási 等人 [2] 在用平均场方法推导 BA 模型网络度分布时,得到的是 概率密度,现在已经 约定俗成,既不便更改也无须争辩 。
下面以伪分形图 [7] 为例子来讨论。 [7] 精确分析了该网络的结点度和结点数, 结点 只有 度 2, 22, 23,  ¼ ,2t-1, 2t, 2t+1 ,对应的结点数分别是 3t, 3t-1,3t-2 ¼  ,32, 3, 3 ,结点总数为 3(3t+1)/2 。于是, [7] 得到 该网络的 稳态 度概率是在 2, 22, 23,  ¼ 上取值的幂律,系数为 2 ,幂指数为 负 3 的对数与 2 的对数之比。 因为当中穿插了许许多多概率为零的度,这不是单调递减序列,所以无法判断。 [7] 采用补分布来绕开这个困难,给出了一个 离散幂律的表达式,幂指数仍为 负 3 的对数与 2 的对数之比,但指出 度指数是 1 加上 3 的对数与 2 的对数之比。随后 几何增长网络的 文献几乎都采用这种方法确定 无标度网和度指数。
我们现在来评论一下上述工作。 [7] 得到的 稳态 度概率是精确的, 度指数也是正确的。然而 补分布 表达式容易误解,对离散情况,众所周之 补分布应该是一个递减的连续阶梯函数。 正确的 补分布可以借助 Heaviside 阶梯 函数表示出来。另外, [4] 中给出的概率密度尾部也不准确,离散的概率密度也不是 单调递减序列。因此,对 几何增长网络, 我认为度分布最好采用 递减的连续阶梯函数 , 度指数是其幂指数 除掉负号后加 1 。如果采用度概率,必须说明定义域,度指数仍需在其幂指数 除掉负号后加 1 。
事实上,只有当度间隔为 1 的概率值 服从 幂律,才能直接得出无标度网和正确的度指数;否则需要采用 补分布方法。 实际网络统计和模型网络模拟都 会遇到在最小度和最大度之间出现 度概率为零的情况。如果只有偶尔几个零问题还不至于太大,若度概率为零的点比较多,问题就严重了。所以一般建议采用 补分布方法,即统计大于等于 度 k 的结点数与总结点数之比来画图,因为这样 更准确。 不过要注意,度指数是其斜率 除掉负号后加 1 。
(史定华)
 
网络同步、交通和传播动力学的内在一致性
2005年1月,Motter,昌松和Kurths在《美国物理评论E》上发表了一篇不算太难的文章[15],提出网络同步的时候,一个节点被耦合的强度总和应该归一。以前每一条边上的耦合强度都是1,那么一个度为 k的节点,被耦合的强度之和就是 k,现在要归一,就是要除以一个 k——这样得到一个归一化的拉普拉斯矩阵。这个方法虽然简单,但是原来同步能力很差的无标度网络[16],一下子同步能力就变强了。所以说很快就成为了网络同步研究中耳熟能详的著名方法,事实上,一多半的提高网络同步能力的尝试,都受到了这个方法的启发[17],而这篇论文在2005年《美国物理评论E》上发表的2590篇论文中引用排名第3名。
2006年2月和2006年4月,中科大小组接连在《美国物理评论E》上发表了两篇关于交通流的论文,前一篇是仅知道网络局部信息的交通流问题[18],后一篇是知道网络整体结构的交通流问题[19]。这两篇文章也是已发表就受到广泛关注,目前在2006年《美国物理评论E》上发表的2425篇论文中引用排名第6和第4。两篇文章都涉及到同一个问题,就是交通选路时选择短路和选择流量小的路之间的矛盾:如果总是走偏街背巷,尽管不会堵,但是太绕路,如果总是走大路,则有可能完全堵死。有趣的是,尽管两篇论文所利用的信息和路由策略非常不同,但是结论却很相似,前者发现最优的策略是按照与邻居度 k成反比传送信息包,后者指出最优路由策略可以通过按照与节点度 k成正比的数值进行路径加权。
假设我们考虑一个带有自由参数 α的一个与度相关的量 kα,会发现这些最优值的位置简直太漂亮了,要么是1,要么是-1。尽管在一些假设的基础上,似乎也能够对这样的最优参数给出似是而非的解释,但是真正从头做起的完整的解析却很困难,因为同步能力中涉及的特征值问题和网络交通流中涉及的路径问题,都有巨大的复杂性。这里,我想特别强调的一点是,这些似乎很不一样的物理过程,都可以看做一种“流驱动的动力学”(flow-driven dynamics):同步中是耦合信号在传输,交通中则是信息包在传输,而更加直观的例子,是传播动力学,其中疾病在网络中传播。当然,这其中也有本质的不同之处,例如耦合信号之间互相可以干扰,信息包和疾病则不会;传染源可以复制,而信息包则不会。
因为看到了这种隐隐约约的内在的一致性,我希望能够找到一种非常简单但是又能体现这种流驱动的动力学本质的物理过程,并尝试一些解析。在所有流驱动的动力学中,接触过程( contact process)无疑是最简单的之一,所以我先以此为突破口。我们发现,如果允许一个个体在选择接触对象的时候(只能在邻居中选择),按照与其度 k的一个函数 f( k)成正比的概率选择,那么可以利用泛函变分的方法证明最优的函数是 f( k)=1/ k。注意,这里并不依赖于 f( k)的具体形式。这篇文章 2008年12月也在《美国物理评论E》上发表[20]。
得到这样的解析结果固然可喜,但是并不意味着我们真正理解了这些动力学之间的一致性,甚至不能表明时候真正存在某种有价值的一致性。流驱动的动力学是否拥有一些性质,在同步、交通和传播中都能表现出来呢?对我来说,依然是完全没有头绪的!
(周涛)
 
 
网络同步的中尺度分析
最近读了 CHAOS 20, 010202 ( 2010 )的专辑征稿文章: Announcement: Focus Issue on Mesoscales in Complex Networks ,觉得复杂网络中尺度( Mesoscales )问题的确是值得十分重视的研究方向,正如征稿文章指出的“专辑的目的是通过对复杂网络中尺度层次的研究来推进非线性科学特别是复杂系统的研究”。复杂网络中尺度并不是今天才提出来的,至少在 2006 年文献 [21] 中就明确提到网络的中尺度问题 , 不过这方面的成果似乎不多,而这个问题又十分重要,因此值得我们深入研究。
复杂网络可以在不同层次用不同尺度去刻画。在小尺度(微观、局部)层次,就是点和边的层次,可以讨论它的度、介数、聚类系数等属性,但是要刻画点和边的动力学就不能孤立静态地分析了。在大尺度(宏观、全局)层次,就是从网络的整体分析其参数的统计规律。文献 [21] 中指出,在这两种尺度中间,仍然存在一个包含各种不同尺度的很大的过渡空间,这就是所谓的中尺度。这些尺度可以理解为子结构(子图),相对于整个网络而言,子结构有自己的拓扑实体,例如模体( motifs )、小圈子 (cliques) 、核 (cores) 、环 (loops) ,或者更一般地说成社团。这里对中尺度的定义已经有初步的界定。目前对于大尺度和小尺度两头的属性,研究得比较清楚,可是中间层次的属性,很多都还没有搞清楚,就譬如社团发现问题至今仍然存在着争议。实际系统的社团的确定很难做到是唯一的,原因就在于不同的尺度会有不同的划分。
复杂动力网络的同步已经得到广泛的研究,目前主要集中在给定拓扑结构和动力学后判断网络能否最终达到同步,主要利用主稳定方法和 Lyapunov 方法(少数利用图方法),它是从大尺度来分析网络节点的集体行为。可以说它是一种只看结果(最终是否同步)不顾过程的研究。至于同步过程表现出来的属性很少研究。实际上同步过程是很重要的,因为同步本来就是一个渐进过程,对它的研究有利于揭示复杂系统的演化机理,有利于理解不同复杂系统的时空差异。
研究网络的同步过程离不开网络中尺度层次,网络中尺度有利于揭示同步过程,网络同步过程的中尺度研究可以展示实际系统丰富的时空复杂性。要分析清楚同步过程,需要引进能够刻画同步过程的中尺度物理量。本文介绍几篇文献在这方面的工作。文献 [22] 讨论的是 KM 振子模型,首先引入了全局序参数和局部序参数,前者刻画全局同步程度,后者刻画网络中同步边所占的比例。通过计算 ER 随机网络和 SF 无标度网络在耦合强度增加时这两个参数的变化,发现在开始耦合强度较小时,全局序参数虽然为 0 ,可是局部序参数已经增加,说明虽然全局不同步,但是局部同步已经开始;接下来耦合强度增加时 SF 网络的全局序参数迅速增加;当耦合强度继续增加时, ER 网络的全局序参数和局部序参数都急剧增加而超过了 SF 网络,说明 ER 网络的同步是在比较短的时间内发生,不像 SF 网络同步所需要的时间那么长。文献又引入两个很有意思的参数: GC( 最大同步块所包含的节点数目 ),NC( 局部同步块的数目 ) 。发现在开始耦合强度较小时, GC 值是 SF 网络大于 ER 网络,而 NC 值是 ER 网络大于 SF 网络,当耦合强度继续增加时, ER 网络的 GC 值急剧增加而超过了 SF 网络,而 ER 网络的 NC 值急剧下降而低于 SF 网络。说明 SF 网络由于存在 hubs 节点,它的同步是以 hubs 为中心凝聚方式趋于全局同步,而 ER 网络由于节点度较均匀,它的同步是以许多小社团分别同步开始,然后在比较短的时间内这些小社团相互趋于全局同步; SF 网络由于节点的不均匀性,大多数节点的度值较小,这些度很小的节点达到同步所需要的时间更长,所以造成 SF 网络完全同步所需时间大于 ER 网络。可见度分布的不同造成同步过程和方式的差异。文献计算了网络中不同度的节点属于最大同步块的概率,发现度大的节点即使在耦合强度较小时属于最大同步块的概率仍然很大,而度小的节点即使在耦合强度较大时属于最大同步块的概率仍然很小。
在同行工作的基础上,我们最近在中尺度意义下,也研究了不同拓扑结构的复杂网络的同步以及广义同步过程 [23,24] 。现在我们可以概括为以下几点:( 1 )不同结构的网络其同步方式和过程是完全不同的, SF 网络的同步是以 hubs 为中心凝聚方式趋于全局同步,边缘点(度小的节点)影响同步时间,而 ER 网络的同步是以许多小社团分别同步开始然后相互趋于全局同步。 SF 无标度网络完全同步所需时间比 ER 随机网络长。( 2 )同步是从度大的区域开始的,然后再蔓延到网络的其他节点,对于 SF 无标度网络尤其明显。由于实际网络大多是无标度网络,是否可以说现实的复杂系统的集群行为是从密集处开始。( 3 )社团网络的同步过程是从完全不同步到部分同步,再到聚类同步最后实现全局的完全同步;根据同步过程可以发现网络的拓扑结构,网络社团结构的发现依赖于尺度;分层社团结构的网络的同步过程与特征值谱的分布有关。
(陆君安)
 
复杂网络的加速增长现象
许多实际的网络具有加速增长特征。通过对万维网、因特网、科学家合作网、引文网络等的实证研究发现,在观测的生长期内,这些网络的平均度是随时间增加的,即边的数量比节点的数量增长更快,这种现象一般被称为加速增长 [25] 。过去十年间,已有不少文献对加速增长网络的拓扑性质进行了模拟、解析或数值的分析 [26-32] ,但对网络为何会加速增长这一问题还较少受到关注。本节将对这一问题进行粗浅的探讨。
网络规模的增长通常会表现在两个方面:一是节点数量的增加,二是边数量的增加。当有新的个体进入网络时,网络的节点数量会增加,同时至少会有一条边加入网络中。此处将节点数量理解为网络的演化时刻,则每个时刻网络边增加的数量可以表示为 m (t) ,如果网络的边是加速增长的,则 m (t) 应该是一个增函数 [25] 。需要注意的是,每个时刻增加的边并不一定都是连接新加入节点的,网络中的 “ 老 ” 节点之间也可能产生新的连接 [27] 。例如对于因特网,一个新设备通常是用一条线路而不是多条线路接入网络的。网络边数量较节点数量增加的快,更多的原因是网络中既有设备之间为增加吞吐量或提高速度而增加新的线路。这种现象在合作网络中存在的更为普遍,例如科学家论文合作网络,相当规模的论文是由已发表过论文的作者完成的,这种情况下网络甚至没有增加节点,而只是增加了边(或提高了边的权值)。对于以此种方式演化的网络,我们可以把其加速增长现象理解为:在网络 “ 年轻 ” 时,边更多地是以连接新节点的形式增加;而随着网络年龄的增长,越来越多的边会在老节点之间产生。
那么,为什么很多实际的网络中会有这种“初期以连接新节点为主、后期以连接老节点为主”的边加速增长特性呢?本节尝试用经济学中的边际效用递减理论 [33] 来对其进行初步解释。边际效用递减理论认为,在消费者连续消费某种消费品时,随着所消费的该消费品的数量增加,其总效用虽然相应增加,但消费品的边际效用(即每消费一个单位的消费品所带来的效用增加量)有递减的趋势。如果我们认为网络是自组织的,那么可以把网络自身理解为一个消费者,把网络演化过程中边的增加理解为一次消费行为,而把边连接新节点还是老节点理解为两种消费品。在网络增加边的一次 “ 消费行为 ” 中,是选择新节点连接还是选择老节点连接,取决于这二者中的哪个会带给网络自身更大的 “ 效用 ” 。而根据边际效用递减理论,连接新节点带给网络的效用会越来越小,网络会越来越不倾向于连接新节点,网络会呈现出边加速增长的趋势。例如对于公交网络,在网络发展早期,新辟线路的主要目的是覆盖公交服务盲区,那么连接新站点对提高网络整体效率的效用显然比连接旧站点更大;而随着网络发展,服务盲区越来越少,连接新站点的效用会递减,而减少既有站点间的换乘次数对提高网络整体效率的效用会加大,因此线路更倾向于在既有站点间连接。这样,公交网络的节点增速降低,而边的增速提高,网络会加速增长。对于科研合作网络也可以进行类似的解释:当新出现一个研究方向时,发表论文的 “ 门槛 ” 可能较低,也就是说新节点进入网络的 “ 成本 ” (可以理解为负的效用)较低;但随着这一方向研究的不断深入,新研究者发表论文的 “ 成本 ” 会越来越高,而 “ 老 ” 研究者由于有了更多的积累,发表论文的 “ 成本 ” 会越来越低。网络节点的增加会减速,网络呈现边加速生长趋势。
当然,以上解释只能说是一种类比,对于驱动网络加速增长的内在机制我们还并不十分了解,尚需结合各种实际网络的具体情况进行更深入的分析(最近琳媛、子柯和周涛提出了一种新的观点,即认为无标度网络要保持度指数的稳定,必须采取加速的增长模式 [34] )。但本节从经济学角度所给出的这些解释,为开发更符合实际的网络演化模型提供一种新的视角,有助于更深入地理解复杂网络的演化机制。
(闫小勇)
 
复杂网络中的链路预测
复杂网络研究近几年发展迅速,可谓枝繁叶茂。六七年前,如果你问一个人的研究领域,他说:“复杂网络”。你大概就知道他是干什么的了。如果现在有人问你,你做什么的,如果你只说“复杂网络”人家就会问“具体哪个方向”,然后你说“网络上的动力学”,人家又会继续问“同步,传播,交通,博弈还是什么呢”。可见,如今的复杂网络研究已经不仅仅局限于自身理论和方法的研究,而是成为多学科交叉的研究方向和多学科研究的有力工具。例如生物学中的新陈代谢网络,蛋白质相互作用网络,神经网络;社会学中的性关系网络,朋友关系网络,合作网络;交通系统中的航空网络、铁路及公路网;信息系统中的互联网,万维网等等。复杂网络研究已经与生物学、社会学、交通科学等产生了深刻的联系,而链路预测则是将复杂网络与信息科学联系起来的桥梁。
网络中的链路预测是指通过已知的网络结构信息预测网络中尚未产生连边的两个节点之间产生链接的可能性 [35] ,该研究在理论和应用两方面都具有重要意义。
首先,链路预测的研究可以从理论上帮助我们认识复杂网络演化的机制。由于刻画网络结构特征的统计量非常多,很难比较不同的机制孰优孰劣。链路预测机制有望为网络演化模型提供一个简单统一且较为公平的比较平台。类似地,如何刻画网络中节点的相似性也是一个重大的理论问题,相似性的度量指标数不胜数,只有能够快速准确地评估某种相似性定义是否能够很好刻画一个给定网络节点间的关系,才能进一步研究网络特征对相似性指标选择的影响。在这个方面,链路预测可以一展身手。链路预测本身也带来了有趣且有重要价值的理论问题,也就是如何通过构造网络系综并藉此利用最大似然估计的方法进行链路预测的可行性分析。这方面的研究有望建立链路预测的统计力学基础,迈出从统计力学的观点理解数据挖掘的第一步。
链路预测还具有重要的应用价值。以蛋白质相互作用网络和新陈代谢网络为例,节点之间是否存在相互作用关系,是需要通过大量实验结果进行推断的。我们已知的实验结果仅仅揭示了巨大网络的冰山一角。由于揭示这类网络中隐而未现的链接需要耗费高额的实验成本。如果能够事先在已知网络结构的基础上设计出足够精确的链路预测算法,再利用预测的结果指导试验,就有可能提高实验的成功率从而降低试验成本并加快揭开这类网络真实面目的步伐!另外,在社会网络分析中也会遇到数据不全的问题,这时候链路预测同样可以作为准确分析社会网络结构的有力工具。链路预测算法还可以用于分析演化网络,即对未来可能连边的预测,如在线社交网络的朋友预测(推荐)问题。另外,链路预测的思想和方法,还可以用于在已知部分节点类型的网络中预测未标签节点的类型——这可以用于判断一篇学术论文的类型或者判断一个手机用户是否产生了切换运营商 ( 例如从移动到联通 ) 的念头 [36] 。此外,关于错误链接的预测对于网络重组和结构功能优化也有重要的应用价值。例如在很多构建生物网络的实验中存在暧昧不清甚至自相矛盾的数据,我们就有可能应用链路预测的方法对其进行纠正 [37] 。
链路预测作为数据挖掘领域的研究方向之一在计算机领域已有一些早期的研究。他们的研究思路和方法主要基于马尔科夫链和机器学习。这些方法往往要涉及节点的属性信息。虽然应用节点属性等外部信息的确可以得到很好的预测效果,但是很多情况下这些信息的获得是