文摘
大规模的社交图数据给社会带来重大挑战分析工具来监视和分析社交网络。信息理论的距离测量,即电阻距离,排名有影响力的节点或社区检测的重要参数。抵抗距离和基尔霍夫指数的优势是它可以反映图像的全局属性相当,并被广泛应用于评估图的连通性和鲁棒性。有各种措施的网络临界已经调查了底层网络,同时对相应的指标为混合网络。在本文中,我们提出了积极走算法构造的埃尔米特矩阵混合图,然后介绍耐埃尔米特矩阵和厄米基尔霍夫指数是基于厄米拉普拉斯算子矩阵的特征值和特征向量。与此同时,我们还提出了一个改进算法,直接遍历的算法,选择删除的边缘将最大化厄米基尔霍夫指数一般混合图。最后,我们比较结果与代数连接来验证提出的策略的优越性。
1。介绍
网络科学是一个新兴领域大数据,网络空间安全、和人工智能1- - - - - -4]。许多现实世界的网络混合,如引文网络,网页链接网络,电子邮件网络和信息传播网络。混合网络,就像底层,出现在可替换主体系统(5,6)、生物(7),和社会8]。提出了许多有效的算法来解决函数和混合网络的拓扑结构,如分散优化(9),节点异常检测算法(10[],嵌入算法11),和磁拉普拉斯算子12]。毫无疑问,进一步分析的混合网络已经成为不可或缺的网络科学和跨学科研究的话题。
1993年,克莱恩和Randić首次提出抗距离(13]。肖和古特曼14发现了一个电阻矩阵的一些性质。结合标准化的拉普拉斯算子矩阵和转移概率矩阵,陈和张15)提出了一种新的degree-Kirchhoff指数。Atik et al。16扩展电阻距离加权图。这一天,抵抗距离有许多重要的应用领域,如相变(17硅酸),网络(18)、电气网络(19,20.),和复杂网络21]。特征值和特征向量的计算相比,电阻距离作为度量的优点是,它更好地反映整个网络的性质,它可以减少在大规模网络中计算复杂度。尽我所知,距离耐药性的研究主要是进行减重和无向网络。很少有研究对阻力的距离在混合网络,这是本文的动机。本文的重点是建立一个新的距离度量阻力混合网络。
众所周知,阻力的研究距离从矩阵理论是分不开的。矩阵理论,包括埃尔米特邻接矩阵(22,23],拉普拉斯算子矩阵[24,25),非负矩阵分解(26),和条件概率矩阵27),是一个强大的工具来处理图拓扑结构和功能,因为它可以将复杂的计算转换为一系列的4个操作,它们容易提高计算性能。的基础上(23莫豪尔],[28)提出了第二种的埃尔米特矩阵。Yu et al。29日- - - - - -31日)一直致力于研究的埃尔米特谱理论混合图。基本图的扩展混合图实际上是一个扩展的真正领域复杂的领域。埃尔米特矩阵的重要性越来越突出。矩阵结构取决于图形的方向,所以,如何给图方向符合条件也是一个迫切需要解决的问题。埃尔米特矩阵的发展,越来越多的模型和策略提出了(32- - - - - -34]。Randic指数已广泛应用于网络中心,聚类算法,网络连通性和鲁棒性35- - - - - -37]。Meo et al。38通过Randic指数)估计图像的鲁棒性。埃尔米特矩阵的方向,我们试图引进厄米电阻矩阵和一般的混合图的基尔霍夫指数来估计混合图像的鲁棒性。
本文模拟基本图的拉普拉斯算子矩阵的伪逆矩阵,我们延长相应的可逆矩阵混合图。我们的主要贡献如下:(1)我们建议埃尔米特电阻矩阵和厄米基尔霍夫指数积极混合图,然后建立一个公式行列式和耐埃尔米特矩阵的逆(2)我们提出一个积极走一般的混合算法图(3)鲁棒性评估一般混合图的修改直接遍历的算法基于厄米基尔霍夫指数
本文的其余部分组织如下。部分1提出了相关工作的阻力矩阵和基尔霍夫指数。第二节介绍了埃尔米特拉普拉斯算子矩阵。在第三节,我们定义埃尔米特矩阵的抵抗力积极的混合图和计算它的行列式。在第四节,我们推导公式耐埃尔米特矩阵的逆。第五节特征的厄米基尔霍夫指数积极混合图。统计实验分析一般混合图所示第六节。第七节总结了纸。
2。埃尔米特拉普拉斯算子的矩阵
让是一个混合图和一个有限的顶点集和一个子集 。边集是无向边的结合和定向边缘。为了方便起见,我们定义的无向边 和导演的边缘 如果方向来 。的对角矩阵 度矩阵,在哪里的程度的基本图 。我们表示 。然后,埃尔米特矩阵如果吗 。埃尔米特混合图的邻接矩阵是矩阵 (22,23)的元素
混合走的价值 在是 。混合是积极的(消极的)如果走 ( )。
引理1。(见[30.])。混合图是积极的,当且仅当任意两个顶点吗 ,所有混合路径从来有相同的价值。
引理2。(见[31日])。让是一个连接图在顶点混合 。如果 是半正定矩阵和奇异,那么0是一个简单的特征值与特征向量: 在哪里是1 - - - - - -走在 。
埃尔米特的拉普拉斯算子特征值和正交特征向量将用和 ,分别。酉矩阵表示: 在哪里 。
然后,我们有 和 也就是说,
3所示。埃尔米特电阻矩阵在积极混合图
在本节中,我们建立了厄米电阻之间的关系矩阵和埃尔米特积极的混合图拉普拉斯算子矩阵。
引理3。(见[22])。让是一个复杂的图形。然后,以下是等价的:(1) 是一个积极的(2)
引理4。(见[30.])。让是一个积极的混合图。然后,以下语句:(1) ,在哪里邻接矩阵的谱吗(2) ,在哪里拉普拉斯算子矩阵的谱吗
然后,我们之间的关系建立的埃尔米特矩阵和相应的矩阵基本图的方向矩阵 。
引理5。(见[22])。让是一个积极的混合图顶点,和埃尔米特邻接矩阵和邻接矩阵,分别。为一个对角矩阵 ,我们有
推论1。让是一个积极的混合图顶点,埃尔米特拉普拉斯算子矩阵,是底层的拉普拉斯算子矩阵图。方向矩阵 ,我们有 。
现在,我们表示
因此,
矩阵 是满秩的,我们定义它的逆
同样的,我们有以下推论。
推论2。让是一个积极的混合图顶点, ,在哪里表示所有条目的平方等于1。然后,埃尔米特,
现在,我们将这个过程应用到电阻矩阵。
定理1。让是一个积极的混合图和是底层的电阻矩阵图;然后,埃尔米特矩阵
证据1。由定理3和电阻矩阵的定义,我们有 在哪里对角的成员吗 。
针对定理1,我们有 在哪里
因此,我们有 在哪里生成树的数量吗 。
4所示。耐逆的埃尔米特矩阵
在本节中,我们将展示,埃尔米特耐逆矩阵是满秩和推导公式。
为 ,我们定义的 向量 ,这样
定理2。让是一个积极的混合图顶点,埃尔米特的拉普拉斯算子矩阵联系在一起 。如果 和被定义为上面呢
证据2。让程度的顶点 。根据 ,我们有 然后, 因此, 现在,对于 ,我们有 因此, 。
现在,通过定理2,我们有
定理3。让是一个积极的混合图顶点。让和埃尔米特拉普拉斯算子矩阵和厄米电阻矩阵,分别。如果 向量 ,然后
证据3。由定理2,我们有 针对定理1,我们获得 也就是说, 然后, 以类似的方式, 最后, 应用公式(32)- (35),我们得到 很明显,是一个正定矩阵。
接下来,我们表明,埃尔米特电阻矩阵是满秩,并建立它们的倒数。
定理4。让是一个积极的混合图顶点。让和埃尔米特拉普拉斯算子矩阵和厄米电阻矩阵,分别。然后,是满秩和
证据4。由定理1,我们有 然后, 由定理1,是零。针对 ,存在一个非零的标量这样 也就是说, 因此, 因此,矩阵非奇异的, 。
5。厄米基尔霍夫指数积极混合图
在本节中,我们建立了厄米基尔霍夫指数的光谱以一种积极的混合图。
定理5。让是一个积极的混合图顶点。然后,厄米基尔霍夫指数
证据5。由定理1,我们有
6。实验分析厄米基尔霍夫指数一般混合图
根据引理5,我们建议积极走算法(参见算法1)给一个积极的方向对于一个给定的无向图 。
|
在现实世界中,并非所有的混合图是积极的。如果非奇异的,我们计算Moore-Penrose耐埃尔米特矩阵的广义逆埃尔米特拉普拉斯算子矩阵的混合图:
我们建立了厄米基尔霍夫指数的埃尔米特电阻矩阵在混合图。
定理6。让是一个混合图顶点。然后,厄米基尔霍夫指数
基尔霍夫指数有密切关系和网络的鲁棒性,例如,基尔霍夫指数越大,能力越低的网络功能在紧急情况下。基尔霍夫指数和网络的鲁棒性是负相关。此外,代数连接也被广泛用来衡量网络的鲁棒性;然而,代数连接与鲁棒性呈正相关。也就是说,代数连接性基尔霍夫指数负相关。接下来,我们将使用埃尔米特代数连接和厄米基尔霍夫指数来衡量一般混合图的鲁棒性,作为一个比较不同的鲁棒性措施。为了验证我们的建议的合理性和适用性,我们提出一个直接遍历的算法(参见算法2)获得边集从混合图的删除将最大化厄米基尔霍夫指数。然后,我们比较它与代数连接的结果。彭et al。39研究无向网图的鲁棒性。我们推广混合网格图随机图形。
|
我们把两个e - r图混合作为例子。建立了12分混合图如图1建立了34分和混合图如图2。然后,我们使用直接遍历的算法(参见算法2)来计算图中,我们显示在表的结果1。
7所示。结论
许多社交网络社区检测的策略被开发出来,其中基于电阻矩阵的谱聚类广泛应用于社区检测。在本文中,我们专注于积极的厄米电阻矩阵混合图和一般复杂的图表。埃尔米特电阻矩阵是一个泛化的电阻矩阵基本图形。此外,我们推导的公式行列式,耐埃尔米特矩阵的逆,得到厄米基尔霍夫指数。为了显示埃尔米特矩阵的实用性,我们利用厄米基尔霍夫指数来分析一般混合网络的鲁棒性。此外,我们提出了积极走算法和有向图遍历的算法。我们未来的工作将埃尔米特矩阵算法对矿业定向网络和社区检测的关键节点。
数据可用性
用来支持研究的数据都包含在这篇文章。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作部分是由中国国家自然科学基金(61977016和61977016号)、福建省自然科学基金(2017号。2020 j01164 j01738, JAT170118),中年和青年中国福建省教育部门(JAT200958号和JAT191119)和福建师范大学协和大学研究基金会(KY20200204号)。