时序超网络上重要节点挖掘方法研究

詹秀秀　余小燕　刘闯　张子柯

摘要：在如何識别时序超网络上的重要节点方面取得了一定的进展。定义了该类网络上度量节点重要性程度的 8 个中心性方法及随机移除节点的基线方法，分别侧重于网络不同的拓扑结构性质和时间特征，从多个角度综合考虑了该类网络上节点的重要性。同时，构建了时序超网络上的SI 传播模型，基于该模型提出了新的评估方法来衡量所提出的中心性方法的有效性。研究表明，在时序超网络上，基于最快到达路径的介数中心性方法是评价该类网络上节点重要性的良好指标。此外，基于时间分辨率的度和超度中心性方法通过寻找网络的最佳时间分辨率，可以进一步优化普通的度和超度中心性方法，弥补了普通方法不能有效考虑网络时间信息的缺点，且在多个真实网络上表现出与介数中心性方法相当的性能。

关键词：时序超网络；SI 传播模型；重要节点；中心性方法

中图分类号：N 94            文献标志码：A

Mining methods of important nodes on temporal hyper-networks

ZHAN Xiuxiu1， YU Xiaoyan1， LIU Chuang1， ZHANG Zike2

（1. Alibaba Research Center for Complexity Sciences， Hangzhou Normal University， Hangzhou 311121， China; 2. College ofMedia and International Culture， Zhejiang University， Hangzhou 310058， China）

Abstract： Some  progress  has  been  made  on  how  to  identify  important  nodes  on  the  temporal  hypernetwork. Eight centrality methods for measuring the importance of nodes on this type of network and abaseline  method  for  randomly  removing  nodes  were  defined，  focusing  on  the  different  topologicalproperties and time characteristics of the network， and comprehensively considering the importance ofnodes on this type of network from multiple perspectives. At the same time， a SI spreading model ontemporal hyper-network was constructed. Based on this model， a new evaluation metric was put forwardto  measure  the  effectiveness  of  the  proposed  centrality  metrics.  The  main  results  are  as  follows.Betweenness metric which is based on the fastest arrival path performs better than the other baselines inidentifying  important  nodes  in  temporal  hyper-networks.  In  addition，  the  degree  and  hyper-degreecentrality which consider time resolution are superior to the degree and hyper-degree based on the staticnetwork topology， which makes up for the shortcomings that the static methods that can not effectivelyconsider  the  network  time  information.  In  addition，  they  show  comparable  performance  with  thebetweenness in multiple real networks.

Keywords： temporal hyper-network; SI spreading model; important nodes; centrality methods

网络结构的异质性和复杂性使得在特定观察角度下，某些节点相比于其他节点更具重要性意义，这种重要性可通过中心性来量化。如何衡量网络中节点的中心性是网络分析的基础问题之一，该问题研究目标的实质是确定网络中节点的重要性程度，并对网络中的节点进行重要性排序[1-2]。具有较高中心性值的节点往往是高影响力节点，拥有较强的信息扩散或者疾病传播的能力。因此，找到网络中的高影响力节点具有重要的实际意义。以往的中心性研究成果在现实生活中也获得了广泛应用，如疾病传播控制[3-4]、广告精准投放[5]、交通堵塞疏导[6-8]等。

一般情况下，每个网络都有特定的节点重要性排名，不同的识别方法考虑网络的不同结构属性，会给出不同的排名列表[9]。截至目前，研究者们已经提出了许多用于识别网络中重要节点的中心性方法。例如：Zareie等[10]使用熵对有影响力的节点进行排序； Pu 等[11]提出了局部维度来识别重要节点。 Teng 等[12]追踪了社交网络中的真实信息流，找到了有影响力的传播者；张喜平等[13]引入 m 阶邻居节点的概念，提出了一种基于 m 阶邻居节点重要度贡献的复杂网络节点重要度方法；顾亦然等[14]引入影响度概念，用节点自身的 K- Shell 值与对其邻居节点的影响度来表征节点对邻居节点的贡献重要度。

