————————————————————————————————————————————————有向动态网络中基于模体演化的链路预测方法
作者杜凡，刘群
机构重庆邮电大学计算智能重庆市重点实验室
DOI 10.3969/j.issn.1001-3695.2017.11.0738
基金项目国家自然科学基金资助资助（61572091，61075019）；重庆市自然科学基金资助项目（CSTC2014jcyjA40047）；重庆市教委研究项目（KJ1400403）；重庆邮电大学博士启动资助项
目（A2014-20）
预排期卷《计算机应用研究》2019年第36卷第5期
摘要以往传统的链路预测方法大多数针对无向网络，而实际上大多数社交网络是有向的，并且没有考虑网络中同一节点对之间的重复边以及微观演化信息，因此不能较好地解决有向动态网
络中的链路预测问题。针对有向网络，将节点对之间的重复边信息转换为该节点对之间连边
的权值；接着采用了基于三元组模体的演化模型，对滑动窗口中相邻时间片的模体转换概率
进行统计后，采用指数加权滑动平均法对其进行时序分析得到不同模体转换概率的预测矩
阵，进而使用该矩阵对网络中的链边进行预测。这不仅充分利用了网络微观演化信息，而且
解决了动态网络中重复边的问题。最后对实验结果进行分析发现，在高全局聚类系数高平均
度的网络中AUC相比Triad Transition Matrix方法提高了近0.01，而相比Common Neighbor
方法提高更多。因此，所提方法能够较好地应用网络微观演化信息进行链路预测。
关键词时序链路预测；有向网络；模体演化；时序分析
作者简介杜凡（1991-），男，硕士研究生，主要研究方向为复杂网络?链路预测（280928338@https://www.doczj.com/doc/3f6362298.html,）；
刘群（1969-），女，教授，硕士，主要研究方向为复杂网络?人工智能．
中图分类号TP181
访问地址https://www.doczj.com/doc/3f6362298.html,/article/02-2019-05-010.html
投稿日期2017年11月9日
修回日期2018年1月5日
有向动态网络中基于模体演化的链路预测方法————————————————————————————————————————————————发布日期2018年4月18日
引用格式杜凡, 刘群. 有向动态网络中基于模体演化的链路预测方法[J/OL]. 2019, 36(5). [2018-04-18].
https://www.doczj.com/doc/3f6362298.html,/article/02-2019-05-010.html.
第36卷第5期 计算机应用研究
V ol. 36 No. 5 优先出版
Application Research of Computers
Online Publication
——————————
收稿日期：2017-11-09；修回日期：2018-01-05 基金项目：国家自然科学基金资助资助（61572091，61075019）；重庆市自然科学基金资助项目（CSTC2014jcyjA40047）；重庆市教委研究项目（KJ1400403）；重庆邮电大学博士启动资助项目（A2014-20）
作者简介：杜凡，男（1991-），硕士研究生，主要研究方向为复杂网络?链路预测（280928338@https://www.doczj.com/doc/3f6362298.html, ）；刘群，女（1969-），教授，硕士，主要研究方向为复杂网络?人工智能．
有向动态网络中基于模体演化的链路预测方法 *
杜 凡，刘 群
(重庆邮电大学 计算智能重庆市重点实验室, 重庆 400065)
摘 要：以往传统的链路预测方法大多数针对无向网络，而实际上大多数社交网络是有向的，并且没有考虑网络中同一节点对之间的重复边以及微观演化信息，因此不能较好地解决有向动态网络中的链路预测问题。针对有向网络，将节点对之间的重复边信息转换为该节点对之间连边的权值；接着采用了基于三元组模体的演化模型，对滑动窗口中相邻时间片的模体转换概率进行统计后，采用指数加权滑动平均法对其进行时序分析得到不同模体转换概率的预测矩阵，进而使用该矩阵对网络中的链边进行预测。这不仅充分利用了网络微观演化信息，而且解决了动态网络中重复边的问题。最后对实验结果进行分析发现，在高全局聚类系数高平均度的网络中AUC 相比Triad Transition Matrix 方法提高了近0.01，而相比Common Neighbor 方法提高更多。因此，所提方法能够较好地应用网络微观演化信息进行链路预测。 关键词：时序链路预测；有向网络；模体演化；时序分析 中图分类号：TP181 doi: 10.3969/j.issn.1001-3695.2017.11.0738
Link prediction method based on motif evolution in directed dynamic networks
Du Fan, Liu Qun
(Chongqing Key Laboratory of Computational Intelligence , Chongqing University of Posts & Telecommunication , Chongqing 400065, China )
Abstract: In the past, most of the traditional link prediction methods are oriented to the undirected network, in fact, most social networks are directional, and do not consider the duplication between the same node pair and the microscopic evolution information in the network, therefore they can not solve Link prediction in directed dynamic networks better. This paper focused on the directional network, the repeated edge information between the pair of nodes is transformed into the weight of the edge between the pair of nodes, then used the evolution model based on the triad motif, calculate the motif transformation probability matrix between the adjacent time slice in the move window, the probability matrix be analyzed by exponentially weighted moving average, and then it used the matrix to predict the chain edge in the network. This method not only makes full use of the network micro evolution information, but also solves the problem of overlapping edges in dynamic network. Experiments show that this method can get better results than Common Neighbor, Triad Transition Matrix and other methods in network with high Global Clustering Coefficient and high Average Degree ．Therefore, this method can apply the network microscopic information to the link prediction better.
Key words: time series link prediction; directed network; motif evolution; time series analysis
0 引言
链路预测作为复杂网络研究中的一个重要且有趣的问题，
本质上是从网络链路的微观层面解释网络结构生成的原因，进而帮助人们更好地理解网络所对应的复杂系统的结构生成和演化规律。其在计算机领域已有较深入的研究，但是其中大多数是针对静态网络，而时序链路预测方法可以利用网络的历史信息推测网络中将会产生的边。
在研究与生产环境中，链路预测有非常多的用途。例如，在生物蛋白质互助网络研究中，为降低成本，可以用链路预测算法的结果指导实验，从而降低实验成本。链路预测也可以在社交网络中用来推断两个用户之间有多大可能成为好友，从而进行推荐。另外在文献[1]所提出的对网络中错误连边的预测，对网络重构和结构功能优化也有重要的应用价值。例如对某一机场网络数据进行重建，网络中可能会有些自相矛盾的数据，链路预测就可能对其进行纠正。链路预测在复杂网络理论研究
方面同样具有巨大价值，它可以帮助人们认识复杂网络演化的机制，每一种网络演化机制里可能蕴涵着一种精确的链路预测方法，而每一种优秀的链路预测方法，也可能揭示了一种网络演化机制[2]。
目前比较成熟的静态链路预测方法有基于相似性的链路预测方法，如CN(common neighbor)、Salton、Jaccard、AA（adamic adar）指标等。文献[3]提出了一种基于蚁群算法的链路预测方法。此外，还有基于最大似然估计的层次结构模型以及随机分块模型。文献[4]提出了一种基于随机分块模型的方法进行链路预测。文献[5]将边的存在与否看成边的一种属性，将链路预测问题转变为边的属性预测问题。文献[6]对复杂网络的链路可预测性问题进行了探讨，并提出了一种基于高阶路径的链路预测算法。文献[7]针对无法获取属性标签的异质网络，提出了一种包含三层图模型的学习和推理算法。针对异质网络，文献[8]还提出了一种基于节点度、共同邻居以及Katz三种指标的复合指标，去预测科学家合作网络的新的关系的形成。
以上方法虽然在静态网络中能取得较好的结果，它们都没有将网络的历史演化纳入考虑范围，但是现实世界中的网络大多是随时间变化的，为此，也有大量文献从网络演化的角度去进行研究。文献[9]对网络动态演化进行了量化研究。文献[10]将时序网络按时间窗口分片；然后对每个时间窗口内的网络图进行静态链路预测；最后将预测结果看做一个时间序列，并对其进行时间序列分析。文献[10]分别比较了MA（moving average）、Av（average）、RW（random walk）、LR（linear regression）等几种时间序列预测模型，发现LR预测模型总体上优于其他几种模型。文献[11]提出了一种进化算法对网络中的拓扑特征和属性特征进行整合，以提高链路预测精度。文献[12]考虑链路预测面临正负样本不均衡的问题，提出了一种基于半监督学习的链路预测方法。文献[13]对一个时间片的网络图做静态链路预测后，与其后一时间片的网络图做比较，并计算出每次链路预测的误差值，最后对误差序列做时序分析，得到最终的预测误差，用其来修正最终链路预测结果，以提高链路预测精度。文献[14]提出一种整合网络的时序信息、社区结构以及节点中心性的动态网络链路预测算法。文献[15]使用基于相似性与随机游走的方法进行链路预测。文献[16]提出了一个多维时序的模型，其在vector auto-regression(VAR)模型的基础上，在时序模型中结合拓扑矩阵，并与时间演化预测链接同时进行，可以用来预测重复的链接的发生就像预测新的链接一样。
上述这些方法各有优劣，但是都没有考虑到网络中的微观结构对网络演化的影响。模体(motif)是非常重要的一种网络微观结构，网络模体演化作为网络微观演化的一种，是网络演化分析的重要组成部分。文献[17]研究表明，网络模体的演化规律可以很大程度地揭示网络结构特征的变化。文献[18]提出了一种基于网络中的模体富集信息的聚类方法，在秀丽隐杆线虫神经元网络上应用该方法发现了由20个神经元组成的聚类，该聚类展示了瞬眼调节器被调控的一种途径。文献[19]挖掘三元组模体的转换概率信息得到三元组转换概率矩阵（TTM矩阵）进行链路预测，并且取得了较好的结果。文献[20]在文献[19]的基础上，用三阶张量分解的方法计算三元组转换概率矩阵，并且在进行链路预测时考虑三元组的重要性指标。因此，结合网络模体演化对边的连接进行预测是一个可行的方向。
但是文献[19]的方法没有做充分的时序分析，而文献[20]所提方法没有考虑到网络中可能存在的重复边问题，并且该方法对无向图进行研究，而现实中的社交网络数据大多是有向图，如facebook评论墙网络或者wiki的提问回答网络，必定是由一个用户到另一个用户。为了充分利用网络微观演化信息，并且考虑网络中重复边，本文对有向动态网络进行研究，提出MELP(motif evolution link prediction)算法进行链路预测，使用指数滑动平均的方法计算三元组转换概率矩阵，并考虑网络中边的权重与局部的结构信息。在facebook网络中，本文方法较TTM方法在时间窗口宽度为20时其AUC有0.01的提升，但是较CN方法有近0.7的提升。在mathoverflow网络中本文方法AUC也有提升，但是没有在facebook网络中显著，经分析主要是因为算法对不同拓扑结构的网络的适应性不同。
1 相关概念
1.1 问题描述
本文所解决问题可做如下描述：随时间变化的有向带权无环网络G=(g1,g2,g3,…g T)由T个时间片组成，每一个快照包含时序网络中相同时间间隔内的信息。已知时间片g1到时间片g t 的拓扑结构，本文需要解决的就是，给出一种链路预测方法，为时间片g t+1中的任意有序节点对赋予一个分数值，该分数值越大，则表示两节点之间越有可能产生连边。
1.2 模体理论
模体(motif)，也就是网络的基本子结构，最初在生物学里表示蛋白质网络中最基本的功能模块，这一概念也可以应用在复杂网络中。三元组是网络中最简单的模体，由三个节点组成。对于有向图，可以用16种三元组模体[21]进行表示，如图1所示，图中标注的ID与名称有唯一性，在本文的其他章节将会用到。
图116种三元组模体
这些不同的模体在网络的演化中有着重要的作用，本文所提方法的主要思想是利用各三元组模体之间的转换概率来进行链路预测。
对于一个网络中的任意由三个点组成的节点集，可以称为一个三元组模体m ，m 必定为图1中所示的16中模体类型之一，即为mtf i 的一个实例(mtf i 表示第i 类三元组模体)。网络的演化过程可以看做模体的不断转换。对于三个相互之间没有连边的节点(a,b,c)若在演化过程中，产生一条边e(a,b)，这个过程可表示为
003012mtf mtf →
即三元组(a,b,c)由模体类型003转换为模体类型012。在此
基础上，就可以描述网络的所有演化。本文对网络中所有模体类型的转换作统计，并计算各模体类型之间转换的概率P[mtf i ->mtf j ](即为模体类型i 转换为模体类型j 的概率)，这个概率可以看做目标网络的一个演化特征。
例如，对于图1中的模体021D 与模体030T ，通过模体转换概率计算方法经过对其在某一网络中的历史数据进行统计，发现模体021D 到030T 的转换概率非常高。那么对于该网络中t 时刻一个模体为021D 的三元组，可以知道其在t+1时刻，转换为030T 的概率就会非常高，而从图1可知，由021D 到030T 需要生成一条边，那么就可以依据上述方法预测这条新连接边出现的可能性较大。 1.3 指数加权滑动平均法
指数加权滑动平均法 (exponentially weighted moving average) [22]是一种时间序列预测方法。滑动平均法 (moving average) [23]主要思想是依据一个时间序列未来可能出现的值序列与较近时期的历史观测值序列具有一定的相关性关系，进而通过取与预测期相邻的几个历史观测数据的数值平均值作为未来时间序列的预测值，得到预测结果。例如，假设数值时间序列X=(x 1,x 2,…x t )，需要预测t+1时刻的值，公式如下：
()()111
1t t t n MA t x x x n
--++=
++?+ (1)
其中：(1)MA t +表示t+1时刻的预测平均值。
指数加权滑动平均法是滑动平均法的改进，它既有滑动平均法的优点，又减少了数据的存储量。对于上述序列X ，使用指数加权平均法计算t+1时刻的预测平均值的公式如下：
(1)(1)()t EWMA t x EWMA t αα+=+-
(2) 其中：(1)EWMA t +为t+1时刻的预测平均值；()EWMA t 为t 时刻的预测平均值；t x 为t 时刻的实际值；α为平滑系数。 1.4 连边权值
动态社交网络往往含有重复边，而本文将两节点间重复边的多少看做其关系的强弱程度。某条边重复出现的次数越多，那么这条边所代表的关系越强，所以算法开始前，可以对数据进行如下预处理：对于网络中的重复边e 1,e 2…e n ，只保留第一次出现的边e 1，并将该边所出现的次数n 作为边e 1的权值h ，这个权值就代表着两点之间的联系的强弱程度。
2 算法设计
2.1 模体转换概率
本文主要研究基于模体演化的有向动态网络的链路预测问题，提出了一种链路预测的MELP 算法。该算法在TTM [19]算法的基础上，采用指数加权滑动平均法进行时序预测，并且考虑了网络中的重复边信息。
本算法首先对数据集按照某一时间跨度划分为T 个时间片，然后对相邻两时间片之间的三元组模体进行统计，并计算模体
转换概率。从图1可以看出，三元组模体类型总共有16种，因此本文定义一个16×16的矩阵来描述相邻时刻不同三元组模体类型的转换概率称为模体转换概率矩阵MTM(motif transition matrix)，该矩阵行标和列标分别对应16种三元组模体，其中的元素表示该时刻行标对应模体转换到列标对应模体的概率，该值为
,,[][)](1t i j i j m P mtf t mtf t =→+
(3)
其中：[]i mtf t 表示t 时刻第i 类三元组模体；,,t i j m 表示从t 时刻到t+1时刻第i 类三元组模体转换到第j 类三元组模体的概率，即为对应时刻MTM 矩阵第i 行第j 列的元素。转换概率矩阵计算的算法描述如算法1所示。
算法1 转换概率矩阵计算
输入：t+1时刻的图\ G, t 时刻的图preG 。 输出：16×16的转换概率矩阵MTM 。 1 初始化MTM ；
2 for EACH v in G do
3 vnbrs = get_neighbors(v)； //vnbrs 包含与节点v 相邻的所有节点
4 for EACH u in vnbrs if u <= v then begin
5 neighbors = vnbrs | get_neighbors(u) – {u, v}；//neighbors 包含与节点u,v 相邻的所有节点
6 if 边(v, u)与(u, v)同时存在于图G
7 统计模体102到102，012到102及003到102的转换数量； 8 elseif
9 统计模体012到012及003到012的转换数量； 10 endif
11 for each w in neighbors if u < w or (v < w < u and v
not in get_neighbors(w)) then begin//get_neighbors(w)表示与w 相邻的所有节点 12
[]t i mtf = get_triads_name(preG, v, u, w)；
//get_triads_name(preG,v,u,w)获取前一时间段的图preG 中(v,u,w)所组成的三元组的模体名称 13
[]t 1j mtf + = get_triads_name(G, v, u, w)；
//get_triads_name(G,v,u,w)获取当前时间段的图G 中(v,u,w)所组成的三元组的模体名称
14 MTM[[]t i mtf ][[]t 1j mtf +] += 1；
15 end 16 end 17 end
18 将MTM 矩阵每个元素除以该元素所在行的元素之和得到最终的转换概率矩阵MTM
应用算法1得到所有相邻时间片之间的转换概率矩阵，依次为MTM 1，MTM 2，…，MTM T-1，如图2所示。
本文定义一个三元组模体转换概率预测矩阵PMTM ，矩阵中元素值为
,,,(s )p i j i j m EWMA =
(4)
其中：,(s )i j EWMA 表示对时间序列,s i j 作指数加权滑动平均预测。依次取矩阵第i 行第j 列的值组成时间序列：
,1,,2,,1,,s (,,,)i j i j i j T i j m m m -=?
(5)
2.2 连边分数计算
经过时间序列分析后得到三元组模体转换概率预测矩阵PMTM 。对于训练集为(T 1,T 2,…T ΔT )，测试集为T ΔT+1的情况。PMTM 可以理解为通过对历史信息进行时间序列分析得到网络的ΔT 时刻到ΔT+1时刻的三元组模体转换概率矩阵的预测值。
一个节点对(v,u)，有可能属于多个三元组模体。如图3所示，节点对(v,u)可以属于三元组(v,u,1),(v,u,2)，也可以属于(v,u,3)等，本文中只考虑与v 或u 相邻的节点集{1,2,3,4,5}中的元素与(v,u)所组成的三元组模体，而不考虑其他与v 和u 不相邻的点，如6、7两点。
对于一个三元组(v,u,3)，在v 与u 未连边之前该三元组模
体属于图1中的第6个模体，称之为021C 。如果该节点对产生连边(v,u)，则该三元组模体转换为图1中的第9个模体，命名为030T ；如果产生连边(u,v)，则转换为图1中的第10个模体，称之为030C ；如果两个方向的连边同时出现则转换为图1中的第14个模体，称之为120C 。
由于在计算节点对连边分数时，对连边分数产生影响的每一个三元组内的边具有不同的权值，而权值代表着这条边的重要程度，所以每个三元组对连边具有不同的影响力。因此，根据权值来定义连边影响因子。
(
,,,,edge v u v u w i
S =
∑
(6)
(),,edge v u w 其中：为三元组(v,u,w)内的所有边的集合；i
h 为边i 的权值。连边影响因子越大，说明该三元组对节点对连边贡献越大。由此，将式（6）代入式（7），可以根据矩阵PMTM 计算得到ΔT+1时刻每个节点对的连边分数值：
()()
[],,,1v,u ,nbors v u v u w T T w
score S PMTM N N ??+=
?∑
(7)
其中：T N ?为T ?时刻三元组(v,u,w)的模体名；1T N ?+为1T ?+时刻三元组(v,u,w)的模体名；(,)nbors v u 为节点v,u 的邻居节点集。
3 实验数据
本文采用四个社交网络数据集对算法进行分析，这些社交
网络通过对象间的互动均构成了有向网络，而且包含两节点间连边时间序列信息，所以是动态的有向网络。本文将选择一部分边作为训练集，一部分作为测试集，然后采用链路预测方法对测试集中的边进行预测，以验证本文所提方法的有效性。Facebook-wall [24]数据集是Facebook 在美国新奥尔良地区长达1561天的用户留言版记录，该数据集包含三个属性，分别表示留言者、被留言者与以UNIX 时间戳的形式保存的留言时间；sx-askubuntu [25]数据集是askubuntu 网站用户关于ubuntu 的问答数据，时间跨度为2 613天，包含三个属性，分别是回答者、提问者以及UNIX 时间戳形式表示的回答时间；sx-mathoverflow [26]数据集是Math Overflow 网站的用户问答数据，时间跨度为2 350天，该数据集所包含的属性与上一数据集基本一致。数据具体参数如表1所示。表中动态边数是包含重复边的数据集中的所有边数，而静态边数是指除去所有重复的边后数据集中所包含的边数。
图2 转换概率矩阵预测
2,i,j
T-1,i,j
MTM
图3 一个节点对，可能属于多个三元组模体
表1 实验数据参数 Facebook-wall
Sx-askubuntu Sx-mathoverflow
节点数 45813 159316 24818 动态边数
876993 964437 506550 静态边数 264004 596933 239978 时间跨度
1561day
2613day
2350day
4 实验
4.1 实验设计
为测试算法可行性，本文在上述数据集上进行实验。实验程序采用Python 编写，运行环境为64位Win10系统。
为了全面验证本文所提方法的有效性，本节在上述三个实际数据集上对CN 、TTM [11]以及本文所提出的MELP 算法进行对比。由于AUC(area under the receiver operating characteristic curve)是从整体上衡量算法的精确度，它实际上是指ROC(receiver operating characteristic)曲线下的面积。在实际计算中，可以采用抽样比较的方法得到近似值，即每次从测试集中随机选取一条边，再从不存在的边集合中随机选择一条。如果前者分数值大于后者就加1分，如果两者分数值相等就加0.5分，所以，它也可以理解为在测试集中的分数值有比随机选择的一个不存在的边的分数值高的概率。大多数时序链路预测相关的文献中都采用AUC 作为评价指标，因此本文实验中也采用AUC 值作为算法评价指标。在计算AUC 值时，采用滑动窗口的方法确定训练集与测试集：先将数据按时间间隔分片；然后确定时间窗口ΔT ，选取时间片T 1至T ΔT 为训练集，T ΔT+1为测试集，并计算AUC ；之后将测试集与训练集依次后移一个时间片，再次进行AUC 计算；最终可以得到一个AUC 序列，该序列长度为n-ΔT ，n 为时间片数量。 4.2 实验结果及分析
下面先将时间窗口宽度设置为30。图4为facebook 数据集AUC 计算结果。可以看到MELP 算法在facebook 数据集的表现明显优于另外两种算法。而在mathoverflow 数据集上MELP 算法的表现只略优于TTM 算法，如图5所示。而在ubuntu 数据集上(图6)，MELP 算法的表现并不如TTM 算法但还是大大优于CN 。
为了更加全面地了解本文算法的优劣，了解不同时间窗口宽度下本文算法的表现，下面的实验分别取时间窗口宽度为20和45，如图7～12所示。
图4 facebook 数据集时间窗口为30时AUC 计算结果
图5 mathoverflow 数据集时间窗口为30时AUC 计算结果
图6 ubuntu 数据集时间窗口为30时AUC 计算结果
图7 facebook 数据集时间窗口为20时AUC 计算结果
图8 mathoverflow 数据集时间窗口为20时AUC 计算结果
为了更直观地看到结果，将通过滑动窗口计算得到的AUC 序列取平均值，如表2所示。
从表中可看到，MELP 算法在facebook 与mathoverflow 数据集中都取得了更好的结果；而在ubuntu 数据集中，只有在时间窗口宽度为20的情况下MELP 算法才优与另外两种算法，
所以整体来看，MELP 算法比CN 与TTM 更有效。
另外，从表2中可以发现，mathoverflow 与ubuntu 两个数据集在所有的算法下，时间窗口宽度越大，最后结果越好。在facebook 数据集中，时间窗口宽度为45时反而结果最差，而从图4与7可以看出，滑动窗口移动到靠近中间位置时AUC 值
最大。可以看出，随着窗口的滑动，窗口中包含的数据并不是稳定地有利于预测结果，当时间窗口过大时，每一个窗口中包含了过多不利于链路预测结果的数据，导致最终结果较差。而从图5、6、8、9、11以及图12可看出，对mathoverflow 与ubuntu 两个数据集进行链路预测的得到的AUC 结果较为稳定，所以时间窗口宽度越大，窗口中包含越多有利于预测的信息，
最后结果就越好。
接下来从网络拓扑结构的角度来分析为什么会出现上述实验结果。考虑网络的全局聚类系数(global clustering coefficient ，GCC)以及平均度(average degree ，AD)这两个指标。
GCC closed
closed open
tri tri tri =
+
(8)
2AD e n
= (9)
其中：closed tri 是网络中闭合三角的个数；open tri 是网络中开三角的个数。对于有向网络，从图1可以看到，4、5、6、7、8、11号三元组模体是开三角，而9、10、12、13、14、15、16号三
元组模体是闭合三角。
本文对每一个滑动窗口计算数据集的GCC 与AD ，并对其取平均值，得到表3。
从表3中可以很明显地看出，结果表现最好的facebook 数据集在三个时间窗口大小下都具有最大的GCC 与AD ，而表现
最差的ubuntu 数据集在三个时间窗口大小下都具有最小的GCC 与AD ，由此可知，本文所提出算法在具有高全局聚类系数和高平均度的网络中可以得到更好的效果。
图9 ubuntu 数据集时间窗口为20时AUC 计算结果
图10 facebook 数据集时间窗口为45时AUC 计算结果
图11 mathoverflow 数据集时间窗口为45时AUC 计算结果
图12 ubuntu 数据集时间窗口为45时AUC 计算结果
表2 AUC 平均值
data sets
time window
CN
TTM
MELP
20
0.63466013986 0.690242992424 0.700255128205 30 0.656097608696 0.709551391304 0.71752626087 45
0.642511057692 0.675863671875 0.680392307692 mathoverflow
20 0.601575749674 0.856372881356 0.859170143416 30 0.622039673469 0.870864612245 0.873813510204 45 0.645514819005 0.882094025735 0.88521979638 ubuntu 20
0.524827315542 0.666780548469
0.667061067504 30 0.526036153846 0.681565 0.679561410256 45
0.531397596154
0.705387630208
0.702055128205
4.3 算法时间复杂度分析
本文提出的算法可分为两个主要部分：一是三元组模体转换概率矩阵计算，二是节点间连边分数的计算。假设网络的最大度为d，网络节点数为n，则模体转换概率矩阵计算时间复杂度为O(n*d2)。对于节点连边分数计算，在最坏情况下为O(2d)，即为O(d)。TTM方法所用的三元组模体检测方法为遍历检测其时间复杂度为O(n3)，在节点连边分数计算上，时间复杂度与本算法一致，因此，总体来说本文方法较优。
5 结束语
时序链路预测与网络演化关系密切，将网络的微观演化规律应用到链路预测可以取得较好的结果。并且大多数链路预测方法是基于无向图的，而社交网络中某种关系的发生往往是有方向性的，基于这种关系形成的社交网络是有向网络。因此本文将动态有向网络中的三元组模体的演化应用于链路预测中，提出一种基于三元组模体演化的链路预测方法，并通过实验分析了时间窗口对实验结果的影响。
通过实验可以看出，使用动态网络中的模体转换信息来进行链路预测是可行的，并且可以得到较好的结果。在facebook 数据集中，本文所提算法取得了明显的优势。可以证明，指数加权滑动平均法，用于对模体转换矩阵进行时间序列分析时，可以提高预测结果。在facebook网络中，本文方法较TTM方法在时间窗口宽度为20时其AUC有0.01的提升，但是较CN 方法有近0.7的提升；在mathoverflow网络中本方法AUC也有提升，但是没有在facebook网络中显著；在ubuntu数据集中本文所提算法并没有得出更优的结果。通过对网络结构属性的分析，可以知道本算法在具有高聚类系数高平均度的网络中表现更好。在未来的工作中，本文将会进一步分析网络结构特点对算法表现的影响，将社区理论应用到本算法中，以期提高本算法在低全局聚类系数低平均度网络中的表现。此外，在以后的工作中，仍需深入分析三元组演化规律，将其与社交网络的基础理论(如三元闭包理论)相结合。最后，本文方法仍需进一步降低时间复杂度，并且在更多数据集上测试算法的有效性。参考文献：
[1]Guimerà R, Sales-Pardo M. Missing and spurious interactions and the
reconstruction of complex networks [J]. Proceedings of the National Academy of Sciences, 2009, 106 (52): 22073-22078.
[2]Dorogovtsev S N, Mendes J F F. Evolution of networks [J]. Advances in
Physics, 2002, 51 (4): 1079-1187.
[3]Chen B, Chen L. A link prediction algorithm based on ant colony
optimization [J]. Applied Intelligence, 2014, 41 (3): 694-708.
[4]Guimerà R, Sales-Pardo M. Missing and spurious interactions and the
reconstruction of complex networks [J]. Proceedings of the National Academy of Sciences, 2009, 106 (52): 22073-22078.
[5]Taskar B, Wong M F, Abbeel P, et al. Link prediction in relational data [C]//
Advances in Neural Information Processing Systems. 2004: 659-666. [6]Xu Xiaoke, Xu Shuang, Zhu Y X, et al.Link predictability in complex
networks [J]. Complex Systems & Complexity Science, 2014, 11 (1): 41-47.
[7]Kuo T T, Yan R, Huang Y Y, et al.Unsupervised link prediction using
aggregative statistics on heterogeneous social networks [C]// Proc of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2013: 775-783.
[8]Str?Ele V, Zimbr?O G, Souza J M. Group and link analysis of multi-
relational scientific social networks [J]. Journal of Systems and Software, 2013, 86 (7): 1819-1830.
[9]Michalski R, Bródka P, Kazienko P, et al.Quantifying social network
dynamics [C]// Proc of the 4th International Conference on Computational Aspects of Social Networks. 2012: 69-74.
[10]Soares P R D S, Prudêncio R B C. Time series based link prediction [C]//
Proc of International Joint Conference on Neural Networks. 2012: 1-7. [11]Bliss C A, Frank M R, Danforth C M, et al. An evolutionary algorithm
approach to linkprediction in dynamic social networks [J]. Journal of Computational Science, 2014, 5 (5): 750-764.
[12]Zeng Z, Chen K J, Zhang S, et al. A link prediction approach using semi-
supervised learning in dynamic networks [C]// Proc of the 6th International Conference on Advanced Computational Intelligence. 2013: 276-280. [13]Deng Z H, Lao S Y, Bai L. A temporal link prediction method based on link
prediction error correction [J]. Journal of Electronics & Information Technology, 2014, 36 (2): 325-331.
[14]Ibrahim N M, Chen L. Link prediction in dynamic social networks by
integrating different types of information [J]. Applied Intelligence, 2015, 42
(4): 738-750.
[15]Ahmed N M, Chen L, Wang Y, et al.Sampling-based algorithm for link
prediction in temporal networks [J]. Information Sciences, 2016, 374: 1-14.
[16]?zcan A, ??üdücü ? G. Multivariate temporal Link Prediction in evolving
social networks [C]// Proc of IEEE//ACIS International Conference on Computer and Information Science. 2015: 185-190.
[17]Juszczyszyn K, Musia? K, Kazienko P, et al.Temporal changes in local
表3网络特征
Time Window Data Sets Global Clustering
Coefficient
Average degree
facebook0.028965 3.586067 20mathoverflow 0.009112 1.767520
ubuntu0.002469 1.001330
facebook0.032154 5.386659 30mathoverflow 0.009959 2.625603
ubuntu0.002199 1.529206
facebook0.0311458.451428 45mathoverflow 0.011126 3.936553
ubuntu0.002078 2.280627
topology of an email-based social network [J]. Computing and Informatics, 2012, 28 (6): 763-779.
[18]Benson A R, Gleich D F, Leskovec J. Higher-order organization of complex
networks [J]. Science, 2016, 353 (6295): 163.
[19]Juszczyszyn K, Musia? K, Budka M. Link prediction based on subgraph
evolution in dynamic social networks [C]// Proc of the 3rd IEEE International Conference on Privacy, Security, Risk and Trust. 2011: 27-34.
[20]Wang S H, Yu H T, Huang R Y, et al. A temporal link prediction method
based on motif evolution [J]. Acta Automatica Sinica, 2016, 42 (5): 735-745.
[21]Batagelj V, Mrvar A. A subquadratic triad census algorithm for large sparse
networks with small maximum degree [J]. Social networks, 2001, 23 (3): 237-243.
[22]Makridakis S G, Wheelwright S C. Forecasting methods for management
[M]. [S. l. ] : Wiley, 1985.
[23]Lawless J F, McLeish D L. Testing for unit roots in autoregressive-moving
average models of unknown order [J]. Biometrika, 1984, 71 (3): 599-607.
[24]http://socialnetworks. mpi-sws. org/data-wosn2009. html [EB/OL].
[25]http://snap. stanford. edu/data/sx-askubuntu. html [EB/OL].
[26]http://snap. stanford. edu/data/sx-mathoverflow. html [EB/OL].
一异构网络的融合技术发展现状 近年来，人们已就异构网络融合问题相继提出了不同的解决方案BRAIN提出了WLAN与通用移动通信系统(UMTS)融合的开放体系结构；DRiVE项目研究了蜂窝网和广播网的融合问题；WINEGLASS则从用户的角度研究了WLAN与UMTS的融合；MOBYDICK重点探讨了在IPv6网络体系下的移动网络和WLAN的融合问题；MONASIDRE首次定义了用于异构网络管理的模块。虽然这些项目提出了不同网络融合的思路和方法，但与多种异构网络的融合的目标仍相距甚远。最近提出的环境感知网络和无线网状网络，为多种异构网络融合的实现提供了更为广阔的研究空间。 通信技术近些年来得到了迅猛发展，层出不穷的无线通信系统为用户提供了异构的网络环境，包括无线个域网(如Bluetooth)、无线局域网(如Wi-Fi)、无线城域网(如WiMAX)、公众移动通信网(如2G、3G)、卫星网络，以及Ad Hoc网络、无线传感器网络等。尽管这些无线网络为用户提供了多种多样的通信方式、接入手段和无处不在的接入服务，但是，要实现真正意义的自组织、自适应，并且实现具有端到端服务质量(QoS)保证的服务，还需要充分利用不同网络间的互补特性，实现异构无线网络技术的有机融合。 异构网络融合是下一代网络发展的必然趋势。在异构网络融合架构下，一个必须要考虑并解决的关键问题是：如何使任何用户在任何时间任何地点都能获得具有QoS保证的服务。异构环境下具备QoS保证的关键技术研究无论是对于最优化异构网络的资源，还是对于接入网络之间协同工作方式的设计，都是非常必要的，已成为异构网络融合的一个重要研究方面。目前的研究主要集中在呼叫接入控制(CAC)、垂直切换、异构资源分配和网络选择等资源管理算法方面。传统移动通信网络的资源管理算法已经被广泛地研究并取得了丰硕的成果，但是在异构网络融合系统中的资源管理由于各网络的异构性、用户的移动性、资源和用户需求的多样性和不确定性，给该课题的研究带来了极大的挑战。 二异构网络融合中的信息安全问题 如同所有的通信网络和计算机网络，信息安全问题同样是无线异构网络发展过程中所必须关注的一个重要问题。异构网络融合了各自网络的优点，也必然会将相应缺点带进融合网络中。异构网络除存在原有各自网络所固有的安全需求外，还将面临一系列新的安全问题，如网间安全、安全协议的无缝衔接、以及提供多样化的新业务带来的新的安全需求等。构建高柔性免受攻击的无线异构网络安全防护的新型模型、关键安全技术和方法，是无线异构网络发展过程中所必须关注的一个重要问题。 虽然传统的GSM网络、无线局域网(WLAN)以及Adhoc网络的安全已获得了极大的关注，并在实践中得到应用，然而异构网络安全问题的研究目前则刚刚起步。下一代公众移动网络环境下，研究无线异构网络中的安全路由协议、接入认证技术、入侵检测技术、加解密技术、节点间协作通信等安全技术等，以提高无线异构网络的安全保障能力。 1 Adhoc网络的安全解决方案 众所周知，由于Ad hoc网络本身固有的特性，如开放性介质、动态拓扑、分布式合作
————————————————————————————————————————————————有向动态网络中基于模体演化的链路预测方法 作者杜凡，刘群 机构重庆邮电大学计算智能重庆市重点实验室 DOI 10.3969/j.issn.1001-3695.2017.11.0738 基金项目国家自然科学基金资助资助（61572091，61075019）；重庆市自然科学基金资助项目（CSTC2014jcyjA40047）；重庆市教委研究项目（KJ1400403）；重庆邮电大学博士启动资助项 目（A2014-20） 预排期卷《计算机应用研究》2019年第36卷第5期 摘要以往传统的链路预测方法大多数针对无向网络，而实际上大多数社交网络是有向的，并且没有考虑网络中同一节点对之间的重复边以及微观演化信息，因此不能较好地解决有向动态网 络中的链路预测问题。针对有向网络，将节点对之间的重复边信息转换为该节点对之间连边 的权值；接着采用了基于三元组模体的演化模型，对滑动窗口中相邻时间片的模体转换概率 进行统计后，采用指数加权滑动平均法对其进行时序分析得到不同模体转换概率的预测矩 阵，进而使用该矩阵对网络中的链边进行预测。这不仅充分利用了网络微观演化信息，而且 解决了动态网络中重复边的问题。最后对实验结果进行分析发现，在高全局聚类系数高平均 度的网络中AUC相比Triad Transition Matrix方法提高了近0.01，而相比Common Neighbor 方法提高更多。因此，所提方法能够较好地应用网络微观演化信息进行链路预测。 关键词时序链路预测；有向网络；模体演化；时序分析 作者简介杜凡（1991-），男，硕士研究生，主要研究方向为复杂网络?链路预测（280928338@https://www.doczj.com/doc/3f6362298.html,）； 刘群（1969-），女，教授，硕士，主要研究方向为复杂网络?人工智能． 中图分类号TP181 访问地址https://www.doczj.com/doc/3f6362298.html,/article/02-2019-05-010.html 投稿日期2017年11月9日 修回日期2018年1月5日
网络布线测试中的三个关键步骤 步骤1：通断测试是基础 通断测试是测试的基础，是对线路施工的一种最基本的检测。虽然此时只测试线缆的通断和线缆的打线要领能不能正确，但这个步骤不能少。可以运用能手测试仪执行测试。通常这是给布线施工工人运用的一般性线缆检测工具。 步骤2：认证测试最关键 当线缆布线施工完毕后，须要对全部电缆系统执行认证测试。此时要根据国际标准，例如TSB67、ISO11801等，对线缆系统执行彻底测试，以保证所安装的电缆系统符合所设计的标准，如超5类标准、6类标准、超6类标准等。这个流程须要测试各种电气参数，最后要给出每一条链路即每条线缆的测试报告。测试报告中包括了测试的时间、地点、操作人员姓名、运用的标准、测试的结果。测试的参数也很多，比如：WareMap打线图、长度、衰减、近端串扰、衰减串扰比、回波损耗、传输时延、时延偏离、综合近端串扰、远端串扰、等效远端串扰等参数。 每一个参数都代表不同的意思，各个参数之间又不是独立的，而是相互影响的，如果某个参数不符合规范，须要分析原由，然后对模块、配线架、水晶头的打法执行相应的调整或者重新压接。如果用的是假冒伪劣的线缆或者模块，造成很多指标不通过，甚至须要重新敷设线缆，这个工作量是可想而知的。有些时候，即使有能力投入资金和人力，想换线也未必能够换得了，因为工程有很多工序是不可逆的，比如对于更换石膏板吊顶内的线缆是非常困难的。因此，建议大家从公司声誉出发，为公司的验收和售后服务减少不必要的麻烦，多多运用品牌产品，拒绝假冒伪劣。比如，安普、西蒙、康普等国际知名布线品牌都是很好的选择。 测试报告可以根据须要打印成中文。福禄克公司的DSP100/2000/4000都可以执行不同级别线缆的认证测试。 步骤3：抽查测试不可少 施工完毕，须要由第三方对综合布线系统执行抽测，比如质量检测部门。抽测是必不可少的，而且要收取相应的抽测费用，地域间可能存在差别，但基本上是一个信息点要收50元检测费。综合布线系统抽测的比例通常为10％至20％。 在执行测试的流程中，可能出现的疑问主要有如下情况。
一异构网络得融合技术发展现状 近年来,人们已就异构网络融合问题相继提出了不同得解决方案BRAIN提出了ＷLAＮ与通用移动通信系统（UMTS）融合得开放体系结构;DRiＶE项目研究了蜂窝网与广播网得融合问题；ＷＩNＥGLＡＳS则从用户得角度研究了WＬＡＮ与UＭTS得融合;MOBYＤＩＣK重点探讨了在IPv６网络体系下得移动网络与ＷLＡN 得融合问题;MONＡＳIDRE首次定义了用于异构网络管理得模块.虽然这些项目提出了不同网络融合得思路与方法,但与多种异构网络得融合得目标仍相距甚远。最近提出得环境感知网络与无线网状网络，为多种异构网络融合得实现提供了更为广阔得研究空间。 通信技术近些年来得到了迅猛发展,层出不穷得无线通信系统为用户提供了异构得网络环境，包括无线个域网（如Ｂｌｕeｔooth）、无线局域网(如Wi-Fi)、无线城域网(如WiMAX)、公众移动通信网(如2Ｇ、３Ｇ）、卫星网络，以及Ad H ｏc网络、无线传感器网络等。尽管这些无线网络为用户提供了多种多样得通信方式、接入手段与无处不在得接入服务，但就是，要实现真正意义得自组织、自适应,并且实现具有端到端服务质量（ＱoＳ)保证得服务，还需要充分利用不同网络间得互补特性，实现异构无线网络技术得有机融合。 异构网络融合就是下一代网络发展得必然趋势.在异构网络融合架构下,一个必须要考虑并解决得关键问题就是：如何使任何用户在任何时间任何地点都能获得具有QoＳ保证得服务.异构环境下具备ＱoS保证得关键技术研究无论就是对于最优化异构网络得资源，还就是对于接入网络之间协同工作方式得设计，都就是非常必要得,已成为异构网络融合得一个重要研究方面.目前得研究主要集中在呼叫接入控制(CAＣ)、垂直切换、异构资源分配与网络选择等资源管理算法方面。传统移动通信网络得资源管理算法已经被广泛地研究并取得了丰硕得成果,但就是在异构网络融合系统中得资源管理由于各网络得异构性、用户得移动性、资源与用户需求得多样性与不确定性，给该课题得研究带来了极大得挑战。 二异构网络融合中得信息安全问题 如同所有得通信网络与计算机网络,信息安全问题同样就是无线异构网络发展过程中所必须关注得一个重要问题。异构网络融合了各自网络得优点,也必然会将相应缺点带进融合网络中。异构网络除存在原有各自网络所固有得安全需求外,还将面临一系列新得安全问题,如网间安全、安全协议得无缝衔接、以及提供多样化得新业务带来得新得安全需求等.构建高柔性免受攻击得无线异构网络安全防护得新型模型、关键安全技术与方法，就是无线异构网络发展过程中所必须关注得一个重要问题。 虽然传统得ＧＳM网络、无线局域网(ＷLAＮ）以及Adhoc网络得安全已获得了极大得关注，并在实践中得到应用，然而异构网络安全问题得研究目前则刚刚起步。下一代公众移动网络环境下，研究无线异构网络中得安全路由协议、接入认证技术、入侵检测技术、加解密技术、节点间协作通信等安全技术等，以提高无线异构网络得安全保障能力。 1 Adｈoc网络得安全解决方案 众所周知,由于Ad hoc网络本身固有得特性,如开放性介质、动态拓扑、分布式合作以及
复杂网络中关键节点查找和链路预测应用研究随着网络科学的不断发展和信息数据的不断扩充,网络规模日益增大,大规模网络数据的研究也逐渐成为研究热潮。鉴于表示学习算法对大规模网络研究的优势,关键节点分类以及链路预测等基于网络知识的传统研究内容开始结合知识表示学习算法进行探索研究,并取得显著成果。本文结合网络科学知识和表示学习算法提出关键蛋白质分类和基于Probase知识库的链路预测两种算法框架。首先,本文提出了一种结合生物信息知识的关键蛋白质分类的方法。在关键节点搜索的相关研究中,很多实验已经证明结合多源信息的方法比仅考虑单一知识的方法更加有效。而现有的搜索方法并没有充分的考虑网络本身蕴含的知识,使得很多关键信息被丢失。本文提出的关键蛋白质分类方法则是结合STRING数据库中体现的PPI网络中蛋白质节点的生物信息,同时结合表示学习算法提取网络中蛋白质节点的拓扑结构特征和生物信息特征,实现关键蛋白质节点的分类。通过实验对比分析,本文提出的关键蛋白质分类算法的准确率、召回率及F1值均高于其对比实验,这表明表示学习算法在网络关键节点识别任务中具有一定的优势。其次,本文提出了基于Probase知识库的链路预测方法。链路预测即通过分析网络结构以及节点属性,探索网络中相似的节点,进一步预测与已知节点具有潜在连边的节点。本文提出的链路预测方法主要结合网络嵌入的表示学习算法将网络进行向量化表示,并基于相似度的计算方法确定节点之间的相似程度,实现网络的链路预测。通过统计预测结果的top-k命中率、计算预测节点与给
定节点的相似性和统计最短路径长度来验证算法的有效性和稳定性,从而证明表示学习算法对链路预测任务有很好的提升作用。综上,本文利用多源信息并结合表示学习算法可以有效的提升网络中关键蛋白质节点分类的准确率。同时利用表示学习算法将网络进行向量化表示,借助相似度计算方法来计算节点的相似性,完成链路预测,可以提高预测的命中率,保证预测的稳定性。
第20卷第1期管理科学学报V〇L20N〇.1 2017 年 1月J O U R N A L O F M A N A G E M E N T S C I E N C E S IN C H I N A Jan. 2017 基于决策分析的社交网络链路预测方法? 李永立\罗鹏2，张书瑞3 (1.东北大学工商管理学院，沈阳110169; 2.哈尔滨工业大学管理学院，哈尔滨150001; 3.东北大学信息科学与工程学院，沈阳110169) 摘要：社交网络是社会媒体信息传播的骨架，对其进行链路预测的研究将有助于社会媒体平 台上的信息管理和舆论控制.在既有网络链路预测方法研究的基础上，以决策分析的思想为出 发点，提出了引入效用函数分析的社交网络链路预测方法；针对效用函数中参数的估计问题，进一步提出了允许一定误差度的马尔科夫链蒙特卡洛参数校准方法，并对方法的正确性进行 理论上的论证.在收集到的5个腾讯Q Q群的数据集上，进行了新方法的验证研究，并与既有 的链路预测方法在准确性方面进行了比较分析.研究表明：本文提出的预测方法考虑了链路形 成的微观行为基础，具有较好的预测准确性，并且参数估计算法中“允许误差”的引入有助于 模型应用者在模型效率和准确性方面的折衷中做出合理的决策. 关键词：链路预测；决策分析；效用函数；马尔科夫链蒙特卡洛方法；社交网络；数据分析 中图分类号：TP391; N949 文献标识码：A文章编号：1007 -9807(2017)01 -0064 -11 〇引言 网络构成了社会与经济生活的骨架，大到全 球视角的贸易网络，小到一个单位的人际网络，都 是“网络”这一组织形式在现实生活中的具体体 现.特别是随着社会媒体平台的高速发展，人们曰 常联系的方式变得更加多样，新兴的微信、微博、腾讯Q Q等联系方式层出不穷，由此形成的社交 网络的规模也呈现超速发展的态势，成为信息管 理领域一个热点的研究方向[1_3].在这一研究背 景下，本文将重点研究如下的问题:“在分析社交 网络既有链接形成规律的基础上，如何预测潜在 的链接，进而为研究社交网络形成和演化的规律 奠定微观基础 本文的研究问题属于网络链路预测的研究领 域.具体地说，网络链路预测是通过分析网络现有 的链接规律，从而探究和预测网络未知或潜在的链接.网络链路预测作为网络研究领域较为热门 的研究方向之一，已经有了深厚的研究基础，较为 早期的综述可以参见LU等[4]发表在Physica A上 的文献.本文进一步从研究方法的角度，X t该领域 既有的研究进行一个简单的概述:一方面便于文 章的整体性和可读性，另一方面为进一步的对比 研究提供方法的索引.本文将既有的网络链路预 测方法分为了三类，分别为“基于节点相似性的 链路预测”、“基于最大似然估计的链路预测”和 “基于概率模型的链路预测其中，（1) “基于节 点相似性的链路预测”以两个节点之间相似性越 大，它们之间存在链接的可能性就越大为研究前 提，从度量节点相似性的角度出发进行网络链路 预测的研究;代表性的研究有“基于局部信息相 似性指标的链路预测方法”[5<，“基于全局相似 性指标的链路预测方法〇9]，以及“基于局部- 全局相似性指标的链路预测方法”. (2) “基 ①收稿日期：2015 -05 -17;修订日期：2016 -02-05. 基金项目：国家自然科学基金资助项目（71501034);中国博士后科学基金项目（2016M590230);辽宁省财政科研基金项目（16C024). 作者简介：李永立（1985—），男，辽宁沈阳人，副教授，硕士生导师，Em ail:ylli@https://www.doczj.com/doc/3f6362298.html,
复杂网络链路预测的研究现状及展望 吕琳媛 前言：做链路预测这个方向有一年多的时间了，有一些收获和体会。一直想写一个综述进行总结，总是希望这个综述尽可能的包括更多更全面的信息，但是新的思想和结果源源不断的涌现，所谓的综述也就无限期的搁置了下来。前不久刚刚和伟平合作发表了一篇关于利用网络局部随机游走进行链路预测的文章，借此文发表之动力，总结一下链路预测这个方向的研究进展以及展望。希望该文能对那些正奋战在这个方向上和希望在此领域有所建树的科研工作者有所帮助和启迪。 （本文中所提到的具体的技术方法以及实验结果将在另一篇中文综述中详细介绍。） 1．链路预测及其研究意义 网络中的链路预测(Link Prediction)是指如何通过已知的网络节点以及网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的可能性[1]。这种预测既包含了对未知链接（exist yet unknown links）的预测也包含了对未来链接（future links）的预测。该问题的研究在理论和应用两个方面都具有重要的意义和价值。 近年来，随着网络科学的快速发展，其理论上的成果为链路预测搭建了一个研究的平台，使得链路预测的研究与网络的结构与演化紧密联系起来。因此，对于预测的结果更能够从理论的角度进行解释。这也是我们相比计算机专业的人研究链路预测的优势所在。与此同时，链路预测的研究也可以从理论上帮助我们认识复杂网络演化的机制。针对同一个或者同一类网络，很多模型都提供了可能的网络演化机制[2, 3]。由于刻画网络结构特征的统计量非常多，很难比较不同的机制孰优孰劣。链路预测机制有望为演化网络提供一个简单统一且较为公平的比较平台，从而大大推动复杂网络演化模型的理论研究。另外，如何刻画网络中节点的相似性也是一个重大的理论问题[4]，这个问题和网络聚类等应用息息相关[5]。类似地，相似性的度量指标数不胜数，只有能够快速准确地评估某种相似性定义是否能够很好刻画一个给定网络节点间的关系，才能进一步研究网络特征对相似性指标选择的影响。在这个方面，链路预测可以起到核心技术的作用。链路预测问题本身也带来了有趣且有重要价值的理论问题，也就是通过构造网络系综并藉此利用最大似然估计的方法进行链路预测的可能性和可行性研究。这方面的研究对于链路预测本身以及复杂网络研究的理论基础的建立和完善，可以起到推动和借鉴的作用。 链路预测研究不仅具有如上所述的理论价值，其更重要的意义还是体现在应用方面。很多生物网络，例如蛋白质相互作用网络和新陈代谢网络，节点之间是否存在链接，或者说是否存在相互作用关系，是需要通过大量实验结果进行推断的。我们已知的实验结果仅仅揭示了巨大网络的冰山一角。仅以蛋白质相互作用网络为例，酵母菌蛋白质之间80%的相互作用不为我们所知[6]，而对于人类自身，我们知道的仅有可怜的0.3%[7,8]。由于揭示这类网络中隐而未现的链接需要耗费高额的实验成本。那么如果能够事先在已知网络结构的基础上设计出足够精确的链路预测算法，再利用预测的结果指导试验，就有可能提高实验的成功率从而降低试验成本并加快揭开这类网络真实面目的步伐！实际上，社会网络分析中也会遇到数据不全的问题，这时候链路预测同样可以作为准确分析社会网络结构的有力的辅助工具[9,10]。除了帮助分析数据缺失的网络，链路预测算法还可以用于分析演化网络，即对未来
xx武船网络测试方案 测试原则 一种好的测量方法不仅可以有效监视网络性能、找出网络瓶颈，将性能测量引起的流量降为最低，而且在故障发生时能迅速分离出故障点。理想情况下，一种测量方法应满足以下原则： 不需要额外的结构。尽可能的利用已有的网络拓扑，避免单纯为了测量而重新构造一套新的基础设施。 避免重复测量。尽可能充分的利用测量的结果，避免由于测量而引起网络资源过多的消耗。由测量引起的流量不应对网络原有的服务造成冲击，引起网络性能的下降，否则将与网络管理及性能测量的初衷相违背。 简便。在能满足上述各原则的前提下，测量方法还应尽可能的简便。尽量使用已有的测量工具，使用得到广泛支持的和充分实现的协议。例如：ICMP协议在几乎各种主机和路由器上都得到支持，因此使用ping工具来测量往返xx和丢包率就是十分简便的方法。尽管ping的方法所测得的数据有一定的局限性，其性能和其他TCP、UDP或其他IP协议有一定的出入（一般，路由器给ICMP协议的优先性较低），但考虑ping工具及ICMP协议实现的普遍性，利用ping工具测量全网的性能，尤其在测量端到端性能的时候，是最普遍的做法。 网络测试 网络设备测试 网络设备测试主要是对网络设备的运行情况、设备参数进行测试，验证网络设备参数的正确，网络运行的稳定。 测试对象：核心交换机（S12508）、汇聚交换机（S7503E）、接入交换机（S5120/S3100）。 核心交换机 基本测试
测试目的：查看交换机的硬件和IOS的配置情况 测试平台：PC机从交换机console口接入或工作站远程登录到交换机测试内容： 设备信息 1. QW-FLHX-1交换机 2. QW-FLHX-2交换机 汇聚交换机 基本测试 测试目的：查看交换机的硬件和IOS的配置情况 测试平台：PC机从交换机console口接入或工作站远程登录到交换机测试内容： 设备信息 1. QW-FLHJ-1交换机 2. QW-FLHJ-2交换机 S5120接入交换机 基本测试 测试目的：查看交换机的硬件和IOS的配置情况 测试平台：PC机从交换机console口接入或工作站远程登录到交换机测试内容： 设备信息 1. QW-FL6-4
光纤布线系统安装完成之后需要对链路传输特性进行测试，其中最主要的几个测试项目是链路的衰减特性、连接器的插入损耗、回波损耗等。 一、组网： 用户采用4台S5500作为接入交换机、1台S5500作为核心交换机组网，4台接入交换机分别在三个仓库以及门卫处与核心机房都是通过2根八芯单模光纤走地井连接，在这5个机房再通过跳纤来连接到交换上。用户要求实现内网的用户主机访问公共服务器资源，并实现全网互通。 二、问题描述： PC现无法访问server服务器，进一步发现S5500光纤端口灯不亮，端口信息显示down状态。在核心交换机端通过自环测试发现该端口以及光模块正常，接入交换机端也同样测试发现正常。监控网络正常使用，再将网络接口转接到监控主干链路上，发现网络同样无法正常使用。 三、过程分析： 想要恢复链路，首先要排查出故障点，根据故障点情况结合实际恢复链路通畅。在这里主要分析光纤通路，光信号从接入交换机光口出来通过跳线，转接到主干光纤，然后再通过核心跳线转接到核心交换上。由于该链路不通，首先要排除两端接口以及光模块问题，这里使用自环检测(如果是超远距离传输光纤线缆需要接光衰然后在自环，防止
烧坏光模块)。当检测完成发现无问题，再测试接入端的光纤跳纤：如果是多模光纤可以将一端接到多模光纤模块的tx口，检测对端是否有光；单模光纤如果没有光功率计可以使用光电笔检测(该方法只能检测出中间无断路，并不能检测出线路光衰较大的情况)。最后再检测主线路部分，检测方式同跳线一样。 四、解决方法： 从上述的分析可以看出，只要保证了光信号一出一收两条路径都能正常就可以解决用户无法访问服务器的问题。为了保证光路正常通路，最好的解决方法就是，通过使用光功率计来检测对端发射光在本端的光功率是否在光口可接受范围内。由于用户组网使用了一些监控设备来接入该主干光缆，并且该光路现正常使用，通过将网络光纤转接到该监控主干光缆，发现网络光路仍然不通；并且两端端口自环检测正常。由此可以判断出主要问题在两端的跳纤上。 五、说明及注意事项： 1、光纤的连接需要注意以下几点：(1)光纤接口有没有插紧完全对接上；(2)光纤接口端面是否受灰尘等污染；(3)光纤中间是否存在物理损坏，部分损伤或者断开；(4)光纤弯曲是否半径小于8cm。 光纤网络的测试测量设备 1、光纤识别器 它是一个很灵敏的光电探测器。当你将一根光纤弯曲时，有些光会从纤芯中辐射出来。这些光就会被光纤识别器检测到，技术人员根据这
DOI : 10.11992/tis.201810025网络出版地址: https://www.doczj.com/doc/3f6362298.html,/kcms/detail/23.1538.TP.20190109.1748.006.html 融合朴素贝叶斯方法的复杂网络链路预测 王润芳1，陈增强1,2，刘忠信1,2 （1. 南开大学 人工智能学院，天津 300350; 2. 天津市智能机器人重点实验室，天津 300350） 摘 要：近来复杂网络成为了众多学者的研究热点。但真实网络中的连边信息并不完整，不利于网络的分析研究，链路预测可以挖掘网络中的缺失连边，为网络重构提供基本依据。本文认为网络中链接的产生不仅受外部因素——共同邻居的影响，还受其自身因素的影响。其中，共同邻居的影响可以通过文献中的局部朴素贝叶斯(LNB)模型量化，节点的影响则根据其自身的度量化。本文将两者综合考虑，提出了融合朴素贝叶斯(SNB)模型，然后用共同邻居(CN)、Adamic-Adar(AA)和资源分配(RA)指标进行推广。在美国航空网(USAir)上的实验结果表明，该方法的预测准确度比LNB 和基准方法均有所提高，从而证明了该方法的有效性。 关键词：复杂网络；融合朴素贝叶斯模型；局部朴素贝叶斯模型；贝叶斯模型；链路预测；共同邻居；节点度；网络重构 中图分类号：TP391 文献标志码：A 文章编号：1673?4785(2019)01?0099?09 中文引用格式：王润芳, 陈增强, 刘忠信. 融合朴素贝叶斯方法的复杂网络链路预测[J]. 智能系统学报, 2019, 14(1): 99–107.英文引用格式：WANG Runfang, CHEN Zengqiang, LIU Zhongxin. Link prediction in complex networks with syncretic naive Bayes methods[J]. CAAI transactions on intelligent systems, 2019, 14(1): 99–107. Link prediction in complex networks with syncretic naive Bayes methods WANG Runfang 1，CHEN Zengqiang 1,2，LIU Zhongxin 1,2 (1. College of Artificial Intelligence, Nankai University, Tianjin 300350, China; 2. Key Laboratory of Intelligent Robotics of Tianjin,Tianjin 300350, China) Abstract : Recently, complex networks have become a research hotspot. However, edge information in the real network is incomplete, which is not conducive to the analysis and research of the network. Link prediction can provide a funda-mental basis for network reconstruction by digging out the missing edges in the network. This paper demonstrates that the generation of links in the network is not only influenced by external factors (common neighbors) but also by its own factors. Among them, the influence of common neighbors can be quantified via the local naive Bayes (LNB) model in the literature, whereas the influence of nodes can be quantified depending on their degree. Therefore, a syncretic naive Bayes (SNB) model is proposed based on comprehensive consideration of the influence of the two abovementioned as-pects. The model is then extended to common neighbors, Adamic-Adar, and Resource Allocation methods. Finally, the experimental results on USAir show that the prediction accuracy of the method is higher than that of LNB and the benchmark method, which proves the effectiveness of the SNB model. Keywords : complex network; syncretic naive Bayes model; local naive Bayes model; Bayes model; link prediction;common neighbors; the degree of node; network reconstruction 现代社会中的信息呈爆炸式增长，使得社会 系统极具复杂性。研究表明，各种系统之间的交 互信息可以通过对应的复杂网络表示，其中，网络中的节点代表系统中的个体，连边代表个体之间的关系[1]。网络科学是专门用于研究各种复杂网络系统的定性和定量规律的一门交叉学科[2]。然而，由于隐私政策和个体设置等原因，实际获收稿日期：2018?10?23. 网络出版日期：2019?01?10. 基金项目：国家自然科学基金项目(61573199, 61573197). 天津 市自然科学基金项目(14JCYBJC18700). 通信作者：陈增强. E-mail: chenzq@https://www.doczj.com/doc/3f6362298.html, .第 14 卷第 1 期 智 能 系 统 学 报Vol.14 No.12019 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2019
万方数据
万方数据
万方数据
基于时间序列分析的网络流量预测模型研究 作者：周德懋， 李舟军， 康荣雷， ZHOU Demao， LI Zhoujun， KANG Ronglei 作者单位：北京航空航天大学,计算机学院,北京,100191 刊名： 现代电子技术 英文刊名：MODERN ELECTRONICS TECHNIQUE 年，卷(期)：2009,32(8) 被引用次数：2次 参考文献(17条) 1.Garrett M W;Wilhinger W Analysis,Modeling and Generation of Self-similar VBR Video Traffic 1994 2.Chen Borsen;Yang Yusuarg;Botekuen Lee Fuzzy Adaptive Predictive Flow Control of Network Traffic[外文期刊] 2003(04) 3.刘嘉琨;金志刚;薛飞基于FARIMA过程的网络业务预报与应用[期刊论文]-电子与信息学报 2001(04) 4.Chen Liang;Wang Xiaofan;Han Zhengzhi Controlling Bifurcation and Chaos in Internet Congestion Control Model 2004(05) 5.Joachim H;Werner L Lyapunov Exponents from a Time Series of Acausic Chaos 1989(04) 6.文兰动力系统简介[期刊论文]-数学进展 2002(04) 7.文成林;周东华多尺度估计理论及其应用 2002 8.杨福生小波变换的工程分析与应用 1999 9.雷霆;余镇危一种网络流量预测的小波神经网络模型[期刊论文]-计算机应用 2006(03) 10.陈振伟;郭拯危小波神经网络预测模型的仿真实现[期刊论文]-计算机仿真 2008(06) 11.文成林;周东华多尺度估计理论及其应用 2002 12.张传斌;王学孝;邓正隆非线性时间序列的RBF神经网络预测方法及其应用[期刊论文]-热能动力工程 2001(03) 13.张玉瑞;陈剑波基于RBF神经网络的时间序列预测[期刊论文]-计算机工程与应用 2005(11) 14.林天峰基于最大熵原理的网络流量预测综合模型[期刊论文]-微电子学与计算机 2006(08) 15.郭琳;张大方;黎文伟基于稳态模型的流异常检测算法[期刊论文]-计算机工程 2006(19) 16.余健;郭平基于改进小波神经网络的网络流量预测研究[期刊论文]-计算机应用 2007(12) 17.郑成兴网络流量预测方法和实际预测分析[期刊论文]-计算机工程与应用 2006(23) 本文读者也读过(10条) 1.潘乔.罗辛.王高丽.裴昌幸.PAN Qiao.LUO Xin.WANG Gao-li.PEI Chang-xing基于FARIMA模型的流量抽样测量方法[期刊论文]-计算机工程2010,36(15) 2.李林峰.裘正定时间序列分析在网络流量预测中的应用研究[会议论文]- 3.赵海阔.朱正平.ZHAO Hai-kuo.ZHU Zheng-ping基于非线性算法的网络业务流量预测[期刊论文]-自动化与仪器仪表2010(4) 4.何建基于时间序列的网络流量分析与预测[期刊论文]-中国科技信息2005,2(22) 5.段智彬.孙恩昌.张延华.董燕.DUAN Zhi-bin.SUN En-chang.ZHANG Yan-hua.DONG Yan基于ARMA模型的网络流量预测[期刊论文]-中国电子科学研究院学报2009,4(4) 6.闵洁.李潇.MIN Jie.LI Xiao基于最小二乘支持向量机的网络流量预测[期刊论文]-九江学院学报（自然科学版）2010,25(1) 7.韩志杰.王汝传.段晓阳.HAN Zhi-jie.WANG Ru-chuan.DUAN Xiao-yang一种基于小波卡尔曼滤波的MPLS流量预测算法[期刊论文]-计算机技术与发展2010,20(11)
一异构网络 异构网络(Heterogeneous Network）是一种类型的网络，其是由不同制造商生产的计算机，网络设备和系统组成的，大部分情况下运行在不同的协议上支持不同的功能或应用。 所谓异构是指两个或以上的无线通信系统采用了不同的接入技术，或者是采用相同的无线接入技术但属于不同的无线运营商。利用现有的多种无线通信系统，通过系统间融合的方式，使多系统之间取长补短是满足未来移动通信业务需求一种有效手段，能够综合发挥各自的优势。由于现有的各种无线接入系统在很多区域内都是重叠覆盖的，所以可以将这些相互重叠的不同类型的无线接入系统智能地结合在一起，利用多模终端智能化的接入手段，使多种不同类型的网络共同为用户提供随时随地的无线接入，从而构成了异构无线网络。 异构网络融合是下一代网络发展的必然趋势。下一代无线网络是异构无线网络融合的重要原因是：基于异构网络融合，可以根据用户的特点（例如车载用户）、业务特点（例如实时性要求高）和网络的特点，来为用户选择合适的网络，提供更好的QoS。一般来说，广域网覆盖范围大，但是数据传输速率低，而局域网正好相反。因此在实际应用中，多模终端可以根据自身的业务特点和移动性，来选择合适的网络接入。与以往的同构网络不同，在异构网络环境下，用户可以选择服务代价小，同时又能满足自身需求的网络进行接入。这是由于这些异构网络之间具有互补的特点，才使异构网路的融合显得非常重要。因此一些组织提出了不同的网络融合标准，这些组织有3GPP（The 3rd Generation Partnership Project）、MIH（The IEEE 802.21 Media Independent Handover working group）和ETSI（The European Telecommunications Standards Institute）。 通信技术近些年来得到了迅猛发展，层出不穷的无线通信系统为用户提供了异构的网络环境，包括无线个域网(如Bluetooth)、无线局域网(如Wi-Fi)、无线城域网(如WiMAX)、公众移动通信网(如2G、3G、4G、5G)、卫星网络，以及Ad Hoc网络、无线传感器网络等。尽管这些无线网络为用户提供了多种多样的
复杂网络论文：复杂网络链路预测节点相似度指数弱连接【中文摘要】自然界和人类社会中广泛存在着各种各样的复杂系统,而复杂系统可通过复杂网络来描述。复杂网络的研究将极大地促进复杂系统的研究与发展,对理解复杂系统的结构与功能具有重要的意义。近年来,复杂网络的研究正渗透到从物理学到生物学的众多不同学科,对复杂网络的定性特征与定量规律的深入探索、科学理解以及可能的应用,已经成为复杂系统或复杂性科学研究中一项极其重要的挑战性课题。链路预测是复杂网络中的一个新兴的研究方向,是指利用已知的网络节点和网络结构等信息预测网络中存在但尚未发现的未知链接和不存在但可能形成的未来链接。近年来,链路预测因其重要的理论价值和潜在的应用前景而广受关注,成为了复杂网络研究领域的研究热点之一。目前,链路预测的研究主要集中在无向无权网络,关于有向或加权网络的链路预测问题的研究较少。本论文以无向无权网络的链路预测算法为基础,分别发展了有向网络的链路预测算法和加权网络的链路预测改进算法。本论文共分四章,第一章简单介绍了复杂网络中链路预测及其研究意义。第二章回顾了无向无权网络中链路预测的研究进展。在第三章中,我们首先将12种针对无向网络的链路预测算法拓展有向网络的情况,建立起了基于局域连接信息的有向链路预测算法的基本框架。然后,基于有向网络模体的统计分析,我们构造了一种广义的共有邻居指数,同时也提出了一种两指数共同预测的结合指数。在10个真实有向网络中,我们对基于这些指数所建立的16种链路预测算法进行了测试和分析,得到了一些对实际应用
有一定指导意义的结论。特别地,归因于高的预测精度和低的计算复杂度,广义共有邻居指数和结合指数将有望在实际的链路信息挖掘中得到应用。在第四章,我们提出了一种适于加权网络链路预测的改进算法,在几个真实的加权网络中进行了测试,分析了强、弱链接对预测精度的影响,发现弱链接在实现链路的高精度预测方面具有比强链接更重要的作用。最后,我们对论文进行了总结,并对将来可能的研究方向进行了展望。 【英文摘要】Complex networks provide a qualitative description for various complex systemswhich exist extensively in nature and human society. The research of complex networksvastly boost the study of complex systems and is of great significance for understandingrelations between their structure and function. Recently, the research of complexnetworks is extended to a number of disciplines from physics to biology and others. Thedeeper analysis of the qualititative and quantitative characteristics of complexnetworks,accumulation of scientific knowledge and the mining of their potentialapplications are becoming an important and challenging subject for the research ofcomplex systems and complex science.As a new research direction of complex networks, link prediction is to predict themissing links which exist yet not been found and the future links which
Abstract With the continuous development of artificial intelligence technology,online Internet technology has accelerated the popularity of social networking applications.The network contains a huge amount of data,it also contains valuable data information and network topology features,including personal information and individual individuals.Relationship is an important part of social networks.However,how to find useful information in massive data and predict implicit links in the network has become an important research topic.Therefore, information analysis for social networks has become a hot topic.The main task of link prediction is to predict the future possible links through existing links in the current network. The link prediction problem in social networks has great practical application value and attracts more and more researchers'attention and research. Due to the existing link prediction algorithm,there is a problem that the link weight is single,and it cannot be applied to a complex type of heterogeneous social network.Therefore, in this paper,based on heterogeneous social networks with weighted types,the concept of node weights is introduced into the link weighting process between users and users on the basis of constructing the heterogeneous network structure,which quantifies the time impact of users on the location signing behavior.At the same time,the location and user links,as well as the location and location links are weighted.Finally,a mixed weighted link prediction algorithm for heterogeneous social networks based on user location is proposed.In addition, according to the user's behavioral relationship to location access,the user's preference for location check-in behavior is regarded as a latent property,and the user-user link is weighted by bias,and an offset-weighted user link algorithm is proposed. Finally,this paper selects the real data set and conducts experiments and analysis on mixed weighted link prediction algorithm and biased weighted user link algorithm in heterogeneous networks.The results show that the mixed weighted link prediction algorithm for heterogeneous social networks based on user location has obvious prediction effect,and the biased user link algorithm has obvious prediction effect in the case of sparse data. Key words:social network,heterogeneous,link prediction,weighting