重要节点辨识*
胡钢1)† 许丽鹏1) 徐翔2)
1) (安徽工业大学管理科学与工程学院, 马鞍山 243032)
2) (国防科技大学信息系统工程重点实验室, 长沙 410073)
(2020 年10 月30日收到; 2020 年12 月1日收到修改稿)
时序网络可以更加准确地描述网络节点在时空演化过程中的交互顺序变化和交互关联关系. 为辨识时序网络中的重要节点, 本文提出基于时序网络层间同构率动态演化的超邻接矩阵建模的重要节点辨识方法.首先, 依托复杂网络的层间时序关联耦合关系, 定义了相邻与跨层网络综合逼近关系系数. 其次, 依据层内连接关系和层间逼近关系构建时序网络超邻接矩阵. 再次, 使用特征向量中心性方法对时序网络中的节点重要性排序, 分析计算时序全局效率差值, 通过肯德尔相关系数验证. 最后, 实证数据仿真显示: 与经典时序网络模型相比, 本文模型所得Kendall’s t值在各时间层上平均提高, 最高为8.37%和2.99%, 结论表明时序网络层间同构率的度量方法科学有效.
关键词：时序网络, 层间同构率, 特征向量中心性, 时序全局效率
PACS：89.75.Da, 05.10.–a DOI: 10.7498/aps.70.20201804
1 引 言未识别的网络
动态时序网络研究节点间的时空交互关联关系和节点重要性动态分类、排序等演化次序辨识，可以更加准确地刻画手机通讯、社交等复杂系统的交互关系[1]. 节点重要性的评价方法有很多种, 如度中心性[2]、介数中心性[3]、紧密度中心性[4]、特征向量中心性[5]、K-核中心性[6]等, 不同的评价方法考虑的网络特征也各有不同. 胡钢等[7]选取了七个代表性指标进行网络重要性节点贡献率排序, 研究网络节点不同重要性指标对节点的影响程度. 传统的节点重要性排序方法多从单独的指标或因素进行分析, 使得评价结果缺乏全局性与合理性, 于会等[8]提出了基于多属性决策的复杂网络节点重要性综合评价方法. 胡钢等[9]根据解释结构模型对网络邻接矩阵进行级位划分, 得到网络的递阶有向图, 确定节点的重要性. 王凯莉等[10]基于网络中节点自身壳值及其多阶邻居的壳值, 提出了多阶邻居壳数向量中心性方法. Li等[11]从传播动力学的角度, 提出了一种新的分类邻居算法来量化节点传播能力, 进而区分不同节点的影响.
复杂网络重要节点辨识的研究在静态网络上已取得一定进展, 但是在时序网络(节点间关联关系随时间动态变化的网络)的情况下仍缺乏系统理论方法用于识别时序网络中的重要节点[12]. Tang 等[13]通过时序最短路径定义时序介数中心性和时序紧密度中心性等网络结构特性, 提出节点重要性预测及网络切片
方法. Zhao等[14]将空气质量系统创新地抽象为复杂的网络, 在量化区域动态相互联系和相互作用的基础上, 提出一种建模方法来挖掘不同区域之间的关系. Li等[15]提出一种新算法来
* 国家自然科学基金(批准号: 51368055, 61702006)资助的课题.
† 通信作者. E-mail: hug_2004@126
© 2021 中国物理学会 Chinese Physical Society wulixb.iphy.ac
检测由网络中的主要领导者驱动的团簇结构, 并应用于电子商务系统. 代萌等[16]基于31年滑动窗口研究了时序空间上干旱多属性风险的动态特征, 对干旱动态演变的驱动力进行了探究. Qu等[17]提出了用于时序网络的时序信息收集(TIG)过程, 并探索时序信息对节点重要性的影响. 为了利用现有
信息来恢复不确定的复杂网络的拓扑结构和系统参数, Wang等[18]提出了一种基于自适应预期同步的方法来识别存在噪声的不确定时变时滞复杂网络的未知系统参数和网络拓扑结构. Tang等[19]基于拓扑-时间规律的组合提出了一个基于熵率的框架, 用于量化时序网络的可预测性. Yang等[20]提出一种基于节点相似度的社会网络模糊化方法，并对网络模糊密度与模糊中心势进行预测, 实现模糊网络的度量预测. Schaub等[21]基于复杂网络动力学以及多元微分方程, 提出一种复杂网络的多尺度动态嵌入技术. 李志宇等[22]构建针对新增节点的动态特征学习方法, 使得模型可以提取大规模社会网络在动态变化过程中的结构特征.
上述方法仅仅考虑时序网络各节点在每个时间切片上的连接关系, 为完整地表示时序网络的动力学过程和结构演变特征, 还需要考虑时序网络各节点在不同时间切片间的连接关系. 郭强等[23]基于TOPSIS多属性排序方法得出使用优先链接指标(PA)度量挖掘出的重要节点最准确. 邱路和黄国妍[24]提出时变状态网络模型, 分析不同时间状态网络的连接相似性. Taylor等[25]考虑用多层耦合网络分析的方法, 将时序网络按层间关系和层内关系建立超邻接矩阵(supra-adjacency matrix, SAM)，并定义了基于特征向量的中心性指标和节点重要性随时间波动的评判指标. 经典的SAM方法忽略了复杂网络中不同节点层间连接关系的差异性, 杨剑楠等[26]将节点的层间连接关系用邻居拓扑重叠系数表示, 提出了基于节点层间相似性的超邻接矩阵(similarity-based supra-adjacency matrix, SSAM)时序网络构建方法. 朱义鑫等[27]针对相关系数的改进问题, 给出一个网络演化速度指标; 同时, 提出了一个具有非马尔可夫性质的时序网络演化模型. 但也只是表达相邻网络间的耦合关系, 基于此, 我们考虑了跨层网络间的相容相似度, 并结合向量在n维实数空间上的投影值以及节点邻居的贡献值提出了时序网络层间逼近关系系数, 实现了信息的矢量计算和标量计算, 通过信息的集结弥补了邻居拓扑重叠系数的不足, 最后构建了改进的
o(n2)
基于时序网络层间同构率动态演化的超邻接矩阵模型(isomorphism rate based supra-adjacency matrix, ISAM). Workspace及Email-eu-core数据集上的实验结果显示, 本文方法得到的Kendall’s t值较SAM方法在各时间层上平均提高, 最高为8.37%和2.99%. 且本文方法在算法复杂度上和SAM 一样, 均
为, 说明本文方法能更准确地辨识时序网络中的重要节点, 为时序网络建模提供了一种新的思路.
2 时序网络相关概念
基于目前研究的复杂网络相关方法, 本文综述了时序网络定义; 同时, 为了时序网络表征研究更近一步的推广, 给出了时序网络向量范数、时序网络相容相似度系数、时序网络向量投影值、时序网络节点资源分配相似度系数以及时序网络层间逼近关系系数等定义.
2.1 时序网络定义
网络科学将复杂系统抽象为复杂网络, 动态时序网络是一个包含了个体、个体间交互作用及时间轴的复杂系统. 我们将个体视为节点, 则个体间的交互作用形成了节点间的连边, 边与边之间的交互作用形成了网络分块, 块与块的相互影响构成了整个复杂网络. 当节点间的关联关系随时间演化呈现出一定规律, 即发生关联点、关联边随时间先后增删的系统性变化, 我们把这样一个过程叫做时序网络演化过程. 通常一个网络可以定义为二元组G = (V, E), 所有节点构成节点集V = {v1, v2, ···, v N}，节点间的关系构成边集E = {e1, e2, ···, e H}. 在时序网络中, 边集E中的元素可以用形如(i, j, t, d t)的四元组表示[28], 表示节点i与节点j从t时刻开始产生交互并持续d t的时长. 如视频通话数据网络中, 用户A, B在t1时刻开始视频通话, t2时刻结束视频通话, 这个事件可以表示为(A, B, t1, t2–t1), 所有这些四元组的序列构成了视频通话数据的时序网络. 如果省略时序网络中个体间发生事件的时长信息, 而只考虑两个体在某一时间窗内
发生交互的初始时刻, 则可以用三元组(i, j, t)来表示节点i与节点j在t时刻发生交互. 将时序网络整个观察期[t, t + S] 分成T个时间窗口, 每个时间窗的大小为t = S/T, 可以得到T个等间距、不重叠且连续的时间窗口{[t, t + t), [t + t, t + 2t),
···, [t + (T - 1)t , t + S )}, 则时序网络被分为T 个离散有序的时间层网络G 1, G 2, ···, G T .
2.2 时序网络层间逼近关系系数分析
定义1 时序网络向量范数. t 时刻网络G t 有邻接矩阵A = (a ij )∈R n × n (i , j = 1, 2, ···, n ), 在无向网络中, 显然有
A T = A , 即
a ij = a ji . 邻接矩
阵A 可用向量表示为A = (a 1, a 2, ···, a n )T , 对于向量a i (i = 1, 2, ···, n )∈R n , 与a i 对应的一个实
值函数(并记为) ||a i ||称为R n 上的一个向量范数,
且满足:
1) ||a i || ≥ 0, 其中||a i || = 0当且仅当a i = 0;∀2) ||a a i || = |a | ||a i ||, a ∈R ;
∀3) ||a i + a k || ≤ ||a i || + ||a k ||, a i , a k ∈R n .于是有向量a i = (a i 1, a i 2, ···, a in )∈R 范数一
当p →∞, 定义∞–范数:
定义2 时序相邻网络相容相似度系数. 考虑到时序相邻网络层上节点自身邻居的影响[23], 即两个节点的共同邻居越多, 两节点越相似. 我们用Salton 指标(Salton index, SAL)[29]定义相邻网络相容相似度系数, 具体形式如下:
相邻网络相容相似度系数描述了节点邻居关系以及节点间持续关联的层间同构率. 其中a ij (t ),a ij (t + 1)对应相邻时间层网络G t , G t +1的邻接矩阵元素. 如果在任一时间层网络G t 中节点i 与节
点j 之间存在连边, 则a ij (t ) = 1; 否则a ij (t ) = 0.此外, 向量a i 在相邻时刻t , t + 1均为零向量(孤立节点)时, 规定c i (t , t + 1) = 1; 仅有一个时刻为零向量时, 规定c i (t , t + 1) = 0.
定义3 时序跨层网络相容相似度系数. 时序网络中节点间的连边随时间动态增删, 仅仅考虑相邻网络间的同构率可能无法准确辨识时序网络的重要节点. 基于此, 我们提出了时序跨层网络相容相似度系数.
例如, 跨一层网络相容相似度系数
跨两层网络相容相似度系数
跨层网络相容相似度系数揭示了跨层网络间的同构率, 反映了在某一时间区间内网络的局部特征与局部链块的鲁棒性与稳定性的传承. 参数p 随所跨网络层数的变化而改变, 即p = m ; 当跨层数增加到无穷大的时候, 用∞-范数代替p -范数;m 即网络G t , G t+m 间的间隔层数, 只有节点j 同
时满足在m 个时间层上都是节点i 的邻居, 才有a ij (t )a ij (t + 1)···a ij (t + m ) = 1; 其他情况时a ij (t )a ij (t + 1)···a ij (t + m ) = 0. 向量a i 在时刻t , t + 1, ···, t + m 均为零向量(孤立节点)时, 规定c i (t , t + m ) = 1; 不全为零向量时, 规定c i (t , t + m ) = 0.
定义4 时序网络向量投影值. 为描述向量在
n维实数空间随时间演化的方向变化, 我们把相邻层网络向量之间的夹角叫做向量投影角, 投影角的余弦值定义为投影值. 邻接矩阵A可以由n个行向量(矢量)表示, 则向量a i在两时间层t, t + m (t, m = 1, 2, ···, T–1)的投影值具体表示为:
(i) 时序相邻网络向量投影值(m = 1)
其中, 0 ≤ d i(t, t + 1) ≤ 1, 投影值d i(t, t + 1)越大, 表示向量a i在相邻时间层t, t + 1的方向一致性越高, 反映节点在时序演化过程中同构率越大. 向量a i在相邻时间层t, t + 1均为零向量(孤立节点)时, 规定d i(t, t + 1) = 1; 仅在一个时间层为零向量时, 规定d i(t, t + 1) = 0.
(ii) 时序跨层网络向量投影值(m > 1)
¯d
¯d/σα=max {¯
d1
σ1
,
¯d
2
σ2
,···,
¯d
n
σn
}
d(t,t+m)
i
∈[0,1]
对于跨层网络向量投影值, 我们通过两两比较相邻层网络向量, 根据(7)式求出所有相邻层网络的投影值的平均值, 再计算投影值的标准差s，定义为跨层网络向量投影值d i(t, t + m), 其中参
数, 保证.该投影值越大, 表示向量a i在时间段[t, t + m] (m > 1)的方向一致性越高, 反映节点在时序演化过程中越稳定.
定义5 时序网络节点资源分配相似度系数.静态网络中资源分
配指标(resource allocation, RA)[30]的思想是: 如果网络中两个节点没有直接相连, 可以将它们的共同邻居作为传递的媒介. 基于此, 我们提出了时序网络节点资源分配相似度系数, 具体如下:
(i) 时序相邻网络节点资源分配相似度系数
(ii) 时序跨层网络节点资源分配相似度系数
例如, 跨一层网络节点资源分配相似度系数:Γ(i t)∩Γi t+1
其中表示节点i在相邻时间层的共同邻居, d(z)表示共同邻居节点的度值. 该系数反映了节点间的相似性不仅和共同邻居的数量有关，还和邻居节点的质量(度值)有关. 节点共同邻居的数量越多、邻居节点的度值越小, 则时序相邻网络节点资源分配相似度系数越大.
定义6 时序网络层间逼近关系系数. 综合考虑两时间层网络相容相似度变化(标量变化)、向量间的投影值变化(矢量变化)以及节点资源分配情况, 我们提出时序网络层间逼近关系系数Z
, Z = (Z1, Z2, ··· Z N)T. Z i(t, t + m)表示节点i在两时间层网络的同构率, 具体形式如下:
d(t,t+m)
i
c(t,t+m)
i
S(t,t+m)
i
其中反映节点邻居数量多少，反映节点邻居质量优劣, b(b∈[0, 1])表示偏好系数. Z i(t, t + m)越大, 表示两时间层网络节点连接关系越紧密, 则节点在两时间层网络的同构率越高; 反之, 表示两时间层网络节点连接关系越稀疏, 则节点在两时间层网络的同构率越低.
3 时序网络超邻接矩阵系统模型构建
经典时序网络建模时考虑用多层耦合网络分析的方法, 将时序网络按层间关系和层内关系建立超邻接矩阵, 但在表示不同时间层网络间关系中使用了相同的参数, 忽略了复杂网络中不同节点层间连接关系的差异性. 为此, 我们提出了改进时序
网络建模方法, 在经典SAM 模型的基础上, 给出时序网络层间逼近关系系数, 并提出改进的ISAM 模型.
3.1 经典时序网络建模思想
文献[25]将时序网络通过层内连接关系和层间耦合关系来表示, 提出了经典的SAM 时序网络模型, SAM 为NT × NT 的分块矩阵, 为构建时序网络提供了一种新思路. 我们把有序时间层网络集合定义为G = {G t } (t = 1, 2, ···, T ), T 为切分的时间层总数, 则其SAM 模型具体表示如下:
其中, 超邻接矩阵A 表示经典的时序网络模型;A (1), A (2), ···, A (T )表示层内连接关系, 这里用等间距切分的T 个时间层网络对应的邻接矩阵表示，依次位于超邻接矩阵A 的对角线上, 表示有序的时间层网络: 定义a ij (t )为邻接矩阵A (t )中的元素，则a ij (t ) = 1表示在时间层网络G t 中节点i 与节点j 间有连边, a ij (t ) = 0表示无连边; w I 表示相邻层网络层间耦合关系, 其中w 为可调参数, 在lim w → 0时, 层变得不耦合; 在lim w → ∞时, 层之间的耦合非常强, I 为N × N 单位矩阵. 由于经典的SAM 时序网络模型中仅考虑层的最近邻耦合关系, 所以超邻接矩阵A 其他部分均用0表示.
3.2 改进时序网络建模分析
用同一参数w 来表示, 忽略了异质网络中不同节点的差异性, 为了更真实地反映相邻时间层网络连接的实际情况, 本文对SAM 模型中的相邻层间关系做出改进, 并考虑了非相邻层间耦合关系.
时序网络相邻层间关系和节点在相邻网络间的连接关系与其在相邻层上的持续出现度及节点的邻居关系层间相似程度有关[26], 考虑时序演化过程中节点邻居的数量和质量变化, 我们提出时序网络层间逼近关系系数Z . 改进的基于层间同构率的ISAM 时序网络模型具体表示形式如下:
T ISAM (n )=o (kn 2)T ≪n T ISAM (n )=o (n 2)其中, Z (1, 2), Z (2, 3), ···表示相邻时间层之间的逼近关系, Z (1, 3), ··· 表示非相邻层之间的逼近关系;Z (1, 2)为N × N 的对角矩阵, 即Z (1, 2) = diag (Z 1(1, 2), Z 2(1, 2), ···, Z N (1, 2)), 而Z i (1, 2)即为节点的层间逼近关系系数, 描述了节点i 的层间同构率. 图1
给出了该模型的算法流程图, 该模型的算法复杂度
, 其中k 是关于时间层数T 的函
数, 当 时, .
图2给出了一个包含3个时间层和4
个节点的时序网络及ISAM 模型的构建, 其中黑实线表示层内连接关系, 黑虚线表示层间逼近关系.
图2对应的层内连接关系由各个时间层网络的邻接矩阵确定, 即(14)式的对角线矩阵块部分；不同时间层网络的层间逼近关系则由各个节点的层间同构率, 即(12)式层间逼近关系系数计算得到. 图2的模型计算结果如下:
发布评论