然而，这些对网络节点中心性的研究仅停留在表示成对节点交互的普通静态网络上，当网络的结构发生动态变化时，静态网络并不能完全准确地描述各式各样的现实世界系统，即现实中的交互均是非静态的、随时间不断发展和变化的，而时序网络可以很好地表达这一概念[15-18]。另外，相比于普通网络所表达的二元交互，现实世界更普遍存在的是表达多个个体间联系的高阶交互，如电子邮件的发送者和接收者、出版物的共同作者、购物网站共同购买一样物品的用户等。放松节点数量限制的超网络是这一类型交互的理想载体[19-20]。因此，为更准确地表达现实世界的复杂关系，本研究将这两类网络组合，构造了一类全新的网络——时序超网络。该类网络随着时间的推移，网络的拓扑结构会随时建立和瓦解，且可形成节点数大于2的超边，其为研究真实复杂系统的动力学提供了良好的表示工具[21]。该框架尤其适用于描述社交系统，典型的如物理接触网络和在线社交网络。在这两种网络所对应的实际场景中，人群间的真实接触和在线会话等交互会随着时间的推移发生变化，此类交互往往是高阶的，并在时间上具有突变性和持续性。已有研究表明，在研究人类时间动力学时，考虑社会互动的高阶结构是非常重要的[21]。时序超网络能以超高的时间分辨率描述现实世界动态演化过程，并从中挖掘到具有高影响力的重要节点，该过程对于上述问题的解决具有非常重要的参考意义。然而，目前关于时序超网络上节点中心性评估方法的研究还寥寥无几，且还未形成系统化的定义。

本文的研究目标是在时序超网络上寻找重要的节点，通过构建基于时序超网络的 SI 传播模型来模拟网络的动态演化过程，定义时序超网络上8个节点中心性评估方法。此外，通过攻击不同中心性方法所寻找到的重要性排名较高的节点来评估所提出的中心性指标的有效性，为挖掘时序超网络上的重要节点提供了理论支撑。

1方法

1.1时序超网络的定义与表示

为方便讨论，假设记录网络的时间有限，且开始记录的时间tstart =0，结束记录的时间tend = T。在时间窗口[0， T]上，根据不同时间戳的节点与超边的隶属关系，构建时序超网络H0（T）={H0 ， H1 ， ··· ， HT}，即时序超网络可以由每个时刻的静态超网络Ht =（Vt ， Et）来表示，且t e [0， T]。其中，Ht =（Vt ， Et）表示属于t 时刻的一组节点 Vt ={v1 ， v2 ， ··· ， vN }和一组超边Et ={e1 ， e2 ， ··· ， em}构成的超网络， N表示时序超网络中的总节点数， m表示Ht中的超边数。值得注意的是，任意一条超边ej可以包含多个节点，任意一个节点vi也可以隶属于多条超边。在时序超网络中，假设每个时间片中的节点个数相同，而超边的数量会随着时间的推移而发生改变。时序超网络若忽略不同交互所发生的时间，即为H0（T）所对应的静态超网络 H =（V， E），其中 V ={v1 ， v2 ， ··· ， vN }，超边eje E，当且仅当ej在Et（t e [0， T ]）中至少出现过一次。

图1（a）为一个由3个时间戳和6个节点组成的时序超网络示例，根据不同时间戳发生的交互所形成的不同连接进行着色。中间的纵轴线代表时间流动的路径，曲线连接着一个交互所涉及到的多个节点，不同颜色代表该时刻的高阶交互所形成的不同超边：如在t1时刻，节点v1，v2，v3之间的两两交互形成一个拥有3个节点的超边（3–超边）；节点v2和v4之间的交互形成拥有两个节点的超边（2–超边）。若忽略图1（a）中时序超网络每条超边出现的时间信息，就可以得到其对应的静态超网络，如图1（b）所示。

1.2时序超网络上节点中心性方法

为了挖掘时序超网络上的重要节点，定义度量该类网络上节点重要性的一系列中心性指标，包括基于节点的度、超度、接触数、节点之间的距离以及网络的时序信息等。

1.3评估方法

针对上述8种时序超网络上重要节点挖掘的中心性指標，提出合理可靠的方法来评估这些度量指标的有效性。

