复杂网络随着信息技术的发展不断被应用到各个领域,而对复杂网络的研究通常需要对其进行建模和简化.Han等人在EDBT 2009和SIGMOD 2010会议上提出一种新的复杂网络表现形式,即信息网络(information network).信息网络属于复杂网络范畴,是对现实空间中海量、多维、复杂结构和问题更具一般性的抽象^{[1, 2]}.信息网络一般都有动态的演化过程,网络中的节点和边随着时间不断改变,这里统称为动态信息网络.传统复杂网络研究多将复杂系统建模为静态网络,在揭示社交网络、生物网络等复杂系统的性质与特征等方面都已取得重要成果.而在现实世界中,几乎所有的网络结构是随时间不断变化的,社交网络^{[3, 4]}、科研合作者网络^[5]、蛋白质网络^[6]等都是动态信息网络的实例.动态网络是当前复杂网络领域中极具挑战的新问题,其动态的演化过程具有时序、复杂、多变的特点,蕴含着丰富的潜在信息和商业价值.

结构^[7]是网络的基本特征,分析动态信息网络结构的演化过程,对全面认识复杂系统的行为倾向具有重要意义.针对网络结构的表示问题,KDD 2012会议上的文献[8]首次提出用潜在的角色(role)来刻画节点的结构行为.角色代表网络结构的某种类型,结构类型相似的节点属于同一种角色,如中心节点、边缘节点等.动态网络的结构预测是网络演化分析的重要问题,它旨在利用历史网络信息预测未来时刻节点的拓扑结构,帮助人们提前进行预警和决策.例如:生物学家需要预测分子网络的拓扑结构何时发生变化,因为细胞分子的结构与生物体的生长状况息息相关;在商品销售网络中,挖掘未来可能成为关键节点的用户可以实现广告的精准投放;而针对通信网络,通过预测通信网络节点的重要性来优化网络资源的均衡分配, 是网络管理人员的迫切需求.

动态网络的结构演化分析的目的是挖掘网络随时间演化的特点,由于网络结构本身比较复杂,难以表示和量化,动态网络时序、多变的演化过程更增加了分析的难度.目前,动态网络研究还处于起步阶段,Rossi等人以角色为基础进行了一系列动态网络演化分析相关的研究^[9-11],是本文研究工作的基础.文献[9]提出一种基于自学习方法挖掘动态网络角色的混合模型DBMM(dynamic behavioral mixed-membership model);文献[10]在DBMM模型的基础上分析了网络整体角色随时间的动态变化情况,提出角色演化的几种特点.然而,以上模型并未针对动态网络的特点给出角色匹配以及角色解释的方法,因此可解释性不强.WSDM 2013会议的文献[11]进一步将上述模型进行扩展,应用模型进行未来时刻网络角色的预测,其思想是将动态网络的多种角色视为网络的多个状态,通过计算网络在相邻时刻的状态转移矩阵来进行角色演化的分析与预测.但是,由于该方法的转移矩阵模型只由相邻两个时刻的网络数据得到,忽略了历史时间因素对角色演化的影响,因此效果并不理想.

为解决以上问题,本文使用角色来量化动态网络的结构,以得到的动态网络角色模型为基础,为网络结构预测问题提供了新思路.主要贡献如下:

(1) 提出动态网络的角色模型.使用角色来表示动态网络的结构,将静态网络的角色发现方法扩展至动态网络,用相对简单的角色序列来量化复杂的结构演化,得到动态网络角色模型;对得到的模型进行分析,给出角色匹配与角色解释的方法.

(2) 提出了基于多目标回归思想的动态网络角色预测方法MTR-RP(multi-target regression based role prediction).以历史网络数据作为训练数据构建模型,预测未来时刻网络可能的角色分布情况.该方法不仅克服了已有基于转移矩阵方法忽略时间因素的不足,还考虑了多个预测目标之间可能存在的依赖关系.

1 动态网络的角色模型

为解决动态网络进行结构演化分析的问题,本文将角色引入动态网络场景,提出适合网络结构演化分析的动态网络角色模型.根据动态网络的演化特点,将静态网络的角色发现方法扩展至动态网络,通过将复杂的网络结构量化为相对简单的角色分布,减小直接分析网络结构演化的难度.

1.1 用角色建模动态网络

在用角色建模动态网络之前,首先要构建动态网络.动态网络的定义如下.

