一种基于α三角形的图特征向量中心性

《Chaos, Solitons & Fractals》:An α-triangle eigenvector centrality of graphs

【字体: 大 中 小 】 时间:2026年09月26日 来源:Chaos, Solitons & Fractals 5.7

编辑推荐:

   摘要 中心性度量是复杂网络分析中的一个基本概念,通过中心性度量可以识别网络中的重要顶点。多年来,研究人员从不同角度开发了多样化的中心性度量方法。本文提出了一种α-三角形特征向量中心性(αTEC),这是一种基于边和三角形结构的全局中心性度量。它可以通过参数α(α∈(0,1])动

  

摘要 中心性度量是复杂网络分析中的一个基本概念,通过中心性度量可以识别网络中的重要顶点。多年来,研究人员从不同角度开发了多样化的中心性度量方法。本文提出了一种α-三角形特征向量中心性(αTEC),这是一种基于边和三角形结构的全局中心性度量。它可以通过参数α(α∈(0,1])动态调整边和三角形的影响。顶点的中心性得分定义为非负张量的谱半径对应的特征向量。根据Perron-Frobenius定理,αTEC保证连通图中所有顶点的中心性向量是唯一的正向量。在合成网络和真实世界网络上的数值实验表明,αTEC能够捕捉边和三角形对顶点重要性的影响。随着α增大(减小),中心性排名反映出边结构的贡献增强(减弱),而三角形结构的贡献减弱(增强)。

引言 中心性度量是识别复杂网络中重要顶点的基本工具,应用于社会网络分析[1]、疾病传播[2]、网络分解[3]和网络聚类[4]等领域。由于不同的度量方法捕捉不同的拓扑特征,它们可能对同一网络产生截然不同的排名。

现有的中心性度量方法在所利用的结构信息方面存在差异。局部度量方法,如度中心性[5]和三角形中心性[6],主要刻画顶点的直接邻域。全局度量方法,如特征向量中心性[7]、子图中心性[8]、[9]、中介中心性[10]和接近中心性[11],则纳入网络范围的信息。

许多全局中心性度量方法以成对邻接、路径或游走为基础进行构建。尽管三角形丰富的结构可能间接影响其值,但基于三角形的交互并未作为顶点重要性的独立来源被表示出来。三角形是图中最简单的高阶结构之一,在链接预测[12]、社区检测[13]和网络稳定性[14]中发挥着重要作用。相反,仅基于三角形的度量方法会丢弃不包含在三角形中的边的信息,可能无法区分三角形结构之外的顶点。因此,仅考虑边或三角形可能会导致结构信息的损失。

已有若干研究将三角形或高阶信息纳入中心性度量。Burkhardt[6]提出了三角形中心性,利用与顶点及其邻居相关的三角形计数来评估顶点。尽管该度量捕捉了局部三角形的集中程度,但它并没有通过整个网络递归传播顶点重要性。类似地,文献[15]、[16]中的度量方法通过统计与顶点相关的特定子图来评估顶点重要性。Arrigo等人[17]提出了一种非线性中心性框架,将成对链接的矩阵表示与楔形或三角形交互的三阶张量表示相结合。然而,边和高阶分量作为不同阶的代数对象被保留下来,而非嵌入到统一的张量表示中。相比之下,我们的方法将边和三角形信息编码在一个非负三阶张量中,并通过其特征向量定义中心性。Benson[18]为均匀超图开发了张量特征向量中心性度量。将图三角形视为三顶点超边会产生基于三角形的张量表示,但不包含三角形之外的成对边。此外,原图的连通性并不必然意味着诱导三角形超图的连通性,因此保证所有原顶点具有正的唯一得分的条件可能不成立。因此,一个尚未解决的问题是:如何在单一谱框架内整合成对边和三角形交互,为连通无向图定义全局递归中心性,同时保证所有顶点的得分为正且唯一。

为了解决这一问题,我们提出了α-三角形特征向量中心性(αTEC),这是一种针对连通无向图的全局顶点中心性度量,将边和三角形结构信息整合在统一的非负三阶张量框架中。具体而言,我们定义Aα = αAE + (1-α)A?, 0 < α ≤ 1,其中AE和A?分别编码边和三角形结构。αTEC得分由Aα谱半径对应的正特征向量定义。对于每个连通图,当α > 0时,边分量保证Aα是弱不可约的,从而保证在归一化后存在唯一的正中心性向量。