1.3.1 SI 传播模型

构建时序超网络的易感–感染（ susceptible- infected ， SI ）传播模型。在该模型中，个体被分成两组：易感者（susceptible）和感染者（infected）。为简单起见，让所有传播过程都从t =0时刻的一个初始被感染的种子节点开始，其余所有节点的初始状态均被设置为易感状态。按照时间t 推移，依次遍历每一个时刻，若感染节点出现在t 时刻的超边中，就会以β的概率随机去感染其邻居易感节点，该时刻的节点感染完成之后，推移到下一时刻进行感染，传播过程在t = T时刻结束。最后，依次迭代序列中的每一个节点作为初始被感染的种子节点，进行上述传播过程[24]。用φ（t）表示t 时刻以每个节点作为传播源的平均被感染节点总数。

1.3.2节点中心性评估方法

采用不同的中心性方法作为节点攻击策略来评估节点重要性方法的有效性。具体步骤如下： a.对于给定的节点中心性方法，首先用该方法对网络中的节点进行重要性排序； b.删除重要性排名前k的节点序列，构造攻击节点序列后的时序超网络； c.将原始时序超网络和攻击节点序列后的时序超网络分别执行传播概率β下的 SI 传播模拟，分别得到两条传播曲线φ0（t）和φk（t）；d.比较两条传播曲线的差异，即计算两条传播曲线间的面积差。如图2所示，用φ0和φk之间面积差（蓝色标出）评估所提出的中心性指标的有效性，评价指标的数学定义如下：

E （k）越大，说明攻击该中心性方法挖掘到的重要节点能有效抑制传播，同时也验证了该方法的有效性。除了上述8种中心性指标，还将随机删除包含 k个节点的序列作为对比方法（用 Random 表示），随机实验的平均次数为50次。

2实验

2.1数据集

选择9个真实的时序超网络数据集，个体的交互覆盖医院、会议、艺术馆、工作场所、研究机构及学校等。通过这些网络来探究不同的中心性方法在具有不同社会背景和拓扑结构性质的真实场景中的适用性。 EEU1和 EEU2网络描述了欧洲大型研究机构两个不同部门所有成员之间电子邮件的时间网络[25]。HT2009网络是 ACM Hypertext 2009会议期间的时间网络[26]。Gallery 网络记录的是一家艺术馆的参观人员的时间网络[27]。Hospital 网络描述的是法国里昂医院病房中患者、患者和卫生保健工作者以及医护人员之间接触的时间网络[21]。Workplace 网络描述的是2015年在法国办公楼测量的个人之间接触的时间网络[28]。HS2011和 HS2012网络描述的是2011年和2012年法国马赛一所高中学生之间的联系时间网络[29]。PS 网络是儿童和教师之间的联系时间网络[29]。这些网络的基本拓扑性质如表1所示。其中： N 为节点数；C为接触数； T 为网络的最大时间戳；< f >为节点平均度；< g >为节点平均超度；< d >为网络的平均最快到达距离。表2展示的是时序超网络中拥有不同度数的超边规模。表中，超边的度表示一条超边中包含的节点数，这里只统计至网络中超边的度为10的超边数量，“—”表示网络中不存在该度数的超边。从表2可以观察出，随着超边的度的增加，其超边数量是逐渐减少的，大多数的真实时序超网络中的交互局限于度为2，3，4的超边之间，而邮件网络的超边规模偏大。

2.2节点重要性指标的性能比较

上文定义了不同时间分辨率下的度和超度，为了探索不同时间分辨率的中心性指标的性能，将基于时间分辨率的中心性方法的性能定义为从 k =5到k =30范围内有效性E（k）曲线下的面积。以EEU2网络为例，在图3（a）中显示了D 和W方法的有效性结果，并将这两种方法的性能作为对照组（图3（b）中的 static 组），改变网络的时间分辨率?t ，从100增至1000，计算基于不同时间分辨率的度（ D_t）和超度中心性（ W_t）方法的性能。如在图3（b）中，D_t方法的最佳时间分辨率为?t =100，W_t方法的最佳时间分辨率为?t =300。按照这种想法，分别在9个真实网络中，寻找不同方法的最佳时间分辨率，结果如表3所示。如果在某一?t情况下D_t和W_t方法的性能值大于 static 组中的 D 和W方法的性能，则该网络的最佳时间分辨率在表3中用粗体进行标注，可以发现所有网络均可以通过该方法寻找到最佳的时间分辨率，同时在绝大多数网络上D_t和W_t方法的性能比 D 和 W方法更好。因为这两种方法侧重于考虑不同时期网络中节点的重要性，同时结合了网络的时间性质和高阶性质。

