法律状态公告日
法律状态信息
法律状态
2019-10-18
授权
授权
2017-04-19
实质审查的生效 IPC(主分类):H04L12/24 申请日:20161111
实质审查的生效
2017-03-22
公开
公开
技术领域
本发明属于数据挖掘算法技术领域,特别是一种多层网络中的基于路径熵的链路预测方法。
背景技术
链路预测(Link Prediction)问题是数据挖掘的研究方向之一,因其有重要的理论研究意义和广泛的应用价值而受到各个领域的关注。链路预测指如何根据已知网络节点的属性和网络拓扑等信息,预测网络之中未产生连边的节点对之间产生链接的可能性。计算机领域特别是数据挖掘领域的学者较早开展了链路预测算法方面的研究,采用的工具主要包括监督学习、马尔可夫链、似然估计等。这类算法存在以下几个缺点:(1)对样本数据要求高,即需保证节点属性信息的可靠性;(2)复杂度高,对大规模网络限制大;(3)普适性低,即对不同的网络需要采用不同的参数组合以达到好的预测性能。
近些年,在网络理论迅猛发展的带动下,数学、物理、信息等领域的学者进一步掀起了网络链路预测的热潮。主要思路是运用包括图论、统计物理、信息论等工具度量节点对之间的结构相似性和网络链路可预测性,典型的相似性方法包括Common Neighbors(CN)、Adamic-Adar(AA)、Resource Allocation(RA)等局部相似性方法,Local path(LP)等准局部方法,以及Katz、LHN-II等全局相似性方法。其中,CN方法假设两个节点的共同邻居越多,它们就越倾向于连边。在此基础上,考虑邻居间的贡献差异,又派生出AA和RA方法,而Katz、LHN-II方法则进一步考虑了节点对间所有路径的数目。这些相似性方法没有充分考虑甚至忽略了节点、连边类型和路径的异质性,不能很好地抓住目标网络的结构特征,故预测精度有待提高。
信息论作为理论工具能够很好地度量复杂网络拓扑结构的信息熵,从而能够进一步用于衡量节点之间的相似性。目前基于信息论的预测算法方面的研究才刚刚起步,例如基于二阶路径的Mutual Information(MI)算法用互信息刻画共同邻居节点的贡献,较经典算法预测精度有了明显提升,但仍存在以下缺点:计算复杂度高,很难应用于大规模网络;仅仅考虑节点的信息熵对链路预测的贡献,而未考虑边、路径等关键结构的信息熵及其贡献,因此有待进一步扩展。为克服该弱点,本发明从信息论角度研究了网络路径的信息熵,并应用于刻画路径的拓扑贡献以充分考虑路径之间的异质性。注意到,真实网络中的关系往往也具有异质性,即实体之间具有多种不同类型的关系。不同类型的关系拓扑对关系的预测也有着不同的影响作用。目前为止的大多数链路预测算法都只是基于单层网络,即只考虑了单一的连边类型,而忽视了网络连边的异质性。
发明内容
本发明的目的在于提供一种预测性能高、计算复杂度相对较低、应用于多层网络的基于路径熵的链路预测方法。
实现本发明目的的技术解决方案为:一种多层网络中的基于路径熵的链路预测方法,包括如下步骤:
步骤1,根据复杂网络理论将真实网络抽象得到多层网络N′的时序序列G=<G0,G1,...,Gn>,n为N′的节点个数;
步骤2,选择时间戳tk将时序序列G分为训练集和测试集;
步骤3,利用信息理论建立预测方法模型;
步骤4,分别独立挖掘训练集中各层的拓扑信息,来预测测试集中的新增连边信息,从而得到各层作用参数;
步骤5,应用训练后的预测方法预测网络的未来信息。
进一步地,步骤1所述将真实网络抽象得到多层网络的时序序列G=<G0,G1,...,Gn>,具体如下:
截取真实网络发展过程中的若干个网络状态,将每一个状态的网络抽象为静态多层网络,将真实网络中的个体抽象为节点,将个体间的关系按照关系类别抽象为不同层中的连边。
进一步地,步骤2所述选择时间戳tk将时序序列G分为训练集和测试集,具体如下:
将时序序列G按照90%和10%的比例拆分为训练集和测试集,并将训练集和测试集的网络信息分别标识为学习网络数据Glearn和标识网络数据Glabel,Glearn和Glabel分别由t0~tk-2和tk-1~tn这两个阶段的网络拓扑的并集得到,即有
进一步地,步骤3所述的利用信息理论建立预测方法模型,具体如下:
若要预测第k′层k′∈{1,...,∝}中的缺失或未来节点对,则需要计算该层中的给定节点对的相似性分数,对于节点对(a,b),需要计算该节点对在k′层中的相似性分数
各层网络相互独立,又有:
即
其中,∝表示边的类型数,即多层网络N′的层数;
进一步地,步骤4所述的分别独立挖掘训练集中各层的拓扑信息,来预测测试集中的新增连边信息,从而得到各层作用参数,具体如下:
对于第i层而言,只根据第i层拓扑信息G[i]去估计第k′层中(a,b)的相似性分数
若Glearn中共有不相连的实例节点对m对,Glearn相对于Glabel新增mpositive对正实例,那么负实例的个数为mnegtive=m-mpositive对,按照式(3),Glearn中所有实例的相似性分数被计算得到,并按照分数从大到小排序,若该有序实例列表的前mpositive对中有m′对属于正实例,则计算i层的回归率Precisioni的式子为:
继而i层的作用参数βi=∝*recisioni。
进一步地,步骤5所述应用训练后的预测方法预测网络的未来信息,具体如下:
训练后得到各层的作用参数β1,β2,β3,...,β∝之后,就能得到
本发明与现有技术相比,其显著优点为:(1)将包含多种类型关系的真实网络抽象成多层网络,即一种关系对应一层网络,充分考虑连边类型的异质性以进一步提高预测精度;(2)同时利用连边和路径的异质性,并挖掘多层网络中的拓扑价值来预测连边,能够充分提高链路预测算法的预测性能;(3)具有预测性能高、计算复杂度较低的优点,能够被用于复杂系统中信息的还原和预测,特别是社交网络的推荐系统之中。
附图说明
图1是得到学习网络数据和标识网络数据图。
具体实施方式
下面结合附图及具体实施例对本发明作进一步详细说明。
本发明为一种同时考虑路径异质性和连边类型的、基于路径熵的链路预测方法,下面阐述方法的框架模型。
一、在复杂网络理论框架中,图模型被用来分析和处理真实网络。通过图论,网络中的个体被表示为图中的节点,关系被表示为连边。给定网络N,其能被建模成图G(V,E),其中V和E分别是是节点集合和边集合。考虑到个体关系的异质性,即节点间连边含有多种不同的类型,N能够被描述为多层网络N′,N′的每一层网络都表示一种类型的关系集合。N′被定义为多层图:
其中,V是节点集合,Ek表示类型为k的边的集合。∝表示边的类型数,即多层网络N′的层数。本发明方法涉及的相关概念定义如下:
(1)G[k]是N′的第k层的网络拓扑信息;
(2)n=|V|是N′的节点个数;
(3)mk=|Ek|是N′的第k层中的总边数;
(4)
(5)
(6)
二、本发明的预测方法的原理如下:
计算节点对的节点相似性是衡量节点对间相连概率的主要方法。基于节点相似性的链路预测方法都基于相似性假设,该假设认为若节点对之间的相似性越大,则这两个节点相连接的概率就越大。如对于节点对(a,b),a和b间存在一条单边的概率为
三、本发明多层网络中的基于路径熵的链路预测方法,包括如下步骤:
步骤1,根据复杂网络理论将真实网络抽象得到多层网络N′的时序序列G=<G0,G1,...,Gn>,n为N′的节点个数,具体如下:
截取真实网络发展过程中的若干个网络状态,将每一个状态的网络抽象为静态多层网络,将真实网络中的个体抽象为节点,将个体间的关系按照关系类别抽象为不同层中的连边。
步骤2,选择时间戳tk将时序序列G分为训练集和测试集,具体如下:
将时序序列G按照90%和10%的比例拆分为训练集和测试集,并将训练集和测试集的网络信息分别标识为学习网络数据Glearn和标识网络数据Glabel,Glearn和Glabel分别由t0~tk-2和tk-1~tn这两个阶段的网络拓扑的并集得到,即有
步骤3,利用信息理论建立预测方法模型,具体如下:
若要预测第k′层k′∈{1,...,∝}中的缺失或未来节点对,则需要计算该层中的给定节点对的相似性分数,对于节点对(a,b),需要计算该节点对在k′层中的相似性分数
各层网络相互独立,又有:
即
其中,∝表示边的类型数,即多层网络N′的层数;
步骤4,分别独立挖掘训练集中各层的拓扑信息,来预测测试集中的新增连边信息,从而得到各层作用参数,具体如下;
对于第i层而言,只根据第i层拓扑信息G[i]去估计第k′层中(a,b)的相似性分数
若Glearn中共有不相连的实例节点对m对,Glearn相对于Glabel新增mpositive对正实例,那么负实例的个数为mnegtive=m-mpositive对,按照式(3),Glearn中所有实例的相似性分数被计算得到,并按照分数从大到小排序,若该有序实例列表的前mpositive对中有m′对属于正实例,则计算i层的回归率Precisioni的式子为:
继而i层的作用参数βi=∝*recisioni。
步骤5,应用训练后的预测方法预测网络的未来信息,具体如下:
训练后得到各层的作用参数β1,β2,β3,...,βx之后,就能得到应用式(2)去计算第k′层中所有的不相连的节点对的相似性分数,并按分数从大到小排序,根据步骤三中的预测方法模型,最终确定预测结果,即分数最高的前几个实例就是预测所得结果。需要预测的节点对个数可能不止一个,比如若要预测L个,那么就是前L个,方法最后得到的结果是按照分数从大到小排序后的节点对集合,即分数越大,越可能相连。
实施例1
本发明的方法测试:
本仿真实验采取visual studio 2015软件,使用C++语言编写。实验中采用了复杂网络研究领域公开的真实网络测试数据。在本发明的仿真实验之中,为了兼顾预测性能和计算复杂度,考虑的路径长度l为3。
本实验在多个真实网络数据上做了仿真测试,共对比了三类经典预测方法在模拟环境下的表现:基于局部拓扑的预测方法(如CN,RA等)、基于全局拓扑的预测方法(如Katz等)、基于准局部拓扑的预测方法(如LP等)。实验结果证明本发明提出的预测方法在保证合理计算复杂度的同时比经典预测方法的预测性能更好。
机译: 设置火车移动转发器的下行链路和上行链路路径的增益,涉及基于下行链路中自动电平控制中生成的参数来设置上行链路路径中的衰减
机译: 设置火车移动转发器的下行链路和上行链路路径的增益,涉及基于下行链路中自动电平控制中生成的参数来设置上行链路路径中的衰减
机译: 多层网络中基于GMPLS的多层链路管理的方法和装置