定义 1(动态网络). D=＜N,E＞表示一个动态网络,N=＜N₁,N₂,…,N_T＞为节点集合,E=＜E₁,E₂,…,E_T＞为边集合.将D看做一个时间有序的子图序列D=＜S₁,S₂,…,S_T＞,其中,S_t=＜N_t,E_t＞是动态网络D在t时刻的子图快照,N_t为S_t的节点集合,E_t为S_t的边集合,T为动态网络长度.本文研究网络的结构演化,故只考虑无向网络.

将动态网络表示为有序的子图序列后,可以对每个时刻的网络快照分别进行角色发现,即:将每个子网络都转化为节点的角色信息,然后根据节点在各个时刻的角色分布情况分析节点结构的演化过程.本文使用KDD 2012会议的RloX方法进^[8]行角色发现,包括特征提取和角色发现.图 1给出了对动态网络进行角色建模的基本框架.本文将节点的角色看成一种软概率分布,所有角色共同表示节点的结构,从节点的视角刻画每个节点在网络所表现出的结构身份.

1.1.1 角色模型的框架

(1) 特征提取

特征提取旨在尽可能多地为每个节点提取表示结构的特征,力求用一个高维的特征取值向量来保存节点完整的拓扑结构.采用ReFex^[12]的迭代特征产生方法,为每个节点提取基本特征和递归特征,基本特征指节点局部结构的特征,如节点的度、自网络包含的边数、参与三角形的个数等;得到节点的基本特征后,使用聚集函数递归地对其邻居节点的基本特征进行聚集计算得到递归特征,此过程由节点的一阶邻居开始,按照逐层扩散的方式向外围蔓延,将得到的新特征与已有的特征进行对比,若新特征与已有特征相差不大,认为不再有新特征产生并将其抛弃,终止递归^[12].以图 2的网络为例,使用度、自网络包含的边数、参与三角形的个数作为3个基本特征,使用sum和mean两种聚集函数来产生递归特征,为每个节点计算特征取值.如对节点n₁,可得n₁的基本特征向量为＜f₁,f₂,f₃＞=＜5,7,2＞.接着计算递归特征,直到没有新特征产生终止.

定义 2(节点-特征矩阵序列V=＜V₁,V₂,…,V_T＞). 给定动态网络子图序列D=＜S₁,S₂,…,S_T＞,对S_t进行特征提取得到节点的特征矩阵${{V}_{t}}\in {{\Re }^{N\times {{f}_{t}}}},$其中,N为网络的节点个数,f_t表示t时刻得到的特征个数.对每个网络快照D=＜S₁,S₂,…,S_T＞分别进行特征提取,得到节点-特征矩阵序列V=＜V₁,V₂,…,V_T＞.

(2) 角色发现

根据节点的特征矩阵进一步进行角色发现,NMF(non-negative matrix factorization)是一种解决高维非负矩阵分解的有效方法,对特征矩阵${{V}_{t}}\in {{\Re }^{N\times {{f}_{t}}}}$,给定一个正整数r<<min(N,f_t),NMF可以寻找非负矩阵G_t∈ℜ^N×r及$F\in {{\Re }^{r\times {{f}_{t}}}}$满足G_tFV_t,使得下面的函数值最小.

$f({{G}_{t}},F)=\frac{1}{2}||{{V}_{t}}-{{G}_{t}}F||_{F}^{2}$

(1)

其中,$||\cdot ||_{F}^{2}$表示矩阵F范数的平方,分解目标G_t便是节点的角色矩阵.

G_t是一个N行r列的矩阵,每一行表示该节点在各个角色上的概率取值情况,称G_t为节点的角色矩阵.G_t的每个元素g_t(i,j)均为正实数,表示节点i属于角色j的概率.以中心节点、桥梁节点以及边缘节点这3种网络结构为例,有r=3的第n行为节点n在t时刻的角色分布,例如{R₁:0.1,R₂:0.1,R₃:0.8}.本文对G_t进行了行归一化处理,即:

$\forall {{G}_{t}}\in G,\underset{j=1}{\overset{r}{\mathop \sum }}\,{{g}_{t}}(i,j)=1(1\le i\le N)$

(2)

由节点的特征序列V=＜V₁,V₂,…,V_T＞可以得到全部节点的角色序列G=＜G₁,G₂,…,G_T＞.

1.1.2 动态网络进行角色建模算法

对动态网络进行角色建模的伪代码如下.