在传播中选取β=1来评估不同中心性方法的效果，结果如图4和图5（a ）所示。值得说明的是，D_t和W_t方法选取的均是表3中所列出的最佳时间分辨率。在图5（ a ）中，以 Hospital 网络为例，将9个中心性方法在该网络中所得到的性能值组成一个序列X，并将其按照最大最小值方法进行归一化，即Xi（*）=（xi-xmin）/（xmax-xmin）。式中： Xi表示序列 X 的第i个数据； Xi（*）表示序列 X 的第i个数据归一化后得到的结果；Xmax和Xmin分别表示序列 X 中的最大值和最小值。归一化后，得到对应的序列X*，即为9个中心性方法的平均性能序列，在图5（ a ）中以不同颜色的柱子进行显示。图4和图5（ a ）的结果表明，在时序超网络上定义的中心性方法中， B 方法的有效性和平均性能均明显优于其他中心性方法。可能原因有2个： a. B 方法的节点介数中心性值越高，说明节点更大范围地连接着不同时刻的超边，在网络中充当桥梁的作用越明显； b. B 方法在计算距离时是基于节点的最快到达路径的思想，因此在考虑网络全局特征的同时也考虑了时间的全域性，更加适用于时序超网络。另外，图4出现了两个有趣的现象。首先，在 Gallery 网络中， Q方法表现优异，这可能是因为 Gallery网络的节點平均度较小，平均最快到达距离较长，如表1所示。但在其余真实的时序超网络中该方法的有效性并不是很高，尤其在Workplace 网络中， Q 方法的有效性甚至和对比方法的接近，这说明 Q 方法在度量时序超网络上节点的重要性时并不具备普适性。其次，拟合的曲线会出现下降的趋势，如 Gallery网络中的V方法和 EEU2网络中的Q方法，此现象意味着这些方法挖掘到的节点在网络中的重要性程度并不高。而在图5（ a ）中， Q ，U ，V等方法的效果不如其他方法。最后，可以清晰地观察到，在大多数网络中D_t和W_t方法的平均性能比D和W方法的更好。这说明通过寻找最佳时间分辨率，可以进一步有效优化普通的 D 和W方法。同时，验证了在β=0.5的情况下，不同中心性方法及对比方法之间的平均性能与上述β=1情况下的实验结果类似，如图5（b）所示。

2.3肯德尔相关性

肯德尔相关性系数τ，可以衡量两个不同变量之间的相关性[30]。假设对于两个随机变量 Y和Z ，它们的第i个组合用（Yi ， Zi）表示。当Yi>Yj和Zi>Zj或Yi

式中： n+表示具有一致性的序列个数； n一表示不一致的序列个数。τ=1表示不同方法得到的节点重要性排序列表相同；τ=0则表示相反的情况。τ的值越大，说明两种中心性方法的关系越相关。采用该方法来检测定义的不同中心性方法之间的相关性。

图6显示了9个真实时序超网络不同中心性方法之间的肯德尔相关性结果。首先，可以观察到 D ，D_t，W ，W_t这4个方法之间的颜色最深，即它们之间的相关性最高。虽然这4个方法都是侧重于度量网络中节点关于度的信息来判断节点的重要性，但是从图5（ a ）可以看出，D_t，W_t方法会明显比D ，W方法的平均性能更高，这也进一步说明度量节点中心性时考虑网络时间信息的重要性。其次， U和V方法都是从节点的接触次数出发，判断节点的重要性时考虑的方向是相似的，所以这两种方法之间的相关性程度很高，且在图4中，这两种方法的曲线重合度也很高，再次说明了这两种方法具有很高的相似性。但是，节点的接触数和接触邻居数同节点的度和超度是有差别的，因为它们考虑了节点出现的时间信息，统计了节点在不同时刻出现的次数，所以U和V方法同D ，D_t，W ，W_t方法之间的相关性程度减弱。最后， B 和Q方法分别从节点位于网络中的位置和节点到其他节点之间的最快到达距离等方面来衡量节点的重要性，因此，它们之间的相关性程度略低，同其他方法之间的相关性也类似。

