当前位置:文档之家› 自然基金成功范本--复杂网络链路预测的理论、算法和应用研究

自然基金成功范本--复杂网络链路预测的理论、算法和应用研究

申请代码A050105

受理部门

收件日期

受理编号

国家自然科学基金

申 请 书

(2010版)

资助类别:面上项目

亚类说明:

附注说明:

项目名称:复杂网络链路预测的理论、算法和应用研究

申 请 人:周涛 电话: 028-********

依托单位:电子科技大学

通讯地址:成都市建设北路2段4号计算机学院

邮政编码:610054 单位电话:028-******** 电子邮箱:zhutouster@https://www.doczj.com/doc/8818223631.html,

申报日期: 2010年03月06日

国家自然科学基金委员会

经费申请表 (金额单位:万元) 科目

申请经费 备注(计算依据与说明) 一.研究经费

26.0000 1.科研业务费

16.0000 (1)测试/计算/分析费

4.0000开发测试平台,购买计算时间,购买商业数据 (2)能源/动力费

(3)会议费/差旅费

5.0000协办会议1万,国内参会或访问20人次4万 (4)出版物/文献/信息传播费

7.0000国内论文出版费2万,PNAS/PLoS/NJP 论文费5万(5)其他

2.实验材料费

3.0000 (1)原材料/试剂/药品购置费

3.0000项目开展中的各种耗材 (2)其他

3.仪器设备费

7.0000 (1)购置

7.0000购买电脑10台,和其它研究用设备 (2)试制

4.实验室改装费

5.协作费

二.国际合作与交流费

5.2000 1.项目组成员出国合作交流

3.2000项目组成员出国交流访问及参加学术会议4人次 2.境外专家来华合作交流

2.0000境外专家来华访问2人次 三.劳务费

5.8500学生助研费 四.管理费

1.9500项目管理费 合 计 39.0000

国家其他计划资助经费

其他经费资助(含部门匹配)

与本项目相关的 其他经费来源 其他经费来源合计

0.0000

报告正文

(一)立项依据与研究内容

1.项目的立项依据

1.1 问题的提出

链路预测(Link Prediction)问题是指通过对已知网络结构的分析,包括一些可能的节点的其他信息,来评估尚不相连的两个点之间产生链接的可能性,进而实现预测[1]。该问题具有重要的应用价值,并且可以对网络科学的理论研究,特别是网络演化规则和节点相似性指标的评判问题,起到重要的贡献。下面我们从实际应用和理论意义两个方面叙述。

很多生物网络,例如蛋白质相互作用网络和新陈代谢网络,节点之间是否存在链路,或者说是否存在相互作用,是需要通过大量实验结果进行推断。我们已知的实验结果仅仅揭示了巨大网络的冰山一角。仅以蛋白质相互作用网络为例,酵母菌蛋白质之间80%的相互作用不为我们所知[2],而对于人类自身,我们知道的仅有可怜的0.3%[3,4]。由于揭示这类网络中隐而未现的链接需要耗费高额的实验成本,如果能够在已知结构的基础上设计出足够精确的链路预测算法,再利用预测的结果指导试验,就有可能非常明显地降低试验成本并加快揭开这类网络真实面目的步伐!实际上,社会网络分析中也会遇到数据不全的问题,这时候链路预测同样可以作为准确分析社会网络结构的有力的辅助工具[5,6]。除了帮助分析数据缺失的网络,链路预测算法还可以用于分析演化网络。举例来说,近几年在线社会网络发展非常迅速[7],链路预测可以基于当前的网络结构去预测哪些现在尚未结交的用户“应该是朋友”,并将此结果作为“朋友推荐”发送给用户:如果预测足够准确,显然有助于提高相关网站在用户心目中的地位。另外,链路预测的思想和方法,还可以用于在已知部分节点类型的网络(partially labeled networks)中预测未标签节点的类型——这可以用于判断一篇学术论文的类型[8]或者判断一个手机用户是否产生了切换运营商(例如从移动到联通)的念头[9];以及用于纠正观察到的网络结构中可能存在的错误[10],因为很多构建生物网络的实验中存在暧昧不清甚至自相矛盾的数据[11]。

链路预测的研究可以从理论上帮助认识复杂网络演化的机制。针对同一个或者同一类网络,很多模型都提供了可能的网络演化机制[12,13]。由于刻画网络结构特征的统计量非常多,很难比较不同的机制孰优孰劣。链路预测机制有望为演化网络提供一个简单统一且较为公平的比较平台,从而大大推动复杂网络演化模型的理论研究。另外,如何刻画网络中节点的相似性也是一个重大的理论问题[14],这个问题和网络聚类等应用息息相关[15]。类似地,相似性的度量指标数不胜数,只有能够快速准确地评估某种相似性定义是否能够很好刻画一个给定网络节点间的关系,才能进一步研究网络特征对相似性指标选择的影响。在这个方面,链路预测可以起到核心技术的作用。链路预测问题本身也带来了有趣且有重要价值的理论问题,也就是通过构造网络系综并藉此利用最大似然估计的方法进行链路预测的可能性和可行性研究。这方面的研究对于链路预测本身以及复杂网络研究的理论基础的建立和完善,可以起到推动和借鉴的作用。

1.2研究进展

链路预测作为数据挖掘的方向之一在计算机领域已有一些早期的研究。他们的研究思路和方法主要基于马尔科夫链和机器学习。Sarukkai[16]应用马尔科夫链进行网络的链路预测和路径分析。之

后Zhu等人[17]将基于马尔科夫链的预测方法扩展到了自适应性网站(adaptive web sites)的预测中。此外,Popescul和Ungar[18]提出一个回归模型在文献引用网络中预测科学文献的引用关系。他们的方法不仅用到了引文网络的信息还有作者信息,期刊信息以及文章内容等外部信息。应用节点属性的预测方法还有很多,例如O’Madadhain等人[19]利用网络的拓扑结构信息以及节点的属性建立了一个局部的条件概率模型来进行预测。Lin[20]基于节点的属性定义了节点间的相似性,可以直接用来进行链路预测。虽然应用节点属性等外部信息的确可以得到较好的预测效果,但是很多情况下这些信息的获得是非常困难的,甚至是不可能的。比如很多在线系统的用户信息都是保密的。另外即使获得了节点的属性信息也很难保证信息的可靠性,即这些属性是否反映了节点的真实情况,例如在线社交网络中很多用户的注册信息都是虚假的。更进一步,在能够得到节点属性的精确信息的情况下,如何鉴别出哪些信息对网络的链路预测是有用的,哪些信息是没用的仍然是个问题。因此与节点属性信息相比较,已观察到的网络结构或者用户的历史信息更容易获得也是更可靠的。

近几年,基于节点相似性的链路预测框架受到了广泛的关注,在该框架中,两个节点之间相似性(或者相近性)越大,就认为它们之间存在链接的可能性越大。尽管这个框架非常简单,但是相似性定义本身内涵丰富,它既可以是非常简单的共同邻居的个数,也可以是包含了复杂数学物理内容的诸如随机游走的平均通讯时间[21]或者矩阵森林数目[22]。因此这个简单的框架事实上提供了无穷无尽的可能性。Liben-Nowell和Kleinberg[23]将相似性指标分为基于节点和基于路径的两类,并分析了若干指标对社会合作网络中链路预测的效果,他们发现,在仅考虑节点邻居信息的若干指标中,Adamic-Adar参数[24]表现最好。周涛、吕琳媛和张翼成[25]在6种不同网络中比较了9种局部相似性指标在链路预测中的效果,并提出了两种新指标:资源分配指标(resource allocation index)和局部路径指标(local path index)。研究发现,新提出来的这两种指标具有明显好于包括Adamic-Adar 参数在内的9种已知指标的预测能力。最近其他小组的研究结果显示,新提出来的相似性指标在进行群落划分[15]和含权网络权重设置[26]的时候也比原有指标好。吕琳媛、金慈航和周涛[27]进一步在噪音强度可控的网络模型与真实网络中细致分析了局部路径指标的性能,发现这个指标具有与依赖于网络全局结构信息的指标,例如Katz参数[28],可匹敌的预测能力,甚至在噪声较大的情况下可以比Katz参数预测得更加准确。考虑到局部路径指标是一个计算量非常小的局部参数,其应用前景可观。刘伟平和吕琳媛[29]比较研究了一些基于随机游走的相似性指标,并提出了两种局部随机游走指标,他们发现有限步的随机游走反而可以给出超过全局收敛后的预测精度,而最优的游走步数受到网络平均距离的强烈影响。另外,Huang等人的实验结果暗示[30],在得到节点间的直接相似性后,利用协同过滤技术对相似性指标进行一轮加权处理,一般而言可以得到更好的结果。

