complexityworld分享 http://blog.sciencenet.cn/u/pb00011127

博文

大数据研究中心简报(第2期):研究进展部分

已有 18854 次阅读 2015-4-17 10:48 |个人分类:生活点滴|系统分类:科研笔记

复杂网络链路可预测性

链路预测(Link Prediction)是网络科学中一个基础性的重要问题。该问题从已经观察到的网络结构入手,预测可能被观察漏掉的,或未来会出现的链路。精准的预测结果可以指导生物网络结构验证实验,大幅度节省实验成本和提高实验效率;可以进行在线社交网络的好友推荐;还可以挖掘出网络生长的内在机制。

针对这些问题,电子科技大学,大数据研究中心周涛教授和互联网科学中心博士生潘黎明提出用网络特征向量空间来衡量网络的结构规则性,并假设网络规则性越强,受随机增加或减少链路的扰动影响越小。通过应用类似于量子力学中对哈密顿量做一阶微扰的方法,潘黎明等人提出了名为结构一致性structural consistence)的新指标,这个指标是网络的一个特征指标,并可以直接用来刻画网络可被预测的程度。在此基础上,潘黎明等人提出了一种名为结构微扰法的新的链路预测方法,其在预测丢失链路以及甄别噪音边两方面都明显超过了当前主流的方法。

这一研究成果发表在《美国科学院院刊》(PNAS)上,潘黎明、周涛与吕琳媛为共同第一作者。《美国科学院院刊》是与NatureScience齐名,被引用次数最多的综合学科文献之一,在SCI综合科学类期刊排名第三位。

论文信息:

L.Lü, L. Pan, T. Zhou(周涛), Y.-C. Zhang, H. E. Stanley, Toward link predictability ofcomplex networks, PNAS 112 (2015) 2325-2330.

论文链接:

http://www.pnas.org/content/112/8/2325.abstract


多路数据分析中的贝叶斯非参方法

科学进步和经济发展的过程中总是伴随着海量的、动态的、结构复杂的数据的产生,人们称之为大数据。大数据是数字化生存时代的新型战略资源,是驱动创新的重要因素,正在改变人类的生产和生活方式。除了大数据的5V(Volume, Velocity, Variety, Veracity,Value)特性外,含有丰富数据的现实系统通常还具有:(1)高度复杂性,即数据由多个数据源或者多个方面组成;(2)数据存在显著稀疏性或不完整性。例如淘宝网会员超过3.7 亿人,在线商品超过8.8 亿件,每天交易数千万笔,产生约20TB数据;这里,<用户-商品-交易-时间>也构成一个多元稀疏关系。深刻理解这些多元关系中互动行为有助于把握隐藏在数据中的知识和掌握数据的变化规律。

现实世界中数据的多源多方面特性已不足于由传统的向量和矩阵表示,为此张量(Tensor)作为数据的新的表示方式引起了学术界和工业界的广泛关注。张量可以表示为多维数组(Multidimensional Array),是向量和矩阵的拓展(向量是1维张量,矩阵是2维张量)。这里,多维数组中的每一维被称为张量的一个方面(Aspect)或模(mode)。相比于向量和矩阵,张量结构直观上易于表示现实世界原本存在的多元关系和多方面特性,而向量容易丢失原始数据的结构特征;而且张量可以充分考虑不同方面之间的相关性与互补性,向量表示很难表述上述关系。由于张量数据中缺失值的广泛存在以及低秩性等特征,对张量数据的处理主要是通过张量分解(Tensor Decomposition)的方法。张量分解是机器学习、数学分析、图分析、计算机视觉、推荐系统中的一类重要方法。通过张量分解,可以获得多源多方面数据中每一个对象的隐藏因子,从而可以恢复张量中的缺失值,并解释数据变化的规律。