3总结与展望

构建了一种全新类型的网络——时序超网络，其同时兼具网络的高阶性质和时间性质，能更加准确、有效地描绘真实世界的社会系统。此外，基于节点的最快到达路径计算了时序超网络上节点之间的最快到达距离。接下来，针对挖掘该类网络上重要节点的中心性方法匮乏且不成体系等问题，进一步提出了8个中心性方法和评估指标，并在9个不同领域的真实网络上进行了实验研究。结果表明：提出的所有中心性方法中，介数中心性方法总是具有优越性的，其能有效地挖掘到时序超网络上具有高影响力的重要节点；在基于时间分辨率的中心性方法中，通过寻找网络的最佳时间分辨率，可以进一步优化普通的度和超度中心性方法，解决了在时序超网络上计算度或者超度时不能有效地考虑网络时间信息的问题，想法更加合理，实验结果也更加有效。同时，基于时间分辨率的度和超度中心性方法也表现得极具竞争力。综上所述，在真实世界中为了快速且有效地控制疾病和信息的传播，一方面可以通过寻找具有“枢纽”作用的节点并中断其传播能力，另一方面节点出现的时间信息以及其在不同时间窗口的重要性也是不可忽略的关键因素。

本文基于时序超网络定义的一系列中心性方法，一方面重点考虑了节点的度、超度和接触数、节点之间的路径和距离等信息，另一方面结合了网络的时间性质和高阶性质，力求寻求一种能囊括这两方面且效果优异的方法。因此，该工作弥补了目前在时序超网络上挖掘重要节点的中心性方法稀少且不成体系等问题，为后续深入研究时序超网络奠定了较为坚实的基础。

然而，在时序超网络上挖掘重要节点的中心性方法仍存在许多潜在问题：首先，本文所提出的中心性方法还未结合节点的更多方面特征来综合度量节点的重要性；其次，在寻找网络的最佳时间分辨率时，本文粗略地将网络按照某一数值进行划分，这可能会遗漏一些重要信息，故可以根据网络时间讯息的不同，按小时、天数、月份、年份等信息来划分网络，当然，这不可避免地会增加网络信息收集工作的复杂度和任务量。未来研究中，可以根据此类网络的特点改变或补充一些因素，使方法更具普适性和有效性。

参考文献：

[1]郭晓成， 马润年， 王刚.复杂网络中节点重要性综合评价方法研究[J].计算机仿真， 2017， 34（7）：264–268.

[2] WEN T， DENG Y. Identification of influencers in complex networksbylocalinformationdimensionality[J]. Information Sciences， 2020， 512：549–562.

[3] BELL D C， ATKINSON J S， CARLSON J W. Centrality measuresfordiseasetransmissionnetworks[J]. Social Networks， 1999， 21（1）：1–21.

[4] ZENGQ，LIUY，TANGM，etal. Identifyingsuper- spreaders in information-epidemic coevolving dynamics on multiplex networks[J]. Knowledge-BasedSystems， 2021，229：107365.

[5]陈峥， 高翔， 梁恒，等.基于复杂网络的在线广告投放方法[P].中国， 201610741623.3.2017-01-04.

[6]李树彬， 吴建军， 高自友， 等.基于复杂网络的交通拥堵与传播动力学分析[J].物理学报， 2011， 60（5）：050701.

[7]周艳， 李妍羲， 江荣贵， 等.交通拥堵与预警信息交互传播动力学分析[J].地球信息科学学报 ， 2017， 19（10）：1279–1286.