最近,最大似然估计方法被尝试应用于链路预测中。Clauset, Moore和Newman[31]认为很多网络的连接可以看作某种内在的层次结构的反映,基于此,他们提出了一种最大似然估计的算法进行链路预测,这种方法在处理具有明显层次组织的网络,如恐怖袭击网络和草原食物链,具有较好的精确度。Guimera和Sales-Pardo[10]假设我们观察到的网络是一个随机分块模型(Stochastic Block Model)[32]的一次实现,在该模型中节点被分作若干的集合,两个节点间连接的概率只和相应的集合有关。Guimera和Sales-Pardo[10]提出了基于随机分块模型的最大似然估计方法,将其用于链路预测,可以得到比Clauset, Moore和Newman更好的结果。

另外一个需要特别注意的趋势,是随着一些原来从事复杂网络研究的学者对链路预测问题的关注,很多复杂网络,特别是社会网络分析中遇到的理论与方法被应用到链路预测中。例如吕琳媛和周涛[33]发现在针对某些含权网络进行链路预测的时候,权重很小的边反而起到了比高权重边更大的作用,这与社会网络研究中广为人知的“弱连接理论”[34]有深刻的关联。Leskovec, Huttenlocher 和Kleinberg[35]则注意到了近期“社会平衡理论”的定量化研究成果[36,37],并在此启发下设计了可以预测网络中的正负(友敌)链接的算法。

链路预测最近两年受到了比较多的关注,很可能得益于Clauset, Moore和Newman在08年发

表的《自然》论文[31],以及Redner在《自然》上的评论文章[38]。国内对这个方向还没有广泛的关注。本项目申请人及其在瑞士弗里堡大学的合作申请团队较早认识到链路预测重要性并开展了一些相关研究。本项目联合申请人张千明[39]尝试将链路预测方法用于标签网络节点的分类中。标签网络节点分类是指在给定一个网络并已知部分节点的类别时预测那些未知标签的节点的类别。目前标签分类的两大困难是已知分类的节点的稀疏性和网络标签的不一致性(相连接的两个节点不属于同一类)。为此张千明等人提出了应用节点的相似性进行分类的方法。通过在政治书籍共同购买网络(co-purchase network of political books)中的试验结果得到,基于相似性的标签分类方法可在一定程度上克服上述两类困难,从而得到较高的预测精度。湘潭大学胡柯小组[40]利用链路预测方法预测人类蛋白质相互作用网络中的致病基因,也得到了不错的精度。胡柯及青岛理工大学许小可与申请人交流过他们在有向网络链路预测和社会平衡理论应用于链路预测的基本思路和初步结果,但尚未形成已经发表的论文。

1.3 前沿趋势和热点分析

我们注意到一方面受阻于网络节点外在属性在获取上的难度,另一方面受益于复杂网络研究的快速发展,链路预测问题的主要研究热点逐渐从依赖于节点属性的方法转移到只利用网络结构信息的方法上[23]。显然,后者在理论上也更优美简洁。不过,这个方面的研究主要集中在社会网络上,尚欠对于大量算法在各种不同网络中的预测能力的系统分析和总结,另外,目前还没有算法性能和网络结构特征之间关系的较深入的研究。对于比较复杂的网络,例如含权网络、有向网络和多部分网络的讨论虽然有[33,35,41],但非常少,也不系统。相关的研究应该是近几年该方向的主流。

网络系综理论和与之关联的网络熵的概念以及最大似然估计方法有望推动形成复杂网络的统计力学理论基础[42-44]。这方面研究存在的一个问题是熵的精确计算复杂性非常大[45],对于大规模网络而言往往不能实现。最近的一些链路预测算法[10,31]已经应用了网络系综和最大似然的概念,但是这些算法计算复杂性很大,精确性也不是很高[29],例如文献[31]的方法目前只能处理数千节点的网络,且其预测效果对于不具有明确层次结构的网络并不好[29]。我们认为以下两个问题应该是目前国际上相关研究小组比较关注的:一是如何以网络系综理论为基础,建立网络链路预测的理论框架,并产生对实际预测有指导作用的理论结论,例如通过对网络结构的统计分析估算可预测的极限,指导选择不同的预测方法等等;二是如何设计高效的算法来处理大规模网络的链路预测问题。考虑到Bianconi在2009年加入了西北大学(Guimera与Sales-Pardo目前都在西北大学做助理教授),网络系综理论和链路预测的深度结合很可能成为西北大学研究组最近关注的焦点。

最近十年,复杂网络研究在很多科学分支,包括物理、生物、计算机等等掀起高潮[46],其中相当一部分研究立足于揭示网络演化的内在驱动因素。仅以无标度网络(scale-free networks)为例[47],已经报道的可以产生幂律度分布的机制就包括了富者愈富(rich-get-richer)机制[48],好者变富(good-get-richer)机制[49],优化设计(optimal design)驱动[50],哈密顿动力学(Hamiltonian dynamics)驱动[51],聚生(merging and regeneration)机制[52],稳定性限制(stability constraints)驱动[53],等等。可是,由于刻画网络结构特征的统计指标非常多,很难比较和判定什么样的机制能够更好再现真实网络的生长特性。利用链路预测有望建立简单的比较平台,能够在知道目标网络演化情况的基础上量化比较各种不同机制对于真实生长行为的预测能力,从而可以大大推动复杂网络演化机制的相关研究。Guimera和Sales-Pardo在提到网络重建(network reconstruction)的时候已经表达了相近的思想,但是这方面的研究尚未见报道。

尽管有论文讨论了如何将链路预测的方法和思想与一些应用问题,例如部分标号网络的节点类型预测[8,39,54]与信息推荐问题[25,35,55],相联系的可能性与方法,但是,目前尚缺乏对于大规模真实数据在应用层面的深入分析和研究。这方面的研究不仅仅具有实用价值,而且有助于揭示链路预测这个问题本身存在的优势与局限性。

总结起来,国际上很多研究组已经开始将复杂网络的概念和方法与链路预测问题结合起来,并取得了令人瞩目的成果。目前从我们了解的情况来看,在本项目所涉及的研究方向上,国际上较为领先的研究小组包括康奈尔大学Kleinberg教授领导的研究团队,圣塔菲研究所和密歇根大学由Moore教授、Newman教授和博士后Clauset组成的研究团队,西北大学Amaral实验室Guimera 教授的研究团队,卡内基梅隆大学计算机系Faloutsos教授的研究团队,以及本项目的申请团队。我们和其他四个团队间也有相互的交流和讨论,在很多问题上存在共同兴趣和竞争关系。

1.4 本项目的宗旨

本项目组成员已经在链路预测问题,包括相关的复杂网络、信息推荐等问题有相当丰富的研究经验和具有广泛国际影响力的系列研究成果。复杂网络链路预测本身是一个非常集中和具体的研究题目。本项目团队在选题和研究目标上的宗旨是“题目不大,贡献不小”。我们希望通过基金委的支持,全方位推动复杂网络链路预测在理论、算法和应用方面的研究,把链路预测研究小组从一个国际上较为领先的团队建设成为国际相关研究方向上最好的团队之一。本项目力争在链路预测相关的若干理论与应用方向作出有长期影响力的重要贡献,这些贡献可能包括但不限于以下五个方面:(i)利用网络系综和最大似然估计的思想和技术,建立基于相似性框架的链路预测的理论基础;(ii)丰富和提高现有相似性预测的算法,特别是针对有向网络、含权网络、多部分网络、含不同类连边的网络等较复杂的情形,提出新的相似性指标;(iii)对已知算法的性能进行深入细致的分析,揭示算法性能和网络结构特征之间的关系;(iv)基于链路预测的思想,建立可以针对给定演化轨迹的目标网络评价不同演化机制的平台;(v)实现有代表性的链路预测的应用研究。