张量分解的算法主要包括Tucker分解和并行分解(PARAFAC)。目前,已有的张量分解算法是基于Tucker分解和并行分解的扩展。Tucker分解模式可由左图所示:给定张量M ,张量分解的目标是寻求低秩矩阵U1U2U3和核心张量(Core TensorW的乘积来逼近M。这里U1U2U3称为张量在各个方面上的因子。Tucker分解可以表示为:PARAFACTucker分解的特殊情形:当强制W是对角张量,而且张量的各个模(也叫方面)中因子的数目都相等()Tucker分解就退化为PARAFAC了。传统的张量分解算法已成功地应用到了各个领域,然而,它们大多属于线性分解(Multilinear Decomposition)算法,不足以对张量元素间的复杂交互关系进行充分描述。张量中大量存在的缺失值(Missing Value)也给线性分解模型带来了挑战,而且线性算法很难对张量的数值类型(如二进制、有序、数量型、离散型)进行建模。

为了解决上述问题,电子科技大学,大数据研究中心,大数据挖掘与推理研究所徐增林教授,Facebook公司严丰博士,和普渡大学漆远教授共同提出了一种基于张量高斯过程(Tensor-variate Gaussian Process)的非线性Tucker分解模型,称为无限张量分解(Infinite Tucker Decomposition)。在这个模型中,张量中元素的相似性可以用任意核函数(Kernel Function,例如高斯核函数)来度量。为了能够表示不同的数据类型,该模型通过采用不同的连接函数(Link Function)来映射隐张量(Latent Tensor)和观察到的张量(Observed Tensor)的关系。徐增林教授等首次将张量分解问题转变为一个非线性模型,并支持所有的数据类型。实验表明,该方法取得了比传统张量分解模型更高的预测精度。

 

论文信息:

Zenglin Xu(徐增林), Feng Yan, and Yuan (Alan) Qi.Bayesian nonparametric models for multiway data analysis. IEEE Transactions onPattern Analysis and Machine Intelligence, 2015, 37 (2): 475-487.

论文链接:

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6629993


大规模系统所有反例搜索方法研究

模型检测是重要的软件安全验证的形式化方法之一。通常模型检测方法返回单个反例。然而单个反例在软件故障定位(调试)中会存在信息不足的问题,会极大延长软件的验证和调试周期。

针对这一问题,电子科技大学,大数据研究中心,安全大数据研究所题为“An I/O Efficient Approach forDetecting All Accepting Cycles”的论文在CCF(中国计算机学会) 推荐的A类国际期刊《IEEE Transactions on Software Engineering》上发表。该文由电子科技大学吴立军副教授、张小松教授、王舒鹏研究生、澳大利亚格里菲斯大学苏开乐教授、蔡少伟博士、澳大利亚昆士兰大学张诚一讲师共同完成。吴立军副教授为第一作者,张小松教授为通信作者。

吴立军等人对现存模型检测技术进行改进,第一次提出了大规模系统所有反例的搜索方法。理论分析和试验结果证明尽管搜索的是所有反例,但其算法复杂度和实际性能仍然优于现有模型检测单反例搜索的最佳方法。

CCF将著名的国际期刊和国际会议分为ABC三类。A类指国际上极少数的顶级刊物和会议,鼓励我国学者去获得重大突破。《IEEE Transactions on SoftwareEngineering》是软件工程领域中最具影响力的A类期刊。该期刊为双月刊,每年总共收录几十篇软件工程领域的顶尖论文。

论文信息:

Lijun Wu(吴立军), Kaile Su, Shaowei Cai, XiaosongZhang(张小松), Chenyi Zhang, Shupeng Wang. An I/OEfficient Approach for Detecting All Accepting Cycles. IEEE Transactions onSoftware Engineering,2015.3

论文链接:

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=7056483


耦合网络上非对称作用的传播动力学研究

流行病传播和消息传播是复杂网络上的两大基本传播动力学过程,已有研究大多都是独立的分析这两个传播动力学。然而,实际生活中它们却紧密相关,存在非对称耦合作用。比如,大规模的流行病爆发依赖于关于疾病消息的传播,尤其是流行病传播初期,个体意识到存在感染邻居将采取措施保护自己,从而极大程度的抑制了流行病传播。探究消息传播和流行病传播的内在机制及其相互影响已成为复杂网络科学的一个新的研究方向。

针对这一问题,大数据研究中心,网络科学实验室博士生王伟在唐明副教授的指导下,与本校博士生杨慧、韩国庆北大学Younghae Do教授、GyuWon Lee教授和亚利桑那州立大学Ying-Cheng Lai教授合作在《Scientific Reports》发表“Asymmetrically interacting spreadingdynamics on complex layered networks”一文。王伟等人研究了消息和疾病在各自的网络上传播且它们之间存在非对称耦合作用的情况,重点关注爆发阈值和传播范围两个重要指标。他们发现接触网络上的流行病爆发会引发通讯网络上的消息爆发,而消息的传播会增加疾病的爆发阈值。此外,两个子网之间存在度关联并不改变消息爆发阈值,却有利于抑制疾病爆发。他们发展了一套数学解析方法来研究消息和疾病传播动力学之间的相互作用。他们的研究模型和理论框架加深了人们对信息-疾病耦合动力学、社会-生物传播系统的理解和认识,有助于进一步揭示个人、经济和社会等方面因素在流行病传播过程中的影响机制,也为流行病预警和控制提供了理论指导。

 

论文信息:

Wei Wang(王伟), Ming Tang(唐明), Hui Yang(杨慧), Younghae Do, Ying-Cheng Lai, and GyuWon Lee,Asymmetrically interacting spreading dynamics on complex layered networks, Sci.Rep. 4: 5097 (2014).

论文链接:

http://www.nature.com.sci-hub.org/srep/2014/140529/srep05097/full/srep05097.html


网络上具有粘滞性和持续性特征的消息传播:高的簇系数并不总是促进大尺度的传播

与疾病传播机制不同的是,最近的实证研究工作已经证实一些复杂的认知机制例如记忆效应、社会加强效应和衰减效应在消息和行为传播过程中起着关键作用。

根据以往的实证研究结果和理论分析,兰州大学的崔鹏碧博士、吴枝喜教授和电子科技大学,大数据研究中心的唐明副教授一起提出了一个考虑这三种机制共同作用并将其量化为消息粘滞性和持续性的消息传播模型。通过利用渗流理论对不同网络上的消息传播的相变行为进行解析和分析,研究发现在树形网络上粘滞性决定了消息的最终传播规模和相变行为,同时持续性的重要性也不可忽略但其作用被拐点位置所决定。与之前研究结论不同的是,仅当消息爆发开来的时候,其在规则晶格网络上传播范围才会比在树形网络上更广。持续性此时在消息传播中扮演着更重要的角色。但是当衰减性比较强时,由于最短路径和hub节点的存在,消息更容易在树状网络上爆发和传播到更广的范围。这也就是说高的簇系数并不总是促进大尺度的传播。针对实际中含有复杂认知机理的消息传播现象,这个工作提供了一个可能的理论分析框架。

 

论文信息:

Pengbi Cui (崔鹏碧)Ming Tang (唐明)Zhi-Xi Wu (吴枝喜)Message spreading in networks with stickiness and persistence:Large clustering does not always facilitate large-scale diffusion, Sci. Rep.,2014, 4: 6303.

论文链接:

http://www.nature.com/srep/2014/140909/srep06303/full/srep06303.html


网络核心结构挖掘和超级传播源的识别

复杂网络方法被广泛的应用于建模和分析真实世界的复杂系统。控制和预测网络上的传播行为是一个重要课题。在网络结构中,核心节点位于网络的中心,是传播中最有影响力的传播源。对核心节点的定位和控制决定了传播控制的效果。中心性指标常被用于确定网络的核心,其中一个重要方法是k-shell分解。通过迭代的剪去度小于等于k的节点,网络被分解为从核心到边缘的壳层,核心层被认为是网络的核心。这一方法广泛的应用于网络核心的挖掘和分析,如生物网络、科学家合作网、朋友关系网、通信网络等。

然而,通过对多个不同类型真实网络的核心结构的分析,我们发现并非在所有的真实网络中,k-shell方法都能准确定位网络核心。在许多网络中,k-shell方法找到的核心是假核心。这对之前基于k-shell方法的工作提出了挑战。通过对网络结构的细致分析,我们发现网络中存在局域连接过于紧密的小团体,它们是形成假核心的原因。进一步的,我们基于信息熵理论中熵的定义,提出了网络连接熵,度量网络壳层连接的多样性。局域连接紧密的小团体具有相对低的信息熵。这一方法为更加准确的确定网络核心提供了依据。

该工作由电子科技大学互联网科学中心、大数据研究中心的刘影博士、唐明副教授、周涛教授及韩国庆北大学的都永海教授合作完成,并发表在2015年的Scientific Reports上。

 

论文信息:

Ying Liu (刘影), Ming Tang (唐明), Tao Zhou (周涛), and Younghae Do (都永海), Core-like groups result ininvalidation of identifying super-spreader by k-shell decomposition. ScientificReports, 2015, 5:9602.


时间尺度的多样性促进零行列式策略在网络系统中涌现

零行列式(Zero-determinant strategy, ZD)策略是近年来博弈论关注的一类重要策略,使用零行列式策略的个体可以单方面保证双方期望收益满足线性关系。零行列式策略为刻画博弈双方作用关系提供了全新的研究视角,正在改变博弈理论的研究范式。剥削策略(Extortion strategy)—它可以使自身收益是对手的任意倍—作为一类重要的零行列式策略近年来被广泛关注。最近的研究指出,剥削策略在种群中通常不是演化稳定的,但它可以作为触媒促使合作行为在种群中涌现。因此,以剥削策略为代表的零行列式策略在种群中的演化机理正被深入研究。

网络演化博弈中存在两类相互耦合的网络:相互作用网络和策略演化网络,前者描述了个体与谁博弈;后者刻画了个体行为的变化,二者演化的时间尺度可能不同。基于前期网络中时间尺度演化研究的基础上,荣智海教授、吴枝喜教授(兰州大学)、郝东博士、Michael Chen博士(香港大学)、周涛教授合作探讨了策略演化时间尺度的多样性对剥削策略的演化作用机理。考虑获得高收益的个体更倾向于维持当前行为而减缓策略演化速度,因此可以将策略演化时间尺度与个体收益联系,研究因收益导致的不同时间尺度的个体在规则格子、随机网络和无标度网络中的剥削策略演化过程。不同于过去认为剥削策略在均匀混合种群中的演化不稳定,该文发现策略演化时间尺度因素的引入会促使剥削策略在网络环境中的稳定存在,并进一步导致合作行为的涌现。由于个体收益与时间尺度之间的反馈作用,无标度网络中大度节点更倾向于采取剥削策略,促使合作行为在异质的无标度网络中更容易涌现。这可以为群体行为调控和多智能体协议设计提供理论指导。

 

论文信息:

Z. Rong(荣智海), Z. Wu(吴枝喜), D. Hao(郝东), Michael Z. Q. Chen(陈志强), T. Zhou(周涛) (2015), Diversity of time scalepromotes the maintenance of extortioners in spatial prisoner's dilemma game,New Journal of Physicsvol.17, pp.033032.

论文链接:

http://iopscience.iop.org/1367-2630/17/3/033032

 




http://blog.sciencenet.cn/blog-3075-883134.html

上一篇:耦合网络上非对称作用的传播动力学研究
下一篇:大数据研究中心简报(第2期):中心简讯部分

3 王军 陆泽橼 荣智海

该博文允许注册用户评论 请点击登录 评论 (4 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2020-2-17 18:08

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部