　　算法 1. 动态网络角色建模算法.

　　输入:动态网络D=＜S₁,S₂,…,S_T＞;

　　输出:节点角色序列G=＜G₁,G₂,…,G_T＞.

　　1.　G=∅;

　　2.　for (t1 toT)do

　　3.　　G_t=∅; //G_t为t时刻节点的角色矩阵

　　4.　　V_t=∅; //V_t为t时刻节点的特征矩阵

　　5.　　for (n∈N_t)do

　　6.　　　V_t(n)=V_t(n)∪ReFex_basic(n); //ReFex_basic()提取节点基本特征,V_t(i)为特征矩阵V_t的第n行

　　7.　　end for

　　8.　　while (true)do

　　9.　　　for (n∈N_t)do

　　10.　　　　Nei(n)=getNeighbor(n); //计算一阶邻居节点集合

　　11.　　　　f_Nei=∅; //保存由当前一阶邻居所产生的递归特征

　　12.　　　　f_Nei=f_Nei∪ReFex_recurse(Nei(n)); //ReFex_recurse()产生递归特征,使用聚集函数(sum,mean)递归地对其邻居节点的基本特征进行聚集

　　13.　　　end for

　　14.　　　count=0;

　　15.　　　for (f∈f_Nei)do

　　16.　　　　if (ReFex_isNewFeature(f_Nei)) //判断是否为新特征

　　17.　　　　V_t(n)=V_t(n)∪f; //添加新特征

　　18.　　　　elsecount++;

　　19.　　　end for

　　20.　　　if (count==f_Nei.size())break;

　　21.　　end while

　　22.　　G_t=NMF(V_t); //非负矩阵分解得到角色矩阵

　　23.　end for

算法第2行~第21行是对单个网络快照进行特征提取的过程,其中,第2行~第7行得到节点的基本特征,第8行~第21行计算递归特征.第15行~第19行判断本次递归过程中所得到的特征是否与已有特征相似:若不相似则为新特征,并入特征集合;若得到的所有特征都与已有特征相似,则终止递归.第22行用非负矩阵分解得到节点的角色矩阵.

1.2 角色匹配

要识别相邻时刻的角色是否一致,可以将某时刻的角色与下一时刻的所有角色一一匹配.由于角色模型将每个节点在每个时刻都表示为一个角色概率的向量,向量的每一维表示节点在相应角色上的概率取值,假定概率取值最大的角色作为节点的角色,当节点本身属性比较模糊,可以将节点同时划分到相对应的两个角色集合中.通常来说,网络中大部分节点的角色在短时间内不会剧烈变化,因此,可以根据比对相邻时刻两角色节点集合的公共节点来进行匹配,匹配得多的两个角色认为是同一种角色.基于以上思路,接下来定义t时刻角色R_t,i与t+1时刻角色R_t+1,j的匹配程度.

$M({{R}_{t,i}},{{R}_{t+1,i}})=\frac{|{{R}_{t,i}}\cap {{R}_{t+1,i}}|}{|{{R}_{t,i}}\mathop{\cup }^{}{{R}_{t+1,i}}|}$

(3)

1.3 角色解释

得到角色序列G=＜G₁,G₂,…,G_T＞后,节点结构表示为一系列角色的取值分布.由前面介绍可知,节点的角色可以认为是节点的某种相似性度量,能否用熟知的其他度量(如度、介数等)来从侧面对角色做出解释?

给定动态网络的子图快照S_t与角色矩阵G_t,为每个节点选定m种熟知度量,可以得到矩阵M_t∈ℜ^N×m,M_t为t时刻节点的度量矩阵,m为度量个数.要量化角色与度量之间的关系.再次使用非负矩阵分解方法NMF求解一个新的矩阵E_t,使得G_tE_tM_t,其中,E_t∈ℜ^r×m.因此,E_t的行对应r个角色,列对应m个度量,E_t的每一行则表示该角色在各个度量上的概率取值.如此,将角色与一系列熟知度量的关系进行量化,可以形成对角色的直观感受.

2 动态网络角色预测 2.1 问题定义