参考文献

[1] L. Getoor, C. P. Diehl, Link Mining: A Survey, ACM SIGKDD Explorations Newsletter 7 (2005) 3.

[2] H. Yu, et al., High-quality binary protein interaction map of the yeast interactome network, Science 322 (2008) 104.

[3] M. P. H. Stumpf, T. Thorne, E. de Silva, R. Stewart, H. J. An, M. Lappe, C. Wiuf, Estimating the size of the human

interactome, Proc. Natl. Sci. Acad. U.S.A. 105 (2008) 6959.

[4] L. A. N. Amaral, A truer measure of our ignorance, Proc. Natl. Sci. Acad. U.S.A. 105 (2008) 6795.

[5] L. Schafer, J. W. Graham, Missing data: Our view of the state of the art, Psychol. Methods 7 (2002) 147.

[6] G. Kossinets, Effects of missing data in social networks, Social Networks 28 (2006) 247.

[7] R. Kumar, J. Novak, A. Tomkins, Structure and evolution of online social networks, Proc. ACM SIGKDD 2006, ACM Press,

New York, 2006, p. 611.

[8] B. Gallagher, H. Tong, T. Eliassi-Rad, C. Falousos, Using ghost edges for classification in sparselylabelednetworks, Proc.

ACM SIGKDD 2008, ACM Press, New York, 2008, p. 256.

[9] K. Dasgupta, R. Singh, B. Viswanathan, D. Chakraborty, S. Mukherjea, A. A. Nanavati, A. Joshi, Social Ties and their

Relevance to Churn in Mobile Telecom Networks, Proc. EDBT’08, ACM Press, New York, 2008, p. 668.

[10] R. Guimera, M. Sales-Pardo, Missing and spurious interactions and the reconstruction of complex networks, Proc. Natl.

Sci. Acad. U.S.A. 106 (2009) 22073.

[11] C. von Mering, R. Krause, B. Snel, M. Cornell, S. G. Oliver, S. Field, P. Bork, Comparative assessment of large-scale data

sets of protein-protein interactions, Nature 417 (2002) 399.

[12] R. Albert, A.-L. Barabasi, Statisrical Mechanics of Complex Networks, Rev. Mod. Phys. 74 (2002) 47.

[13] S. N. Dorogovtsev, J. F. F.Mendes, Evolution of networks, Adv. Phys. 51 (2002) 1079.

[14] E. A. Leicht, P. Holme, M. E. J. Newman, Vertex similarity in networks, Phys. Rev. E 73 (2006) 026120.

[15] Y. Pan, D.-H. Li, J.-G. Liu, J.-Z. Liang, Detecting community structure in complex networks via node similarity, Physica A

(to be published).

[16] R. R. Sarukkai, Link prediction and path analysis using markov chains, Computer Networks 33 (2000) 377.

[17] J. Zhu, J. Hong, J. G. Hughes, Using markov chains for link prediction in adaptive web sites, Lect. Notes Comput. Sci.

2311 (2002) 22.

[18] A. Popescul, L. Ungar, Statistical relational learning for link prediction, Proc. Workshop on Learning Statistical Models

from Relational Data, ACM Press, New York, 2003, p. 81.

[19] J. O’Madadhain, J. Hutchins, P. Smyth, Prediction and ranking algorithms for even-based network data, Proc. ACM

SIGKDD 2005, ACM Press, New York, 2005.

[20] D. Lin, An information-theoretic definition of similarity, Proc. 15th Intl. Conf. Machine Learning, Morgan Kaufman

Publishers, San Francisco, 1998.

[21] F. Fouss, A. Pirotte, J.-M. Renders, M. Saerens, Random-walk computation of similarities between nodes of a graph with

application to collaborative recommendation, IEEE Trans. Knowl. Data. Eng. 19 (2007) 355.

[22] P. Chebotarev, E. Shamis, The matrix-forest theorem and measuring relations in small social groups, Automat. Remote

Contr. 58 (1997) 1505.

[23] D. Liben-Nowell, J. Kleinberg, The Link-Prediction Problem for Social Networks, J. Am. Soc. Inform. Sci. Technol. 58

(2007) 1019.

[24] L. A. Adamic, E. Adar, Friends and neighbors on the web, Social Networks 25 (2003) 211.

[25] T. Zhou, L. Lü, Y.-C. Zhang, Predicting missing links via local information, Eur. Phys. J. B 71 (2009) 623.

[26] Y.-L. Wang, T. Zhou, J.-J. Shi, J. Wang, D.-R. He, Emipirical analysis of dependence between stations in Chinese railway

network, Physica A 388 (2009) 2949.

[27] L. Lü, C.-H. Jin, T. Zhou, Similarity index based on local paths for link prediction of complex networks, Phys. Rev.E 80

(2009) 046122.

[28] L. Katz, A new status index derived from sociometric analysis, Psychometrika 18 (1953) 39.

[29] W.-P. Liu, L. Lü, Link Prediction Based on Local Random Walk, Europhys. Lett. (to be published).

[30] Z. Huang, X. Li, H. Chen, Link prediction approach to collaborative filtering, Proc. 5th ACM/IEEE-CS Joint Conf. Digital

Libraries, ACM Press, New York, 2005.

[31] A. Clauset, C. Moore, M. E. J. Newman, Hierarchical structure and the prediction of missing links in networks, Nature

453 (2008) 98.

[32] P. W. Holland, K. B. Laskey, S. Leinhard, Stochastic blockmodels: First steps, Social Networks 5 (1983) 109.

[33] L. Lü, T. Zhou, Link Prediction in Weighted Networks: The Role of Weak Ties, Europhys. Lett. 89 (2010) 18001.

[34] M. S. Granovetter, The strength of weak ties, Am. J. Sociology 78 (1973) 1360.

[35] J. Leskovec, D. Huttenlocher, J. Kleinberg, Predicting Positive and Negative Links in Online Social Networks, Proc.

WWW 2010, ACM, New York, 2010.

[36] T. Antal, P. Krapivsky, S. Redner, Dynamics of social balance on networks, Phys. Rev. E 72 (2005) 036121. [37] S.

Marvel, S. Strogatz, J. Kleinberg, Energy landscape of social balance, Phys. Rev. Lett. 103 (2009) 198701.

[38] S. Redner, Teasing out the missing links, Nature 453 (2008) 47.

[39] Q.-M. Zhang, M.-S. Shang, L. Lü, Similarity-based classification in partial labeled networks, arXiv: 1003.0837.

[40] L. Zhang, K. Hu, Y. Tang, Predicting disease-related genes by topological similarity in human protein-protein interaction

network, Cent. Eur. J. Phys. (to be published).

[41] T. Murata, S. Moriyasu, Link prediction of social networks based on weighted proximity measures, Proc. IEEE/WIC/ACM

Intl. Conf. Web Intelligence, ACM Press, New York, 2007.

[42] G. Bianconi, Entropy of network ensembles, Phys. Rev. E 79 (2009) 036114.

[43] K. Anand, G. Bianconi, Entropy measures for networks: Toward an information theory of complex topologies, Phys. Rev.

E 80 (2009) 045102.

[44] G. Bianconi, P. Pin, M. Marsili, Assessing the relevance of node features for network structure, Proc. Natl. Acad. Sci.

U.S.A. 106 (2009) 11433.

[45] J. Li, B.-H. Wang, W.-X. Wang, T. Zhou, Network Entropy Based on Topology Configuration and Its Computation to

Random Networks, Chin. Phys. Lett. 25 (2008) 4177.

[46] A.-L. Barabasi, Scale-Free Networks: A Decade and Beyond, Science 325 (2009) 412.

[47] G. Caldarelli, Scale-Free Networks: Complex webs in nature and technology, Oxford Press, New York, 2007.

[48] A.-L. Barabasi, R. Albert, Emergence of scaling in random networks,Science 286 (1999) 509.

