有向超图中的重要节点识别：一种基于邻域超边熵的方法

《Neurocomputing》：Identifying important nodes in directed hypergraphs: a method based on neighborhood hyperedge entropy

　　谢金|朴宇豪|高伟峰|李红
中国山西省西安市710126，西安电子科技大学数学与统计学院

摘要
在定向超图中识别有影响力的节点对于理解复杂系统中的高阶相互作用至关重要，但目前相关方法较为匮乏，且往往无法捕捉超边的方向性和结构差异性。本文提出一种新的中心性度量方法——邻域超边熵方法（HEM），用于对定向超图中的节点进行排序。该方法首先将定向超图转化为线图，其中超边变为节点，并定义了考虑头节点与尾节点比例以及超边之间交集的超边度。接着，在该线图中引入基于熵的框架，通过指数衰减的方式结合入度与出度的邻域信息，以捕捉多阶影响，从而得到超边的影响力。为确定节点层面的重要性，我们设计了三阶段分配机制，根据头节点与尾节点数量、超边间共享节点以及连接不同超边的桥节点这三类结构特征，将超边中心性分配给各个节点。在来自不同领域的12个真实定向超图上的大量实验表明，无论是在感染动态（SI模型）、单调性、鲁棒性还是排序相关性方面，HEM均优于现有的中心性方法，包括基本方法以及近期提出的更优的超图中心性算法。

引言
网络本质上是由节点和边构成的复杂系统。重要节点通常在网络的结构稳定性、信息流传递、资源分配等方面起着关键作用。近几十年来，识别重要节点的研究已广泛应用于疾病传播[1]、[2]、谣言控制[3]、[4]、[5]、广告领域[6]以及交通控制[7]、[8]、[9]等多个领域。这些研究大多集中在普通图上[10]、[11]。目前，关于节点识别的研究大多也聚焦于普通图，其主要改进方式包括优化引力模型和k壳层方法[12]、[13]、[14]，基于全局与局部双重视角的识别方法[15]、[16]，以及图嵌入方法[17]等。然而，针对定向图中重要节点的识别方法却非常少[18]、[19]。普通图中每条边仅连接两个节点，无法体现多个节点之间的协同效应，而允许超边连接多个节点的超图则能有效克服这一局限。目前，关于超图识别网络的研究大多集中于无向超图。王等人[20]提出了一种基于节点本身、所属超边及社区来识别多层无向超图中重要节点的方法。谢等人[21]提出了一种新的中心性方法（HGC）以及基于引力模型的半局部中心性方法HGC，能够在精度与计算复杂度之间取得平衡。刘等人[22]提出了一种结合超边连接与节点信息熵，并与k壳层分解相结合的无向超图重要节点识别方法，该方法通过节点的过度数及共享信息的熵值来评估节点的局部重要性，从而更准确地衡量局部属性。王等人[23]提出了一种基于信息传播动态的定向超图重要节点动态识别算法，结合波动扩散模型与蚁群协作模型来识别无向超图中的重要节点。李等人[24]提出了一种基于LGKs k壳层分解的方法，结合全局与局部视角，降低了时间复杂度，提高了无向超图中重要节点识别的精度。不过，针对定向超图的类似研究仍然较少。

过去几十年中，图熵一直被用作衡量网络节点中所含信息量的标准。Rashevsky[25]首次提出了图熵的概念。近年来，图熵被频繁用于识别重要节点。费等人[26]提出了一种利用相对熵和拓扑斯方法识别重要节点的新方法。由于不同网络中的信息流动方式各异，这种同时考虑局部与全局因素的方法能够更有效地识别重要节点。雷等人[27]提出了一种基于Taslli熵的局部结构熵（LSE）方法，该方法通过Taslli熵结合一阶和二阶相邻节点的度与区间，通过节点移除后的网络结构特征来衡量重要节点。曾等人[28]提出了一种基于熵的节点重要性识别方法，该方法基于度中心性、介数中心性、接近中心性、特征向量中心性及聚类系数为系统建立基于熵的度量标准。张等人[29]提出了一种基于s距离的模糊中心性方法，通过超边来描述节点间的关联，该方法假设节点的影响力取决于与其具有特定s距离的相邻节点。春等人[30]系统地回顾了39种超图中心性与重要性度量方法，提出了结构、功能与背景三大类别的框架，并通过实证分析比较了它们的相似性及计算效率。李等人[31]对超图挖掘中的结构模式、分析工具及生成模型进行了系统综述，提出了分类体系及未来研究方向。李等人[32]提出了h-模体与特征谱（CP），用于系统分析真实超图的局部结构，并开发了一种名为MoCHy的高效并行计数算法。昂等人[33]提出了一种基于邻域熵（NEM）的方法，用于识别定向网络中的关键节点，通过定义节点的k阶内部熵与k阶外部熵来捕捉节点的邻域信息，同时还引入了一个可调参数，以平衡内部邻居与外部邻居对节点影响力贡献的程度。然而，这些方法并未从边的角度来定义熵，尤其是在高阶结构中。如果计算节点的熵，必然会导致算法复杂度上升。