动态网络的角色预测,就是要利用若干历史网络数据来预测下一时刻网络的节点角色矩阵.形式化表示为:给定动态网络D=＜S₁,S₂,…,S_T＞,得到动态网络角色模型G=＜G₁,G₂,…,G_T＞,G_i为i时刻节点角色矩阵,角色预测就是要得到t+1时刻网络的节点角色矩阵${{{G}'}_{t+1}}.$

若将动态网络角色预测问题视作回归问题,要得到t+1时刻网络的节点角色矩阵,就是要预测每个节点n在t+1时刻的角色分布向量g_t+1${{{G}'}_{t+1}}$的第n行).因此,对每个节点而言,预测目标是一个向量.回归问题分为模型训练和测试两个阶段,设用于学习模型的历史快照数为k+1个,即,用＜G_t-k,…,G_t-1,G_t＞训练模型,其中,提取＜G_t-k,…,G_t-1＞用于预测的属性,G_t为预测目标,采用滑动窗口,向后推移一个时刻,得到测试数据＜G_t-k+1,…,G_t,G_t+1＞,其中,＜G_t-k+1,…,G_t＞提取属性,${{{G}'}_{t+1}}$为预测目标,如图 3所示.k可以视作窗口往前滑动,如此完成动态网络预测任务.

2.2 属性选择

将动态网络角色预测转化为回归问题,首先要为每个节点选择合适的属性.为了尽可能提高预测效果,本文不仅使用了网络的节点角色信息,还为节点计算多种度量.对时刻i的网络快照,为每个节点选择属性集合F=F_R∪F_M,其中:F_R表示节点的角色属性,是节点在各个角色上的取值,由节点角色矩阵G_i得到;F_M是节点的多种度量取值.本文计算6种常见的节点度量(度、带权度、介数、特征向量中心性、带权特征向量中心性以及PR值),角色特征为4个,见表 1.

完成属性选择后,为每个节点得到一个k×f维的属性集合x=[x₁,…,x_d],预测目标为节点在下一时刻的角色分布向量,记为y=[y₁,…,y_m](本文中m=4) .因此,用于训练模型的k+1个历史网络快照可以表示为D={(x¹,y¹),…,(x^N,y^N)},D是训练集,其中,N为网络节点的个数,也是D包含的实例条数.那么,角色预测问题就是要学习模型h:X→Y,能为给定的属性向量x^q预测目标向量y′^q=h(x^q),使得y′^q与真实值y^q最接近.

3 基于多目标回归的动态网络角色预测模型 3.1 预测模型

本文用问题转换思路来解决多类标分类的方法,为每个类标分别建立数据集,每个数据集只包含一个类标,然后使用单类标分类器完成分类.在预测类标时,并没有直接用单类标分类器作为最终模型,而是把得到的所有单目标分类结果重新并入属性集合,如此更新训练数据的属性集合.本文提出解决动态网络角色预测问题的多目标回归模型MTR-RP包括训练和测试两个阶段(如图 4所示),其中,训练阶段又包括了训练一阶模型和训练二阶模型两步.

(1) 训练一阶模型

根据问题转换思想,首先将数据集D={(x¹,y¹),…,(x^N,y^N)}划分为m份,每份表示为${{D}_{j}}=({{x}^{1}},y_{j}^{1}),...,({{x}^{N}},y_{j}^{N})$,对D_j应用已有的单目标回归方法(如线性回归)可得到h_j:X→R.如此,可得到m个预测模型h₁,…,h_m.本文称这些模型为一阶模型,过程如图 5所示.

虽然用单目标回归算法已经为每个目标得到了一阶模型,但本文没有直接将一阶模型作为最终模型.为方便实验对比,本文将这些由单目标回归方法得到的一阶模型记为单目标回归的角色预测方法STR-RP (single-target regression based role prediction).

(2) 训练二阶模型

由一阶模型h₁,…,h_m可以得到各目标的一阶预测值,如图 6所示.为了利用多个预测目标之间可能存在的依赖关系,此处将得到的一阶预测值重新并入数据集的属性集合中用于预测,因此,原始数据集${{D}_{j}}=({{x}^{1}},y_{j}^{1}),...,({{x}^{N}},y_{j}^{N})$更新为$D_{j}^{*}=\{({{x}^{*1}},y_{j}^{1}),...,({{x}^{*N}},y_{j}^{N})\}$,其中,$$x_{j}^{*n}=\left[ x_{1}^{n},...,x_{d}^{n},y_{j}^{\prime n},\ldots ,y_{j-1}^{\prime n},y_{j}^{\prime n},\ldots y_{m}^{\prime n} \right]$为扩充后的属性集合,$y_{j}^{\prime n}$为一阶模型h_j得到的一阶预测值$y_{j}^{\prime n}={{h}_{j}}({{x}^{n}})$,扩充后属性集合的属性个数为[d+(m-1)]个.由扩充后数据集$D_{j}^{*}$使用单目标回归方法得到新的预测模型$h_{j}^{*}:{{X}^{*}}\to R$.如此,可得到m个更新后的模型$h_{1}^{*},...,h_{m}^{*}$,如图 7所示.这里称其为二阶模型,也就是最终的预测模型.在得到一阶模型h₁,…,h_m与二阶模型$h_{1}^{*},...,h_{m}^{*}$后,使用G=＜G_t-k+1,…,G_t,G_t+1＞数据为测试集,记每个节点从时刻(t-k+1) 到时刻t得到的属性集合为x^s,由一阶模型h₁,…,h_m得到一阶预测结果${{y}^{\prime s}}=[y_{1}^{\prime s},y_{2}^{\prime s},y_{3}^{\prime s},y_{4}^{\prime s}]=[{{h}_{1}}({{x}^{s}}),{{h}_{2}}({{x}^{s}}),{{h}_{3}}({{x}^{s}}),{{h}_{4}}({{x}^{s}})]$,然后利用一阶预测结果为每个目标更新属性集,对目标h_j,有$x_{j}^{*s}=[x_{1}^{s},...,x_{d}^{s},y_{1}^{\prime s},...,y_{j-1}^{\prime s},y_{j+1}^{\prime s},...,y_{m}^{\prime s}]$,由此可得最终预测结果(如图 8所示).

${{y}^{\prime\prime s}}=[y_{1}^{\prime\prime s},y_{2}^{\prime\prime s},y_{3}^{\prime\prime s},y_{4}^{\prime\prime s}]=h_{1}^{*}(x_{1}^{(*s)}),h_{2}^{*}(x_{2}^{(*s)}),h_{3}^{*}(x_{3}^{(*s)}),h_{4}^{*}(x_{4}^{(*s)})].$

3.2 MTR-RP的训练过程算法

由此,MTR-RP的训练过程算法可抽象如下.

　　算法 2. MTR-RP的训练过程.

　　输入:数据集D={(x¹,y¹),…,(x^N,y^N)},其中,x=[x₁,…,x_d]为属性集,y=[y₁,…,y_m]为预测目标;

　　输出:一阶模型h₁,…,h_m与二阶模型$h_{1}^{*},...,h_{m}^{*}.$

　　1.　//产生一阶模型

　　2.　for j=1 to m

　　3.　　${{D}_{j}}=({{x}^{1}},y_{j}^{1}),...,({{x}^{N}},y_{j}^{N})$; //复制m个数据集

　　4.　　h_j:D_j→R; //学习单目标回归模型

　　5.　　$D_{j}^{*}=\varnothing $; //初始化新数据集

　　6.　end for

　　7.　//更新数据集

　　8.　forj=1 tom do

　　9.　　foreach x_j∈D_j do

　　10.　　　$x_{j}^{*}={{x}_{j}}$;

　　11.　　　for k=1 to m,k≠j do

　　12.　　　　${{{y}'}_{k}}={{h}_{k}}({{x}_{j}})$; //一阶预测结果

　　13.　　　　$x_{j}^{*}=[x_{j}^{*},{{{y}'}_{k}}]$; //合并一阶预测结果到属性集

　　14.　　　end for

　　15.　　　$D_{j}^{*}=~D_{j}^{*}\cup x_{j}^{*}$; //添加新数据

　　16.　　endforeach

　　17.　end for

　　18.　//产生二阶模型

　　19.　for j=1 tom do

　　20.　　$h_{j}^{*}=D_{j}^{*}\to R$;

　　21.　end for

实验所用单目标回归为线性回归,调用自WEKA函数包weka.classifiers.functions.LinearRegression.class.训练过程的时间复杂度主要在更新数据集时的循环,取决于预测目标的个数m、数据集实例个数(即节点个数)N,时间复杂度为O(Nm²).预测目标一般较小,本文为4,因此,训练过程的时间消耗主要取决于网络节点个数.

4 实验及分析 4.1 数据集

本文选取具有代表意义的3个动态网络数据集(Enron,Facebook,DBLP).

(1) Enron公司邮件网络(Enron(http://konect.uni-koblenz.de/networks/enron))

Enron公司内部员工的邮件网络.Enron公司2001年宣告破产,也引来众多的研究关注.本文选取2001年数据用于构建动态网络,每月为一个快照间隔,共得到12个网络快照.节点表示员工、边为员工之间的邮件往来.

(2) Facebook社交网络(Facebook-wall(http://konect.uni-koblenz.de/networks/facebook-wosn-wall)) Facebook-wall数据源自社交网站Facebook的“用户墙”应用.本文选取的时间段为2008年(1月~12月),每月为一个快照间隔,节点表示Facebook用户,边表示用户间的一次留言.网络中一直存在的节点数为5 111个.

(3) 科研合作者网络(DBLP(http://dblp.uni-trier.de/xml/))

DBLP是大规模的科研合作关系的数据集.作者为节点,作者共同发表一篇论文则产生一条合作关系.本文选取2002年~2011年的数据构建动态网络,每年为一个快照间隔,网络节点表示作者,边表示作者之间的合作关系.在初始化该网络时,去除发表论文总数小于10篇论文的作者.网络中一直存在的节点数为29 747个.

为简化起见,本文假设网络的节点数目保持不变,因而只考虑在研究时间段内一直出现的节点,忽略中途出现或消失的节点.对以上3个网络,本文均建模为无向加权网络,权重的计算使用按时间衰减的思想,即:离当前时刻越远的网络快照,对当前时刻节点权重影响越小.权重计算公式如下:

${{w}_{a,b}}(t)=\sum\limits_{i}{{{w}_{i}}{{\text{e}}^{-\lambda (t-{{t}_{i}})}}}$

(4)

其中,w_i为边ab在t_i时刻的权重,相应的邻接矩阵序列为＜A₁,A₂,…,A_r＞.

3个数据集的详细信息见表 2.

4.2 对比方法

本文使用3种方法作为对比.

(1) PRE(Baseline):直接用当前时刻的节点角色取值作为下一时刻的预测值,即,用t时刻的节点角色矩阵作为t+1时刻的预测结果,即,${{{G}'}_{t+1}}={{G}_{t}}$;

(2) TM:TM方法是前面提到的转移矩阵方法^[11],该方法利用t-1和t时刻的角色矩阵G_t-1和G_t,根据非负矩阵分解得到角色转移矩阵T:G_s(t-1)TG_s(t),由G_t和T相乘得到t+1时刻的目标角色矩阵.

${{{G}'}_{t+1}}:{{{G}'}_{t+1}}={{G}_{t}}T$

(3) STR-RP:以基于单目标回归算法得到的一阶模型为最终模型,$G_{t+1}^{\prime n}$表示节点n在t+1时刻的预测向量.

$G_{t+1}^{\prime n}=[{{h}_{1}}(G_{t}^{n}),...,{{h}_{4}}(G_{t}^{n})].$

4.3 评估方法

给定预测值${{{G}'}_{t+1}}$和真实值G_t+1,本文使用F范数来度量两个矩阵的差异.

$Frobenious\text{ }Loss=||{{{G}'}_{t+1}}-{{G}_{t+1}}|{{|}_{F}}$

(5)

||·||_F为矩阵的F范,对矩阵A计算F范数,显然,F范数值越小,预测效果越好.

$||A|{{|}_{F}}\sqrt{\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{|{{a}_{i,j}}{{|}^{2}}}}}$

(6)

4.4 实验效果

在本文模型中,参数k是用于提取属性集合的时刻个数,直接决定用于预测的数据,因而首先验证参数k对预测结果的影响.下面以Facebook数据集2008年12月的角色矩阵为预测目标,k取值从2到7,每次分别计算预测矩阵${{{G}'}_{t+1}}$和真实矩阵G_t+1的F范数值.图 9为对每次实验重复10遍后取平均的结果,可以看出,k的值从2变化到7,预测效果并没有随之变好,这说明用作预测的属性个数并非越多越好.事实上这也是合理的:一方面,k取值过大带来太多的预测属性,很可能造成数据过拟合;另一方面,可以认为只有离当前时刻较近的历史数据才能有效帮助预测下一时刻网络状态,太远的历史数据可能反而不利于预测效果.当k取3时,预测效果相对理想.

下面分别在Enron,Facebook以及DBLP这3个数据集上验证MTR-RP模型的有效性.此处参数k均设定为3,因而预测目标从时刻5开始,分别表示Enron数据集中2001年5月~12月(如图 10所示)、Facebook数据集中2008年5月~12月(如图 11所示)、DBLP数据集中2006年~2011年(如图 12所示).

对图 10~图 12的分析包括以下几点.

(1) 总体分析.

可以看到,MTR-RP模型在规模不同的3个真实数据集中都取得了很好的效果.与直接用一阶模型方法STR-RP相比,MTR-RP得到更准确的预测值.这说明节点在4种角色上分别对应的取值是具有一定联系的.本文的节点角色取值在归一化处理后,节点在各个角色上的取值存在求和为1的关系.PRE和TM都只使用了前一个时刻的数据做预测,在3个数据集上的预测效果都不如MTR-RP,STR-RP;并且从曲线形状来看,PRE和TM模型的曲线都比较波动.相比之下,MTR-RP和STR-RP能够得到相对稳定的预测结果.

(2) DBLP网络的有趣现象.

观察PRE曲线与其他3条曲线的距离可以发现一个有趣的现象:相比Enron和Facebook网络,在DBLP数据集中,PRE的预测效果与其余3种方法更为接近.PRE直接使用当前时刻节点的角色作为下一时刻的预测值,这是基于相邻时刻网络结构不会发生剧烈变化的假设.继续分析可知,在Enron和Facebook网络中PRE表现很差.这说明Enron和Facebook网络结构并不稳定.事实上,2001年7月~10月间,Enron公司发生了巨大的人事调动,年底公司破产,Enron网络结构理应是不稳定的;而2008年的Facebook网络正处于超速发展中,6月正式成为全球最大、增长最快的社交网络,Facebook的网络结构也不会是稳定的;但在DBLP网络中,学者一般具有稳定的研究兴趣和合作学者,网络结构自然相对稳定.

5 相关工作

目前,动态网络的结构演化分析的相关研究可以分为动态网络结构预测、动态网络的演化模式挖掘以及动态社团发现等.动态网络结构预测的相关研究主要包括网络的链接预测以及节点中心性预测两部分.链接预测主要有:Sarkar等人^[13]提出了一种基于隐藏空间模型(latent space model)的方法对动态网络的边进行预测,该方法基于马尔可夫假设,即,下一时刻节点的边至于当前时刻有关系;Liben等人^[14]研究动态网络的链接预测问题,提出了基于分类思想的网络链接预测方法;Huang等人^[15]将动态网络的链接数据视为时间序列,通过定义新的时间序列相似性度量进行链接预测.动态网络的模式挖掘主要集中于网络频繁子图模式挖掘问题的研究^[16]. Borgwardt等人^[17]提出了动态频繁子图的概念,提出了Dynamic GREW算法用于挖掘动态频繁子图,通过应用后缀树挖掘单边动态频繁子图,迭代地合并小的动态频繁子图得到规模更大的动态频繁子图;以Borgwardt等人的工作为基础,Wachersreuther等人^[18]提出了DFSD算法挖掘动态图中的动态频繁子图,采用字符串方式将静态频繁子图编码,应用字符串的公共子串发现方法得到这些静态图共有的边出现模式,从而获得动态图中的动态频繁子图;Berlingerio等人^[19]提出一种基于频繁模式挖掘的演化规则挖掘算法GREM,解决了动态网络的局部演化规律挖掘问题.动态网络社团挖掘方法主要分增量聚类和演化聚类两类:增量聚类是分别对每个时刻的网络快照进行聚类;演化聚类多采用时间平滑假设,在多个时刻上对聚类进行连续分析.Toyoda等人^[20]给出了挖掘社团演化的6种类型(出现、消失、增长、收缩、分裂和合并),为每种类型分别定义相应的度量,这是社团演化问题较早的研究之一;Hopcroft等人^[21]使用演化聚类的方法究NEC的文献引文网络中社团结构的演化情况,发现网络中可供跟踪的稳定存在社团.

6 总 结

本文解决了动态网络的结构表示、结构演化及角色预测等问题,通过将静态网络的角色发现扩展至动态网络,提出动态网络的角色模型,并以此为基础,将结构预测问题角色预测,提出基于多目标回归思想的动态网络角色预测算法MTR-RP.动态网络是目前复杂网络研究领域中极具活力的新兴研究方向,相比于静态网络的研究成果,目前动态网络的研究还处于起步阶段.本文只针对其中的演化和预测问题进行研究,传统静态网络中许多问题都需要在动态网络中得到进一步研究与扩展,未来的研究工作将继续关注动态网络的演化问题.