[49] D. Garlaschelli, A. Capocci, G. Caldarelli, Self-organized network evolution coupled to extremal dynamics, Nat. Phys. 3

(2007) 813.

[50] S. Valverde, R. F. Cancho, R. V. Sole, Scale-free networks from optimal design, Europhys. Lett. 60 (2002) 512.

[51] M. Baiesi, S. S. Manna, Scale-free networks from a Hamiltonian dynamics,Phys. Rev. E 68 (2003) 047103.

[52] B. J. Kim, A. Trusina, P. Minnhagen, K. Sneppen, Self organized scale-free networks from merging and regeneration, Eur.

Phys. J. B 43 (2005) 369.

[53] J. I. Perotti, O. V. Billoni, F. A. Tamarit, D. R. Chialvo, S. A. Cannas, Emergent self-organized complex network topology

out of stability constraints, Phys. Rev. Lett. 103 (2009) 108701.

[54] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, T. Eliassi-Rad, Collective classification in network data, AI

Magazine 29 (2008) 93.

[55] T. Zhou, Statistical Mechanics of Information Systems: Information Filtering on Complex Networks, Ph. D. Thesis,

University of Fribourg, 2010.

2 项目的研究内容、研究目标、拟解决的关键科学问题

2.1 研究内容

链路预测是一个方兴未艾的研究方向,其部分算法已经比较成熟,部分成果已经呈现出可以大范围应用的可能性,然而理论基础尚很薄弱。同时,这个研究方向,与复杂网络以及信息挖掘的研究有着内在的紧密联系。本项目试图在理论、算法和应用三个层面全面推进该方向的研究,每个层面又包含两方面的内容,一共6点,按照理论-算法-应用的顺序展开。需要说明的是,复杂网路链路预测是一个非常具体的研究方向,内容相对比较集中。因此,本项目致力于全面推进该方向上的研究,不同于一般申请书仅仅针对相关方向上两到三个重点问题。

(1)基于相似性框架的链路预测的理论基础研究。尽管基于相似性框架的链路预测算法已经有很多报道,但是目前还没有相关理论基础方面的讨论。本项目拟利用最大似然分析的思想与技术,建立相似性预测框架的理论基础,并在这个理论原型下讨论如何快速高效地寻找含参相似性指标的最优参数,以及估算不同类型的相似性指标在不同网络中预测能力的极限。

(2)利用链路预测思想建立复杂网络演化模型的评估系统。本项目拟借助链路预测的精确度评估体系,建立评价不同演化模型的平台。本项目还将以最近广受关注的一些演化网络,包括WWW,Internet和在线社会网络的真实数据为基础,系统分析针对各类网络所发表的数十种演化模型,并在统一的平台上进行评估和分析。虽然这部分研究内容不属于链路预测自身的理论问题,但却有可能极大地推动网络演化理论的研究。

(3)复杂情况下基于相似性框架的算法研究。以前基于相似性的网络链路预测往往只考虑简单无向图。本项目拟探讨在更复杂情况下进行精确预测的可能性和方法,包括有向网络、含权网络、多部分网络等等。特别地,在某些网络中,连边意义不同,例如可能同时存在与政见相同的人的连边和与“敌方”的连边,这种情况下如何进行预测,是本项目关注的。还有一些情况下,特别是生物网络中,部分节点之间已经确切知道不存在连边。这些信息可以看作已知结构信息的一种补充,我们把它叫做负面信息(Negative information),如何利用负面信息,也是本项目关注的问题。

(4)算法性能及预测结果分析。目前已有报道的可以用于链路预测的节点相似性指标超过了二十个,这些指标在不同类型的网络中表现不同。本项目拟选择若干具有代表性的算法评估指标,在此基础上系统研究各种相似性指标在各类真实网络中的表现,确定影响预测精度的网络结构特征以及相应的影响大小,力争总结出如何根据网络结构信息和预测的实际需求选择合适的相似性指标的指南。本项目重点关注的结构特征包括:度分布的异质性、网络的稀疏性、网络连接的聚集特性、网络连接中的噪音强度、社团结构、度度相关性等等。另外,本项目将深入分析预测的结果,力图揭

示“哪类指标倾向于预测哪些链接”这样的关系,并将这些结果和信息挖掘中信息多样性和新颖性的评价体系结合起来。

(5)大规模在线社会网络朋友推荐的应用研究。本项目拟以真实大规模在线社会网络数据为基础,研究已知的链路预测算法之表现,并尝试开发可供学术界共享共用的公共研究平台,以测试各种算法在真实数据中的表现。

(6)手机用户离网预测与分析。本项目拟将链路预测解决部分标签网络中节点类型判定的方法,应用于判定手机用户对网络运营商的忠诚度,从而对手机用户离网行为进行预测。

2.2 研究目标

下面将对应于研究内容分述具体的目标。

(1)基于相似性框架的链路预测的理论基础研究。利用网络系综的思想和最大似然估计方法,建立基于相似性的链路预测方法的理论基础。在这个理论基础上,给出如何高效率地提前评估各种相似性指标可能的预测性能,并为含参数的指标设计出快速寻找最优参数的方案。

(2)利用链路预测思想建立复杂网络演化模型的评估系统。建立简洁统一的评估系统,可以在给定网络连边出现的时间顺序后,自动评估不同的演化模型规则,并按照预测精度为不同演化模型排序。力争最终形成一个可以为学术界共用的包括可下载演化网络共享数据、可支持评估有代表性的演化规则,还可开放设计新规则并自动进行评估的研究平台。

(3)复杂情况下基于相似性框架的算法研究。提出或改进针对有向网络、含权网络和多部分网络的相似性指标。提出针对含有异质连边的网络的链路预测算法。提出可以充分利用负面信息的链路预测算法,该算法应该能够明显提高忽略负面信息的原始算法。

(4)算法性能及预测结果分析。总结有代表性的链路预测算法在具有不同统计特性的网络上的表现,得到如何根据待预测网络自身特性和系统实用要求选择合适算法的定性指南。总结不同预测算法所得到的预测结果所具有的倾向性,例如有些算法可能更倾向于预测两个端点度都很大的连边,有的则相反。

(5)大规模在线社会网络朋友推荐的应用研究。在一个或多个大规模真实在线社区网络中实现有代表性的链路预测算法,或设计有针对性的新算法,总结这些算法在处理大规模真实网络中的表现。开发开放性平台,可以供学术界感兴趣的学者通过该平台测试自己的链路预测算法。

(6)手机用户离网预测与分析。以部分中国手机用户在移动、联通和电信的不含内容的通话记录为基础,利用链路预测和社会网络分析的思想和方法,提出可以提前评估预测目标手机用户离开当前运营商网络并加入其他运营商网络之概率的算法,并建立相应的应用平台。

2.3 拟解决的关键科学问题

随着研究的开展和深入,各种问题都会遇到。下面我们列出在项目初期规划时就已经意识到的一些关键的研究问题。对于部分问题,我们已经有了初步的解决方案,当然也存在一些没有把握的问题,我们会在下面的叙述中说明。

(1)如何建立相似性框架下链路预测问题的理论基础。给定一个相似性指标,利用当前的结构可以计算得到任意一对节点的相似性,在假设这个相似性可以反映某种内在的连接倾向的前提下,可以计算特定网络在节点数和边数不变的情况下,恰好出现观察到的结构的似然(likelihood)。但是这种

理论框架下似然最大的相似性指标是否就对应于预测最精确的指标,还需要大量实验支持,能否利用这种框架解决含参数相似性指标的参数优化问题,也是有待深入研究的。

(2)大规模及超大规模网络的相关快速算法设计。因为绝大多数链路预测已经报道的算法,都是在规模为几千几万的网络中测试,对于真实社会网络动辄千万上亿的规模,相差甚远。为了能够真正推动链路预测的应用研究,也进一步检验算法是否能在真实的演化网络中表现良好,必须考虑如何快速处理百万节点以上的网络。这种大规模及超大规模网络快速算法分为几个方面:首先是如何设计能够保证相当精确度的局部链路预测算法;其次是针对手机用户离网问题,是否能够设计有针对性的分析社会网络中个人影响力范围和强度的快速算法(IBM印度研究院最近有论文讨论类似的问题[K. Dasgupta, et al., EDBT’08, ACM Press],但是该论文所提出的算法是全局收敛的方法,在处理超大规模网络时复杂性太大);最后是在探讨网络结构与算法性能之间关系的时候如何快速挖掘网络的结构特征。