本文提出了一种邻域超边熵方法（HEM），用于识别定向超图中的有影响力节点。该方法首先将每个超边视为一个节点，并定义超边度，从而将原始定向超图转化为线图。随后，在该线图中，根据每个超边的度来计算其邻域熵。最后，根据超边的三种结构特征——头节点与尾节点数量、共享节点以及桥节点——重新分配基于熵的超边重要性，从而得出每个原始节点的重要性。

本文的贡献可总结如下：
(1) 提出了两种定向超图的中心性指标。目前，用于识别定向超图中重要节点的算法极为有限，本文旨在填补这一空白，提出了两种定向超图中心性指标：超图信息流（HIF）与超图模糊度（FUZ）。HIF用于计算节点在信息流中的重要性，而FUZ则用于衡量包含某节点的所有超图中头节点与尾节点数量之间的平均绝对差值。
(2) 提出了邻域超边熵方法（HEM），用于识别定向超图中的重要节点。该方法首先将超图转化为线图表示形式，然后定义定向超边的度，以此区分线图中各个超边节点的重要性。接着，利用邻域熵方法识别重要的超边节点，此时考虑的是超边节点的度而非普通节点的度。最后，设计了一种三阶段分配机制，根据头节点与尾节点数量、共享节点以及桥节点等结构特征，将定向超边的影响力重新分配给各个节点。
(3) 通过大量实验验证了该方法的有效性。我们使用了来自九个不同领域、具有多样特征的实时数据集，证明了HEM在传播能力、单调性及鲁棒性方面均优于其他方法，同时还进行了参数敏感性实验。此外，我们还通过肯德尔相关系数图分析了HEM与其他中心性方法之间的相关性。

章节节选
定向超图的定义
我们将具有节点集V和定向超边集E的超图记为H = (V,E)，其中V为节点集合，E为超边集合。对于某个超边e，其尾节点集称为T(e)，头节点集称为H(e)。需要注意的是，每个超边都包含两个或更多节点，且需满足以下条件：对于任意超边e，其头节点集与尾节点集均非空，同时定向超图中的每个节点至少属于一个超边，这样就避免了某些节点不属于任何超边的情况。

现有方法
目前，用于识别定向超图中有影响力节点的方法相对较少。从传播能力的角度来看，超图中节点的影响力在很大程度上取决于它们的局部传播能力。重要节点应能够通过多种路径向多个潜在方向传播信息。因此，度分布对于确定相邻节点的重要性起着至关重要的作用：度分布越均匀……

实验分析
为证明所提算法的有效性与优越性，本节将在九个真实网络上测试我们的中心性方法，并将其与现有的七种中心性方法进行比较。基准方法包括：超图度中心性（HDC）[34]、超图紧密度中心性（HCC）[35]、超图介数中心性（HBC）[36]。此外还有更先进的中心性方法：超图向量中心性（HVC）[37]、改进版的PageRank算法（ImpageRank）[34]……

结论
在本研究中，我们提出了一种超边邻域熵方法（HEM），用于识别定向超图中的有影响力节点。该算法基于信息熵原理，首先将定向超图中的每个超边视为一个节点，进而将超图转化为线图。之后采用基于度的分析方法，考虑不同超边特征的重要性差异。在该线图中，利用邻域熵来识别关键的超边节点。

讨论
超边邻域熵方法（HEM）是一种用于识别定向超图中重要节点的极具潜力的方法。通过与普通边相比，HEM能够捕捉超边的结构重要性及其在网络中的相互关联。通过定义定向超边的度，利用线图中的超边来计算邻域熵，再根据头节点、尾节点、共享节点及桥节点的数量来分配重要性……

复杂度分析
HEM的时间复杂度为O(E·A·D)，其中E为超边数量，A为平均超边大小，D为线图的平均度，而常数项通常为2–3。相比之下，HDC的时间复杂度仅为O(E)，但它仅计算尾节点权重，无法捕捉方向性及高阶相互作用。像HCC、HBC、NDEK和EHDF这类方法则依赖于所有节点对之间的距离或矩阵运算，其时间复杂度较高，难以适用于大规模节点集。HVC的时间复杂度也为较高水平。

CRediT作者贡献声明
谢金：方法论、研究实施、资金获取、正式分析、数据整理。朴宇豪：资源协调、项目管理、方法论、研究实施、正式分析、数据整理。高伟峰：项目管理、资金获取。李红：项目管理、资金获取。

利益冲突声明
作者声明不存在任何可能影响本文研究的已知财务利益或个人关系。

致谢
本研究部分得到了中国国家自然科学基金项目（编号62276202）、中央高校基本科研业务费项目（编号QTZX25074）、浙江省自然科学基金联合资助项目（编号LHZY24A010005）、中国博士后科学基金会项目（编号2024MD754039和2023T160501）以及空间微波科技国家重点实验室的支持。谢金于2020年在中国西安的西安电子科技大学获得数学博士学位，目前为该校数学与统计学院副教授，研究兴趣包括多智能体系统共识机制、去中心化联邦学习、分布式优化及学习算法。