[8]邢国正， 杜萍萍， 方晗琦， 等.基于复合复杂网络交通运输系统研究[J].南阳理工学院学报， 2017， 9（4）：54–57.

[9] LI Z， HUANG X Y. Identifying influential spreaders by gravity model considering multi-characteristics of nodes[J]. Scientific Reports， 2022， 12（1）：9879.

[10] ZAREIE A， SHEIKHAHMADI A， FATEM A. Influential nodesrankingincomplexnetworks： Anentropy-based approach[J]. Chaos，Solitons & Fractals， 2017， 104：485–494.

[11] PU J， CHEN X W， WEI D J， et al. Identifying influential nodes basedonlocaldimension[J]. EurophysicsLetters，2014， 107（1）：10010.

[12] TENG X， PEI S， MORONE F， et al. Collective influence of multiplespreadersevaluatedbytracingrealinformation flow in large-scale social networks[J]. Scientific Reports，2016， 6（1）：36043.

[13]張喜平， 李永树， 刘刚， 等.节点重要度贡献的复杂网络节点重要度评估方法[J].复杂系统与复杂性科学， 2014， 11（3）：26–32，49.

[14]顾亦然， 王兵， 孟繁荣.一种基于 K-Shell 的复杂网络重要节点发现算法[J].计算机技术与发展 ， 2015， 25（9）：70–74.

[15]李佳佳.动态网络中心性方法分析[D].成都：西安电子科技大学， 2012：12–15.

[16]董永强， 祖倩倩， 陶桦.基于真实数据集的动态网络时间中心性分析[J].华中科技大学学报（自然科学版）， 2015， 43（5）：109–113.

[17]付凯， 夏靖波， 赵小欢.动态融合复杂网络节点重要度评估方法[J].哈尔滨工业大学学报， 2017， 49（10）：112–119.

[18]田亮.复杂网络的统计性质及其上动力学分析[D].南京：南京航空航天大学， 2012.

[19]胡枫， 赵海兴， 马秀娟.一种超网络演化模型构建及特性分析[J].中国科学：物理学力学天文学， 2013， 43（1）：16–22.

[20]王众托.关于超网络的一点思考[J].上海理工大学学报，2011， 33（3）：229–237.

[21] CENCETTI G， BATTISTON F， LEPRI B， et al. Temporal propertiesofhigher-orderinteractionsinsocial networks[J]. Scientific Reports， 2021， 11（1）：7028.

[22]汪小帆， 李翔， 陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社， 2006.

[23] AKSOYSG，JOSLYNC，MARREROCO，etal. Hypernetwork science via high-order hypergraph walks[J]. EPJ Data Science， 2020， 9（1）：16.

[24] ZHANXX，HANJALICA，WANGHJ. Suppressing informationdiffusionvialinkblockingintemporal networks[C]//ProceedingsoftheEighthInternational Conference on Complex Networks and Their Applications. Cham： Springer， 2019：448–458.

[25] PARANJAPE A， BENSON A R， LESKOVEC J. Motifs in temporalnetworks[C]//ProceedingsoftheTenthACM International Conference on Web Search and Data Mining. Cambridge： ACM， 2017：601–610.

[26] ISELLA L，STEHL? J， BARRAT A， et al. What's in a crowd？ Analysisof face-to-facebehavioralnetworks[J]. Journal of Theoretical Biology， 2011， 271（1）：166–180.

[27] VAN DEN BROECK W， QUAGGIOTTO M， ISELLA L， et al. The making of sixty-nine days of close encounters at the science gallery[J]. Leonardo， 2012， 45（3）：285–285.

[28] ZHANGSL，ZHAOXY，WANGHJ. MitigateSIR epidemicspreadingviacontactblockingintemporal networks[J]. Applied Network Science， 2022， 7（1）：2.

[29] ZHAN X X， LIU.C，WANGZP，etal Measuring and utilizingtemporalnetworkdissimilarity[DB/OL].（2021–11–02）. https：//arxiv.org/abs/2111.01334.

[30] LVLY，CHENDB，RENXL，et.alVitalnodesidentificationincomplexnetworks[J]. PhysicsReports， 2016， 650：1–63.

（编辑：丁红艺）