(3)如何充分利用负面信息。同时利用正面(已知连边)和负面(已知不连边)信息进行链路预测是一个全新的问题。因为负面信息的信息总量往往很大(在生物网络中,很多节点对都明确知道不会有相互连接),但是信息价值很低。我们前期的一些研究显示如果赋予不恰当的权重,负面信息的引入会淹没正面信息的价值,反而降低预测精度。如何恰如其分的使用负面信息,不是一个简单的问题。

(4)如何处理异质连边。这是一个与问题(3)相似但不相同的问题。在社会网络中,连边可能代表“朋友”关系或者“敌人”关系;而在二部分的用户-对象网络中,连边可能代表用户对某对象的“赞扬”(打高分)或者“苛责”(打低分)。但是,代表“敌人”或者“苛责”的连边不能简单视作只有负面的效应,因为“苛责”的对象至少是用户关心的对象。我们发现有的时候“苛责”的连边对链路存在性的预测能起到正面的作用[M.-S. Shang, et al., EPL 88 (2009) 68008],但是其权重应该如何分配,特别是如果不仅仅预测存在性,同时还要预测链路类型,应当如何设计算法,我们尚不清楚。

3 拟采取的研究方案和可行性分析

3.1 研究方案

尽管本项目各研究内容之间相互关联紧密,例如理论基础可以指导实际算法,而揭示网络结构特征和算法性能之间的关系对于设计针对真实网络的应用研究很有帮助,但是本项目的各项研究内容原则上可以平行开展,并不存在严格的“谁必须先,谁必须后”的关系。基于此,我下面从5个方面介绍开展本项目研究将要涉及的一些概念、理论、方法和研究思路。某些为学术界熟悉的概念,例如网络度分布、簇系数、度度相关性、社团结构等,和较成熟的技术,例如如何分析刻画一个网络的典型结构特性,在本申请书中不再赘述。

(1)利用最大似然估计建立基于相似性的链路预测算法理论基础的研究思路。

给定一种相似性度量方法,表示为相似性函数S(x,y),其中x和y是任意两个节点(关于已知的二十多种相似性指标,请参考研究方案的第四部分)。一个假设是两个节点之间是否存在一条连边的概率p(x,y)是与S成单调正相关的函数,可以表示为p(x,y)=p(S)。这是能够利用相似性进行链路预测的基本假设,当然,该假设对于真实情况只是一种非常粗糙的描述,因为对于任何已知的相似性指标,都会出现很多相似性大的节点对之间反而没有连边的情况。

A=如果节点x和y相连,否则为0。考虑简单无向网络的情用邻接矩阵A表示网络,其中1

xy

况(复杂情况可以类推),注意到相似性函数给定且只依赖于网络结构时,相似性矩阵S实际上是由A决定的,于是网络A的似然(likelihood)可以写作:

(,)(,)x y

Q p S x y ψ≠=∏

其中

((,)), 1(,)1((,)), 0

xy xy p S x y A x y p S x y A ψ=??=??=?? 给定相似性函数S,我们称使得Q (p ,S )最大的p 所对应的Q 为给定S 下的网络A 的最大似然,记为:

*()max (,)p

Q S Q p S =. 对于一个给定的相似性指标S ,我们猜测,*()Q S 给出了S 可预测性的极限。当然,*()Q S 是否能够刻画真实情况,以及是否容易找到最优或者接近最优的函数p ,本身还需要进行探索研究。

注意到,即使没有找到最优或者近似最优的函数p ,由于给定的相似性函数S 唯一确定了预测的精确度,假设S 是一个含参函数,记为(,,)S S x y λ=,我们仍然可以利用这种方法寻找λ的最优值。我们的基本思路是给出函数p ,并猜想λ的最优值恰好使得似然函数(,)Q p S 最大,记为*()p λ。不同的函数p 对应于不同的λ的最优值,那个对应于网络最大似然的就可能是使得预测精度也最优的λ。这个方法避免了数据集划分方式的不同和精确性度量的不同可能导致的在寻求最优参数时效率较低和评价指标互相冲突的问题。如何快速确定函数p 和相应的*()p λ,是我们要进一步深入研究的。对应于已知网络最大似然的参数是否恰好能够给出最好的预测精度,尚需要我们进一步验证。

(2) 如何评估预测算法的精确性以及如何刻画预测结果的特征。

为了评估链路预测算法的精确性,已知网络的所有连边会被随机划分为两个集合:一个叫做训练集E ,其中的连边看做已知信息;另外一个叫做测试集T ,其中的连边视作未知信息,用于测试预测算法的精确度。对于缺失链路的预测,一般而言两个集合的划分是随机的;对于演化网络的预测,一般而言测试集中的边是新近出现的。假设某算法?给每对在集合E 中没有连边的(x ,y )一个排序r (x ,y )。排序越高(r 值越小)就说明越有可能有连边(例如要预测十条边,就应该给出r =1到r =10所对应的十条边)。我们可以用下面三种指标来度量算法的精确性。

AUC 值。这个指标在链路预测中的应用可以参考Clauset, Moore 和Newman 08年发表在《自然》上的论文。简单地说,AUC 值是一条随机选择的在测试集中的边在算法?中获得了比一条随机选择的不存在的边更高的排序的可能性:

(,)(',')1[(,),(',')]||||x y T x y U E T

AUC r x y r x y T U E T φ∈∈??=??∑∑ 其中U 代表全集,U-E-T 就是不存在的边的集合,而:

1 (,)(',')[(,),(',')]0 (,)(',')r x y r x y r x y r x y r x y r x y φ?

. 注意,算法给出的排序没有相同的。如果是基于相似性的排序,则当两对节点相似性相同的时候,算法可以考虑给出一个随机序。

Precision/Recall 。给定预测的边数L ,如果在这个预测结果中,有M 个是正确的(这M 条边属于集合T ),则:

Precision M L

=

. 相对地,

Recall ||

M T =. 这两个指标可以在文献[J. L. Herlocker, et al., ACM Trans. Inf. Syst. 22 (2004) 5]中找到。

对于预测结果的刻画,可以借鉴[T. Zhou, et al., EPL 81 (2008) 58004; NJP 11 (2009) 123008; PNAS doi: 10.1073/pnas.1000488107]的思想。例如可以用x y k k +或者x y k k 衡量一条边的流行程度(x k 是节点x 的度)。在这个基础上就可以用所有L 个预测结果的平均流行程度来刻画预测的新颖性。当然,这种刻画还是比较粗糙的,进一步地应该观察预测结果中有多少是连接了至少一个大度节点的,有多少是连接了两个小度节点的,等等。如何恰如其分地刻画预测结果的特征,并保证这种刻画方法使得针对不同算法的结果区分度较高,是本项目将要研究的内容。

(3) 建立网络演化规则评估平台的基本思路。

给定了真实演化网络中每条边建立的时间信息,我们可以把一定比例的新近出现的连边作为测试集,在此以前的连边作为训练集。把各种演化模型的规则作用到当前已知的网络结构上,比较新生成的连边和训练集中的连边,就可以评估相应演化模型的准确程度——这就比较自然地把链路预测问题和网络演化模型结合到一起了。实际上,这个平台的评价指标应该还更简单,例如不需要使用AUC 值,还可以令演化生成的边的数目恰等于训练集中的边数,这样Precision 和Recall 的取值都一样。与研究方案第二部分类似,除了精确度以外,我们还可以深入观察不同演化模型相比真实生长过程,具有哪些偏离的倾向?

(4) 拟关注的有代表性的节点相似性指标。

已有的相似性指标按照不同的标准可以划分为不同的类型,下面我们将按照基于节点局部信息,基于网络路径信息,基于网络随机游走和其他较复杂的定义这四类分别进行介绍。

1)基于节点局部信息的相似性算法