参数α调节基于边和基于三角形的交互的相对贡献。当α = 1时,αTEC产生与经典特征向量中心性相同的排名,而较小的α值则更加强调三角形结构。这种参数化与已建立的中心性度量方法一致:Katz中心性[19]使用衰减参数控制不同长度游走的贡献,Bonacich幂中心性[20]使用参数来建模对邻近顶点的不同依赖形式。类似地,α提供了一个可解释的机制,使所提出的中心性能够适应不同的网络结构。每当成对关系和凝聚三元结构都具有有意义的领域解释时,所提出的框架就可以转化为应用设置。例如,在合作网络中,边和三角形分量可能代表双边合作和凝聚的三人团队,而在生物交互网络中,它们可能代表成对分子相互作用和密集连接的三节点结构。因此,α接近1的值强调成对连通性,而较小的值则强调三角形支持的凝聚力。在α值范围内检查排名允许从业者确定识别出的重要顶点是否具有鲁棒性,还是取决于所强调的结构机制。

本工作的主要贡献是一个全局递归中心性框架,将成对边和三角形交互整合在单一的非负三阶张量中。与仅基于三角形的方法不同,所提出的方法保留了所有原始边,并且对于每个连通图都保证存在唯一的正中心性向量。参数α提供了一种可解释的机制,用于考察基于边的和基于三角形的结构强化如何共同决定顶点重要性。本文的其余部分组织如下。第2节回顾了本工作中使用的张量初步知识。第3节定义αTEC并建立其主要理论性质。第4节在合成网络和真实世界网络上进行数值实验,并考察α对顶点排名的影响。第5节总结了主要发现并讨论了未来研究方向。

章节摘要

预备知识 设Cn表示n维复向量空间,C[k,n]表示k阶n维复张量空间。对于张量A = (ai1?ik) ∈ C[k,n]和向量x = (x1, …, xn)T ∈ Cn,定义Ayk-1 ∈ Cn的第i个分量为:

(Ay k-1)i = Σ(i2,…,ik=1→n) aii2?ik · xi2 · xi3 ? xik, i ∈ [n].

如果存在λ ∈ C和非零向量x使得Ay k-1 = λx[k-1],其中x[k-1] = (x1k-1, …, xn k-1)T,则称λ为A的特征值,x为对应的特征向量。A的谱半径ρ(A)定义为最大值……

α-三角形特征向量中心性 在正式定义中心性之前,我们首先介绍几个前提定义。设V?为顶点集的集合,其中每个顶点集包含三个互相连通的顶点,形成一个三角形。设[n] = {1, 2, …, n}。对于n个顶点的连通图G = (V(G), E(G)),其中V(G)和E(G)分别表示顶点集和边集,我们根据某些顶点的边邻域和三角形邻域定义边张量AE = (bijk)和三角形张量A? = (cijk)……

一些数值示例 在这里,我们介绍几种经典中心性度量。在以下实验中,我们将这些中心性度量下的顶点排名与α-三角形特征向量中心性(αTEC)下的排名进行比较。度中心性(DC)通过包含该顶点的边数来量化其重要性[5]。顶点的三角形中心性(TC)通过计算包含该顶点及其相邻顶点的三角形数来定义[6]。中介中心性……

结论 本文介绍了α-三角形特征向量中心性(αTEC),这是一种将成对边和三角形整合在单一非负三阶张量中的全局中心性度量。通过Perron特征向量定义中心性得分,保证了每个连通图存在唯一的且严格为正的中心性向量。我们还推导了所有顶点具有相同αTEC得分的充要条件。

数值实验表明,α控制……

作者贡献声明(CRediT) Qingying Zhang:撰写——初稿,可视化,方法论,概念构思。Lizhu Sun:撰写——审阅与编辑。Changjiang Bu:撰写——审阅与编辑。

利益冲突声明 作者声明不存在任何可能影响本文所述工作的已知竞争性经济利益或个人关系。

致谢 作者感谢Abbas Mohamed Sherif的讨论。本工作得到黑龙江省优秀青年科学基金(批准号:YQ2024A009)和中央高校基本科研业务费专项资金(批准号:2412025QD038和3072025YC2403)的资助。

Qingying Zhang | Lizhu Sun | Changjiang Bu
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号