共同邻居(Common Neighbors):对于网络中的节点x ,定义其邻居集合为()x Γ,则两个

节点x 和y 的相似性就定义为它们共同的邻居数量,即

()()xy s x y =Γ∩Γ

Salton 指标: Salton 指标定义为

xy s = 其中()()k x x =Γ表示节点x 的度。这个指标也叫做余弦相似性。

[G . Salton, M. J. McGill, Introduction to Modern Information Retrieval, MuGraw-Hill, Auckland, 1983]

Jaccard 指标: Jaccard 指标定义为

()()()()xy x y s x y Γ∩Γ=

Γ∪Γ [P. Jaccard, Bulletin de la Societe Vaudoise des Science Naturelles , 37 (1901) 547]

Sorenson 指标: 这个指标常用于生态学数据研究,其定义为

2()()()()xy x y s k x k y ×Γ∩Γ=

+

[T. S φrensen, Biol. Skr., 5(4) (1948) 1]

大度节点有利(Hub promoted) 指标:这一指标是用来定量刻画新陈代谢网络中每对反应物的拓扑相似程度的,其定义为

()()min{(),()}

xy x y s k x k y Γ∩Γ= 在此定义下与大度节点(hub)相连的边就会得到更高的权值。

[E. Ravasz, et al., Science , 297 (2002) 1551]

大度节点不利(Hub depressed)指标: 该指标与上一个恰相反,定义为

()()

max{(),()}xy x y s k x k y Γ∩Γ=

LHN-Ⅰ(Leicht-Holme-Newman)指标: 该指标由Leicht,Holme 和Newman 提出,定义为

()()()()

xy x y s k x k y Γ∩Γ=×

[E. A. Leicht, P. Holme, M. E. J. Newman, Phys. Rev. E , 73 (2006) 026120]

优先连接(Preferential Attachment): 应用优先连接的方法可以产生无标度的网络结构,在

这种网络中,一条新边连接到节点x 的概率正比于x 节点的度k(x),因此新边连接节点x 和y 的概率就正比于两节点度的乘积,由此可定义两个节点间的相似性为()()xy s k x k y =×。此算法的复杂度较其它算法来说最低,需要的信息最少。

Adamic-Adar 指标: 这个指标是在共同邻居算法的基础上赋予其权重,定义为

()()1log ()xy z x y s k z ∈Γ∩Γ=

[L .A. Adamic, E. Adar, Social Networks , 25 (2003) 211]

Resource Allocation(RA)指标: 此指标的提出受到Adamic-Adar 指标的启发,从网络资源

分配的角度提出。考虑网络中没有直接相连的两个节点x 和y ,从x 可以传递一些资源到y ,而在此过程中它们的共同邻居就成为传递的媒介。假设每个媒介都有一单位的资源并且将平均分配传给它的邻居,则y 可以接受到的资源数就可定义为节点x 和y 的相似度,即

()()1()xy z x y s k z ∈Γ∩Γ=

[T. Zhou, L. Lü, Y .-C. Zhang, Eur. Phys. J. B 71 (2009) 623]

2)基于网络路径的相似性算法

Local Path 指标: 在共同邻居的基础上应用打破简并态的思想提出了不仅考虑一级邻居而且

考虑二级邻居的相似性指标,即23

xy S A A =+,其中A 表示网络的邻接矩阵。由于矩阵元素()n ij A 等于节点i 和节点j 之间长度为n 的路径数目,LP 指标可以看成是基于局部路径(考

虑2阶和3阶路径)的相似性指标。此外,该指标还可以扩展为含参数的形式:

23xy s A A α=+?

其中(1,1)α∈?为可调参数。

[L. Lü, C.-H. Jin, T. Zhou, Phys. Rev. E 80 (2009) 046122]

Katz 指标: Katz 指标是基于所有路径的,因此可看成是基于全局信息的指标。其定义为

,1l l xy x y l s paths α∞

<>==?∑

其中α>0为可调参数,,l x y paths <>

表示连接节点x 和y 的路径中长度为l 的路径数。此定义

还可用邻接矩阵表示为 1()S I A I α?=???

为保证数列收敛,参数α取值要小于邻接矩阵A 的最大特征值的倒数。

[L. Katz, Psychmetrika , 18 (1953) 39]

LHN-Ⅱ指标: Leicht,Holme 和Newman 提出的另一种相似性计算方法,定义为

11111

2()S m D I A D αλλ???=? 其中1λ为邻接矩阵A 的最大特征值,

D 为度矩阵,即ij i ij D k δ=,m 为网络中的总边数,α为可调参数,其取值范围为(0,1)。该指标和Katz 一样也是基于全部路径的,不同的是LHN-II 中n A 前面的系数与n A 的期望值相关,而在Katz 中是一个常数。因此可以将LHN-II 看作是Katz 指标的一个推广。

[E. A. Leicht, P. Holme, M. E. J. Newman, Phys. Rev. E , 73 (2006) 026120]

3)基于网络随机游走的方法

Kernel 矩阵: 也就是网络的拉普拉斯矩阵L 的伪逆,即S L +

=。

[F. Fouss, et al., IEEE Trans. Knowl. Data Eng. 19 (2007) 355; F. Gobel, A. Jagers, Stochastic processes and their applications 2 (1974) 311]

平均通讯时间(Average Commute Time)

(文献同上) (2)xy xx yy xy s l l l E +++=+?

其中ij l +为L +的对应元素,

E 为网络的总边数。 基于L +的余弦指标(文献同上)

cos (,)xy s x y l ++==

局部随机游走指标(Local Random Walk index - LRW)为了提高计算的效率,我们提出了

基于局部随机游走的相似性指标:

()()()22y x xy xy yx k k s t t t E E

ππ=+

其中()xy t π为从节点x 出发的随机游走粒子在t 时刻到达节点y 的概率,此概率可由概率

转移矩阵P 求得,即: ()()(0)T t xy xy t P ππ=

其中(0)xy π为初始向量,除了第x 个元素为1以外,其它元素全为零,T 表示转置。

[W.-P. Liu, L. Lü, EPL, in press]

有重叠的局部随机游走(Superposed Random Walk index - SRW)(文献同上)很多实际的

网络都具有较大的集聚系数,也就是说网络的节点更倾向于与较近的节点相连接。为了体现这种效应,我们提出了有重叠的局部随机游走指标,他的值等于所有不同时间下的LRW 的结果的叠加,即:

1()()t

LRW xy xy l s t s l ==∑

这种方法会使预测精确度在更早的时间达到最优。

4)其他方法

矩阵森林算法(Matrix-forest Algorithm):基于矩阵森林理论提出,其定义为

1()S I L ?=+

其中L 为Kirchoff 矩阵,即()ij L l =,,,ij ij

i j ij l l A i j i j ≠=?≠???=??∑ 这个指标也可以写成含参数的形式:

1()S I L α?=+?,0α>。

[P .Chebotarev, E. V . Shamis, Automation and Remote Control , 58 (1997) 1505]

自恰转移相似性:为克服局部相似性算法仅能刻画用户之间直接相似度,而无法利用间接相

似度的缺点,我们提出自恰转移相似性量度,如下式所示:

()1

1ε?=?T S S

式中S 为某种局部相似性指标(例如Salton 指标),T 为自恰转移相似度,ε为可调参数,用以控制直接相似度和间接相似度的权重比例。

[D. Sun, et al., Phys. Rev. E 80 (2009) 017101]

特别值得强调的是,在这些指标中,有六个指标是项目组成员率先提出的,包括大度节点不利指标,Resource Allocation 指标,Local Path 指标,LRW 指标,SRW 指标和自恰转移相似性。对于以上指标,我们已经有了一些研究。在文章[T. Zhou, L. Lü, Y.-C. Zhang, EPJB 2009]中我们对利用节点局部信息的10种指标在6个实际网络中(每个网络90%的数据用于训练,10%的数据用于测试) 进

行了较详细的研究。应用AUC值度量相似性算法在链路预测中的精确度,我们得到下面两个表。结果显示我们提出的RA算法较其它算法具有明显的优势。

六个用于比较的真实网络的结构特征。六种网络分别是蛋白质相互作用网络,网络科学家合作网,美国国家电网,公共博客空间,自主系统互联网和美国航空网;七个结构性指标分别是节点数、边数、最大连通集团节点数/连通集团数目、网络效率、簇系数、相关系数和度分布异质性参数。详见本项目组09年发表于EPJB的论文

网络N M N c E C R H

PPI 261711855 2375/92 0.180 0.387 0.461 3.73

NS 1461 2742 379/268 0.016 0.878 0.462 1.85

Grid 4941 6594 4941/1 0.063 0.107 0.003 1.45

PB 1224 19090 1222/2 0.397 0.361 -0.079 3.13

INT 5022 6258 5022/1 0.167 0.033 -0.138 5.50

USAir 332 2126 322/1 0.406 0.749 -0.208 3.46

十种基于节点局部信息的相似度指标比较

Algorithms PPI NS Grid PB INT USAir

CN 0.889 0.933 0.590 0.925 0.559 0.937

Salton 0.869 0.911 0.585 0.874 0.552 0.898

Jaccard 0.888 0.933 0.590 0.882 0.559 0.901

Sorensen 0.888 0.933 0.590 0.881 0.559 0.902

HPI 0.868 0.911 0.585 0.852 0.552 0.857

HDI 0.888 0.933 0.590 0.877 0.559 0.895

LHN 0.866 0.911 0.585 0.772 0.552 0.758

PA 0.866 0.623 0.446 0.907 0.464 0.886

AA 0.888 0.932 0.590 0.922 0.559 0.925

RA 0.890 0.933 0.590 0.931 0.559 0.955

此外,对于基于路径的算法,我们也做了一些研究。在文献[L. Lü, C.-H. Jin, T. Zhou, PRE 2009]中我们比较了CN,LP和Katz三个指标。由于LP指标比CN应用了高一阶的信息,因此在算法精度上好于其他基于局部信息的算法。此外,其在时空复杂度上也远远小于基于全局信息的Katz算法。在网络的噪音较大的情况下,LP指标甚至可以达到比全局信息算法更好的结果。因此LP指标在大规模无网络应用上具有很大的前景。

最近,在文章[W.-P. Liu, L. Lü, EPL, 2010]中我们提出了基于局部随机游走的两个相似性指标,并比较了他们和其他6种算法,包括CN,RA,LP,ACT,RWR五种相似性指标,以及08年Clauset, Moore和Newman在《自然》上发表的的层次结构算法。通过在5个实际网络中的比较,发现我们提出的算法精度平均而言最高。但是这涉及一个如何寻找最优的行走步数的问题,通过更进一步的实验,发现这个最优的步数与网络的平均最短距离相关,但是相关的强度如何仍然是个未解决的问题。相信上述已有的工作为我们下一步的研究奠定了坚实的基础。

(5)链路预测的思想和方法如何与部分标号网络中的节点类型判定问题联系起来。

部分标号网络的节点标签分类问题是指:给定某网络以及网络节点的类型库,在已知部分节点的标签类型的情况下应用网络的结构等信息预测剩下未标签节点的类型。例如下图所示,网络中有五个节点,节点分为a和b两类,我们的问题是如何判断节点5的类型。

虽然网络标签分类和网络的链路预测看起来是两个不同的问题,但是在本质上他们要解决的最基本的问题都可以归结为如何定义网络中节点的相似性。因此可以将链路预测中的相似性定义方法应用于节点标签分类的问题中。实验表明链路预测中的一些相似性的定义方法对解决网络标签不一致性和标签节点数量稀疏性有明显的改善作用。如图,利用最简单的直接邻居(Relational Neighbors)的方法可以得到节点5的标签应该是b,因为在她的邻居中标签为b的节点数量多。这种预测方法有效的一个前提就是网络的标签一致性,即一条连边的两端节点具有相同的标签。但是在很多网络中一条边两端的节点类型是不一致的,在这种情况下直接邻居的方法就无效了。而在链路预测中基于共同邻居的方法可以有效地解决这一问题。通过在政治书籍共同购买网络中的大量实验我们发现基于共同邻居方法的预测准确度要高于直接邻居的方法,特别是在网络已知标签节点数很少的时候,效果显著。标签预测的另一个困难就是网络已知标签节点数量稀少,在这种情况下应用基于全局信息的相似性方法可以得到比基于局部相似性的方法更好的预测效果,因为全局的相似性方法可以更加充分的利用已知的节点标签信息。

需要特别说明的是,本项目中相当部分的研究内容属于基础性的、探索性的研究,尽管我们对部分研究内容有一些初步的研究思路,并且可以保证申请团队能够在整体上达到本申请书所承诺的整体目标。但是,并非每一个研究内容我们都有成熟的研究方案,事实上,我们在前期的尝试中,例如如何处理负面信息,已经遇到了一定的困难。

3.2 可行性分析

(1)研究问题的可行性。复杂网络链路预测是一个具体而集中的研究题目,本项目团队以“选题不大,贡献不小”为宗旨,所设定的关于理论、算法和应用方面的研究目标,一方面具有相当的挑战性,另一方面也具有通过努力解决或部分解决的可能性。根据我们的研究经验和初步研究结果,我们认真分析了项目成功的关键科学问题,认为本项目的整体目标,既全方位推动复杂网络链路预测的研究,在通过努力工作之后是能实现的。

(2)研究方法和技术路线的可行性。通过对研究内容的限定和关键问题的分析,我们在3.1节列出了完成本项目最主要的一些概念方法和技术手段。首先,我们已经获得开展研究的大量真实数据;其次,我们已经实现了部分申请书提到的算法,并对复杂网络结构特征分析与网络演化模型非常熟悉;最后,项目组研究经验丰富,在很多与本申请课题技术手段相近的研究中获得了较大的成功,包括个性化信息推荐和复杂网络演化的实证与建模。

(3)研究基础较好,准备工作充足。项目组成员具有相当优秀的研究实力,具有开展本项目研

究最重要的人才基础。项目申请团队在链路预测方面已经是国际上较领先的团队,在《欧洲物理快报》和《美国物理评论》上发表了若干密切相关的研究内容。特别地,在基于相似性框架的链路预测方面,应该是国际上研究最为系统深入,也是最活跃的团队。另外,申请团队在相关的研究方向,例如信息挖掘与信息推荐,复杂网络演化的实证分析与建模等方向上也具备国内一流,国际领先的水平。最近2年在《新物理学》、《欧洲物理快报》和《美国科学院院刊》发表的数篇论文,被NatureNews,PNAS News, PhysOrg,TG Daily及L’Atelier报道。项目申请人(电子科技大学团队负责人)周涛于2008年获得第五届中国青少年科技创新奖,于2009年获教育部自然科学一等奖,2009年获得安徽省自然科学一等奖,其论文SCI引用超过1200次,具有圆满完成本项目的科研素养。项目申请人(弗里堡大学团队负责人)张翼成教授是交叉物理方向国际上享有盛名的学者,具有相当丰富的研究经验,并明确承诺将会投入相当精力参与到具体的科研合作中。他领导的信息推荐研究小组已经正式列入维基百科条目专门介绍。我们在下面的工作基础部分列出了与本课题相关的项目组具代表性的研究成果,在申请人简介部分也有相应描述,此处不再赘述。

(4)研究队伍结构合理,经验丰富。项目团队成员中包括国际著名的科学家和年富力强的青年科技工作者,其中高级职称2名,具有博士学位的国外博士后青年学者1名,博士生2名,硕士研究生3名(均有转博意愿),人员配置结构合理,队伍年轻,而且绝大部分成员都具有相当的科研经验,能够独当一面进行科研工作(参考人员简介)。研究人员还和国际上相关研究人员保持密切联系和合作(项目申请团队成员近5年来和二十余个国家地区的超过百名不同学者合作发表过论文),这些丰富的合作资源可以保证项目执行过程中一直处于学科发展的前沿。电子科技大学和瑞士弗里堡大学承诺项目组人员具有充足的研究时间。

(5)计算资源有保障。电子科技大学将为项目开展提供国内一流的工作环境。课题组目前拥有120余平方米的专用实验室,IBM服务器1台,个人计算机10余台,开发用笔记本电脑10余台,拥有完善的计算机网络,齐备的软件开发环境,拥有充足的图书及网络资源。此外,课题组成员还可以使用IBM主机系统教育中心的IBM Z系列大型机和联想深腾1800大型计算机,使用国家级计算机实验教学示范中心的400余台资源和设备。

(6)数据来源有保障。项目组在前期研究工作中已经收集和整理了大量数据资源,这些数据包括在研究方案部分提到的一些公开的基准数据库以及https://www.doczj.com/doc/8818223631.html,和Livejournal这样的大规模在线社会网络数据,同时我们通过网络爬虫收集和整理了一些原创数据。我们和中国移动、阿里巴巴集团淘宝商业数据部、四川电信等企业已有协议或意向共享数据,还会和其他研究团体交换相关的数据库资源。

综上所述,本项目研究内容明确、具体,研究方法得当,技术路线切实可行,开展研究所需的数据、人力、计算资源等都有保障,研究人员具有良好的研究基础,我们相信项目组必将会高质量地完成所承担的研究任务和内容,并取得较好的研究成果。

4 本项目的特色与创新之处

本项目着眼于全方位地推动复杂网络链路预测方面的研究。项目的特色与创新之处分别可以总结为四点和三点。

特色之处!

(1)研究内容的完整性和系统性。复杂网络链路预测是一个比较具体化集中化的研究对象,本项目拟对该问题从理论到应用各个方面全面进行研究,有望整体上推动这个方向的发展。

(2)数据与测试平台共享。这是本项目不同于一般基础理论研究的重要特色!对于统计物理与复杂性科学的若干研究问题,数据的再获取和对相关研究的算法再现上的困难往往制约研究的进展,这使得很多比较性地研究无法在具有一致性的数据和算法上进行。本项目拟开放所有用于研究的数据和算法测试平台,建立用于国际学术交流的链路预测研究网站。

(3)给出具有实用性的链路预测算法选择指南。通过系统研究若干有代表性的链路预测算法以及有代表性的算法评估指标,并通过分析网络结构特性和预测质量的关联关系,揭示网络结构和预测精度之间的关联关系,从而最终形成有助于算法设计参考,提高算法性能的链路预测算法选择指南。该研究思路有望推动并最终解决具有相当挑战性的一个问题:如何为具有不同特征的数据集/系统选择适当的算法。

(4)理论基础研究和应用研究紧密结合。对复杂系统若干年的研究经验告诉我们,对真实系统的深入分析,不仅仅具有相当的应用价值,而且往往带来很多新的理论问题,甚至揭示很多理论研究中难以察觉的深刻见解。本项目不仅仅在一个网络模型和小规模数据上进行理论分析,还将深入研究大规模甚至超大规模的真实系统,并对预测结果进行非常深入细致的分析,这种理论与应用深度的结合是本项目的重要特色。

创新之处!

(1)建立基于节点相似性的链路预测算法的理论框架。在给定相似性指标的基础上对网络结构进行最大似然分析,将最大似然分析的结果和预测精度进行比较,并藉此设计直接利用最大似然分析进行相似性指标寻优的算法,其整个研究思路都是原创的。

(2)考虑含有异质边的链路预测问题,以及如何利用负面信息。绝大多数已知的链路预测算法都是针对简单无向网络的。本项目拟关注的比较复杂的情形,例如有向网络、含权网络和多部份网络,可以看作是对以前研究的重要推广。而对于含有异质链路的网络实现链路预测,以及如何利用负面信息,则可视作本项目重大的且有相当挑战性的创新。

(3)对预测结果的分析。在已知的所有的链路预测研究中,精确度都是唯一的评价标准,因此事实上目前没有任何研究工作报道了对于预测结果的深入分析,例如什么样的算法倾向于准确预测哪种类型的链路?这些研究有望在复杂情形下帮助设计出结合多个算法优点的混合算法,且能大大加深我们对链路预测算法的深入理解。对于预测结果整体统计性质的刻画指标,以及相关的研究思路和分析手法,都是具有原创性的。

5 年度研究计划及预期研究结果

5.1 年度研究计划

2010年4月-2010年12月(预研阶段)。进一步阅读相关文献资料;收集和整理各类可以用于链路预测研究的网络数据,包括演化网络数据和各类具有较复杂结构的网络数据;实现用于本项目研究的几乎所有的基于相似性的链路预测算法。

2011年1月-2011年12月(理论研究)。建立基于相似性的链路预测框架的理论基础,并在这个理论原型上讨论对各类相似性指标预测的精度进行评估的可能性和可行性;设计快速准确的算法,确定含参数的相似性指标的最优参数;建立可用于评估网络演化模型的平台,并以有代表性的AS-Internet,WWW(局部),在线社会网络,科学家合作网等真实网络为例,在该平台上测试已知的若干演化模型;总结理论研究结果,撰写学术论文,在学术会议上报告研究成果。

2012年1月-2012年12月(算法研究)。研究具有较复杂结构的网络的链路预测算法;研究如何处理异质边的预测问题和如何利用负面信息;研究网络结构对链路预测算法性能之间的关系,总结具有实用价值的通过结构分析指导算法选择的手册;深入分析不同算法预测结果的异同;总结研究结果,撰写学术论文,在学术会议上报告研究成果。

2013年1月-2013年12月(应用研究)。以真实大规模在线社会网络为例,讨论有代表性的链路预测算法的效率和精确度,深入挖掘预测结果是否准确的内在原因;开发可供学术界免费共享的算法测试平台;以中国移动手机用户通话数据为基础,设计可以预测和分析用户离网行为的快速算法;总结研究结果,撰写学术论文,在学术会议上报告研究成果;总结整个项目研究,撰写专著或综述。

5.2 预期研究结果

(1)给出国内外同行认可的对于深入全面理解复杂网络链路预测问题有贡献的基础研究成果。

(2)在国内外学术期刊发表10篇左右学术论文,其中至少有一篇发表在《Nature》《Science》《PNAS》《PLoS ONE》这四种具有重大影响力的综合性期刊上,另外至少有4篇论文发表在物理方向的综合性权威期刊上,包括《自然-物理》《美国物理评论》《欧洲物理快报》和《新物理学》。

(3)秉承自然科学基金培养基础研究人才的宗旨,培养出一批在复杂网络和信息挖掘领域能够独立从事创新研究,并开拓新方向的青年学者。具体包括:培养博士研究生3-4 名,硕士研究生2-3 名。

(4)公开相关研究数据和算法代码,公开具有实用指导意义的链路预测算法选择指南,建立与本项目相关的数据和程序共享以及算法测试平台,建立复杂网络链路预测的学术交流网站。

5.3 重要学术交流活动、国际合作与交流计划

本项目系国际合作项目,每年都会较频繁开展中国-瑞士相关学生、学者的学术互访。除此之外,本项目拟支持国内学者4人次参加国际学术会议或国际学术交流。除此之外,本项目将联合支持第6届中国-欧洲复杂性科学暑期班(2012年),并拟协办一届全国复杂网络会议。

(二)研究基础与工作条件

1 工作基础

本项目组由电子科技大学和瑞士弗里堡大学两个研究团队组成。两位团队负责人均有非常丰富的研究经验和在相关领域相当的国际影响力。近3年来有近20篇有关链路预测、复杂网络演化实证分析和建模,信息挖掘和信息推荐的研究论文在以下5种较好的期刊尚发表:Physical Review E, Physical Review Letters, PNAS, New Journal of Physics, Europhysics Letters,文章被NatureNews,PNAS News, PhysOrg,TG Daily及L’Atelier报道。申请人关于复杂网络结构和功能的研究成果获得了2009年教育部自然科学一等奖,和2009年安徽省自然科学一等奖。本项目的其他成员,包括1名博士后,2名博士生和3名硕士生(有明确攻读博士学位意愿)都已经具备独挡一面的科研能力或表现出相当的潜力。

下面分三个方面列出本项目组成员近3年(2007年及以后)完成的和本项目密切相关的学术论文,其中项目成员以黑体和下划线强调。

相关主题
相关文档 最新文档