没有合适的资源?快使用搜索试试~ 我知道了~
埃及信息学杂志(2021)22,339开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com全长文章最大团大小与中心性度量相关性的综合分析对于复杂网络图纳塔拉詹·梅加纳坦计算机科学,杰克逊州立大学,杰克逊,MS 39217,美国接收日期:2015年12月26日;修订日期:2016年3月24日;接受日期:2016年6月19日2016年9月6日翻译后摘要我们试图确定一个或多个计算重量轻的中心性指标,具有很高的相关性,与最大的集团大小(集团的最大大小的一个节点的一部分)-一个计算上在这个追求中,我们计算三个著名的测量评估两个数据集之间的相关性:基于积矩的皮尔逊相关系数,基于秩的斯皮尔曼相关系数和基于一致性的肯德尔相关系数。我们计算了随机网络图和无标度网络图以及一组度分布从随机到无标度的十个真实网络图的最大团大小与四个显著节点中心性度量(度、特征向量、介数和接近度)中的每一个之间的上述三个相关系数值我们还探讨了随机网络和无标度网络的理论模型的运行参数对最大团大小和中心性度量之间的相关性的影响©2021 THE CONDITOR. 由Elsevier BV代表计算机和人工智能学院出版开罗大学情报处。这是一篇CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/).1. 介绍网络科学(英语:Network Science)复杂网络分析(Complex Network Analysis)是大数据范式中的新兴感兴趣领域,并且对应于从图论的角度分析复杂的现实世界网络和基于理论模型的网络在用于复杂网络分析的各种度量中,节点中心性是一个突出使用的度量,电子邮件地址:natarajan. jsums.edu开罗大学计算机和信息系负责同行审查。理论价值和实践价值。节点的中心性是该节点相对于网络中其他节点的拓扑重要性的基于链路拓扑学的定量度量[1]。节点中心性度量的应用可以例如识别社交网络中最有影响力的人,互联网中的关键基础设施节点,疾病的超级传播者等。现有的中心性度量可以大致分为两类[1] : 基 于 邻 居 的 和 基 于 最 短 路 径 的 。 度 中 心 性(DegC)和特征向量中心性(EVC)[2]是基于邻居中心性的众所周知的度量,而介数中心性(BWC)[3]和接近中心性(ClC)[4]是基于最短路径中心性的众所周知的度量。Vari-http://dx.doi.org/10.1016/j.eij.2016.06.0041110-8665© 2021 THE CONDITOR.由Elsevier BV代表开罗大学计算机和人工智能学院出版。这是一个在CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。关键词复杂网络图;相关系数;中心性度量;最大团大小340N. 梅加纳坦我们的时间高效和空间高效算法(例如,[5,6])来确定上述中心性度量中的每一个。因此,我们将节点中心性称为计算上的轻量级度量。除了节点中心性之外,还有几种其他信息性度量用于定量评估复杂网络中节点的重要性,其中一些度量太耗时而无法确定。我们考虑这样的措施在本文中-最大团的大小为一个节点。一个节点的最大团大小被定义为该节点是其一部分的最大团大小[7]。图中的“团的大小是作为团的一部分的顶点的数量图中的每个节点可以是一个或多个不同大小的团的一个节点所属的最大规模的集团对于复杂网络中的社区检测是有意义顶点社区是图中顶点的子集,使得在该子集内的顶点之间有更多的链接,并且到该子集外的顶点的链接相对较少[1]。将网络划分为社区的有效性使用称为模块性得分的度量进行评估[8]。社区内的顶点数量越多,这些顶点之间的链接数量越多,社区的模块性得分就越大。因此,识别高度模块化的顶点并设计涉及这些顶点的社区检测算法是合乎逻辑的不幸的是,确定顶点的最大顶点大小的问题是NP-难的[7],我们将其称为计算上难的测度。人们将不得不依赖于耗时的精确算法或次优(但相对耗时较少)近似算法来确定顶点的最大团大小。此外,研究界的焦点主要集中在开发精确算法和近似算法(例如,[9一个或多个顶点的最大团大小可以对应于图的最大团大小,但并非所有顶点都可能是最大团的一部分。图中可能有几个顶点的最大团大小小于最大团大小。我们在本文中的贡献如下:我们试图确定一个或多个计算重量轻的中心性度量,具有较高的相关性,最大集团大小(计算困难的措施)。在这种追求中,我们为四个中心性度量(DegC,EVC,BWC和ClC)中的每一个运行最省时的算法,以及精确算法[9](最初为最大团大小提出)的适应版本,以确定复杂网络中顶点的最大团大小我们在随机网络和无标度网络上运行这些算法,这些网络分别由著名的我们使用三种众所周知的相关性度量[14]来评估节点的最大团大小与四个中心性度量中的每一个之间的相关性:(i)基于皮尔逊Dall's concordance相关系数我们还确定了具有最高相关性的中心性指标作为相对于随机网络和无标度网络以及十个复杂现实世界网络中的每一个的上述三个相关性度量中的每一个与最大团大小的最低相关性。我们还确定了相关措施,我们招致的最大和最小值的相关系数为不同的组合理论和现实网络的中心性度量。此外,我们还评估了理论模型的操作参数对四个中心性度量和最大集团大小之间观察到的相关性性质的影响。本文的其余部分组织如下:第2节回顾了相关的工作,涉及中心性指标和最大/最大集团大小的相关性研究。第三节介绍了图的最大团大小,并给出了确定最大团大小的一个第4节回顾了两个基于邻居的中心性度量(DegC和EVC)和两个基于最短路径的中心性度量(BWC和ClC),并简要描述了一个有效的算法来确定他们每个。第五节介绍了节点中心性与每个节点最大团大小相关系数的三种度量方法。第六节介绍了十个真实世界的网络图,并讨论了相关系数分析的结果.第7节和第8节分别给出了随机网络图(由第9节总结论文。在整个论文中,术语同样,顶点可以被称为i或vi。意思是一样的。我们将所有的理论模型生成的图和真实世界的网络图建模为无向图。2. 相关工作最近,我们发表了两篇文章[23,24],分析了复杂现实世界网络图的最大团大小与中心性度量之间的相关性这两篇文章仅限于使用基于皮尔逊积矩的相关性度量,并且仅分析了本文研究的十个真实世界网络中的六个。在本文中,除了皮尔逊的措施,我们还使用了其他两个相关性的措施(斯皮尔曼的排名为基础的和肯德尔的一致性为基础的措施),使我们能够确定最大的相关性最好的情况下和最坏的情况下的我们还扩展了分析的复杂网络池,包括从Erdos-Renyi(ER)模型(用于随机网络)和Barabasi-Albert(BA)模型(用于无标度网络)生成的理论网络,我们观察到,在ER模型下,关联水平可以直接与超临界和全连通演化区域中的随机网络状态相关联,在BA模型下,关联水平可以与次线性和线性连通演化区域中的无标度网络据我们最大团大小与中心性度量的相关性341然而,在随机网络和无标度网络中,还没有其他的工作报道最大团大小与中心性度量之间的在[23,24]和本文之前,研究人员仅孤立地分析了中心性度量和最大集团大小在[25,26]中,作者使用Pearson此外,中心性度量也被广泛研究,用于分析和可视化多个领域的复杂网络,从生物网络到社交网络[27,28]。关于单个顶点的最大团大小(顶点所属的最大团大小),在[29]中:在几个真实世界网络图以及小世界网络(在Watts-Strogatz模型[30]的演化下)中,顶点的最大团大小值的分布在文学的其他作品大多集中在开发有效的近似算法,以及精确的算法,以确定最大团大小(NP-难问题)的整个网络图。虽然分支定界是确定最大团大小的精确算法中的共同主题,但区别在于用于修剪搜索空间的方法:节点度[9],顶点着色[10]和顶点排序[11]。正如本文中所观察到的,节省时间(由于修剪)所招致的分支定界为基础的精确算法的最大团大小的整个图是在一定程度上丢失时,这些算法是适应于确定最大团大小的个别顶点由于确定图中顶点的最大团大小的精确算法的耗时性质,识别一个或多个计算上轻量的度量(如度中心性)变得势在必行,所述度量可以用于以与使用最大团大小获得的顺序几乎相同的顺序(如果不精确的话)3. 最大团大小节点的最大团大小是该节点所属的最大团大小。节点的最大团大小是节点的模块化水平的度量,并且可以用于识别社区可以围绕其进化的种子节点(对于社区检测算法)。尽管它的重要性-为了识别复杂网络中的高度模块化节点,文献中的大多数研究焦点都集中在称为最大团大小的相关度量上-图中最大团的大小。由于确定最大团大小和最大团大小的问题都是NP困难的[7],我们决定采用一种确定图中最大团大小的精确算法来确定图中顶点的最大团大小。我们选择Pattabiraman等人最近提出的精确算法。[9]用于确定图的最大团大小,并对其稍作修改以确定图中单个顶点的最大团大小。3.1. 确定图Pattabiraman等人的原始精确算法[9]遵循搜索所有可能的团并将探索仅限于其聚集范围大于到那时为止已知的最大团的大小的顶点的图1示出了用于最大团大小的精确算法的伪代码。可以注意到,该算法使用变量max来跟踪在搜索过程中确定的最大大小的团过程MAXCLIQUE在迭代中进行,并且在第i次迭代中,该算法探索是否可以确定大小大于max的当前值的团,其涉及顶点vi(顶点以其ID的递增顺序被考虑)及其邻居。对于每个这样的顶点Vi,构造涉及Vi的近邻(其度中的每个度至少是max的值)的顶点U的候选集合,并且将其与变量大小一起传递给子例程CLIQUE,在子例程执行期间的任何时间,变量大小的值表示直到那时为止已知的子例程CLIQUE通过迭代和递归的组合,每次用一个顶点(从vi本身开始)扩展涉及vi的团的大小。在每次这样的迭代中,从传递给子例程的集合U中移除随机节点u,并且过滤集合U以仅保留也是节点u的邻居的那些顶点;size的值递增1以说明将节点u包含到团中,并且使用更新的U和size的值递归调用CLIQUE。只要max的当前值小于图1确定图的最大团大小的精确算法(改编自[9])。342N. 梅加纳坦×我j1P比传递给子例程的集合U的大小和直到那时找到的当前团的大小在从递归调用返回的序列期间,还可能的是,vi的不同邻居节点u被选择,并且涉及新节点u及其邻居以及vi的团的大小可以大于max的当前值。此外,在对CLIQUE的任何此类递归调用期间,如果集合U的大小达到零,则算法终止递归序列,并且如果max的值小于直到那时发现的涉及顶点vi及其邻居的团的大小,则更新max该算法的效率受到迭代中考虑顶点的顺序的严重影响按照顶点度的降序对顶点进行标记比随机标记顶点更早地增加了找到最大大小团的机会[9]。如果在较早的迭代本身中找到最大大小的团,则如果在这些迭代中涉及的顶点具有小于直到那时确定的最大大小的团的度,3.2. 确定顶点最大团大小图2示出了我们提出的用于确定给定图中任何顶点的最大 团 大 小 的 修 正 精 确 算 法 的 伪 代 码 。 与 MAXI-MUMCLIQUE过程(在3.1节中讨论过)不同,我们不能再丢弃度低于整个图的最大团大小的顶点。 我们需要为每个顶点运行该过程,以确定涉及该顶点的最大团大小。对于每个顶点vi,首先,直到那时为止已知的最大团大小为0;因此,我们构造包含vi的所有邻居的候选顶点集(U),并将它们传递给子例程CLIQUE。我们可以在子例程CLIQUE中保留所有的修剪策略(在3.1节中讨论过):如果节点u(从集合U中选择)及其邻居的度小于到那时为止已知的size值(涉及顶点vi的最大团大小),则我们不为为了加速,我们列出了从过程MAXIMAL CLIQUE传递到子例程CLIQUE的初始集合U中的顶点vi的邻居,这些邻居的度从高到低。图3给出了一个示例,以说明执行修改的精确算法来确定顶点的最大团大小。我们认为顶点v i=4是我们想要找到最大团大小的顶点。我们用一个唯一的标识号来标识对子例程CLIQUE的每个递归调用(调用#1、2等)。从而易于跟踪算法执行。前几个递归调用(调用#s 1-2-3-4)导致识别大小为3的团{4,2,3}。但是,下一组递归调用(调用#s:1-5-6-7)导致涉及顶点4的最大大小团{4,5,6,7}的识别。图4示出了图1中使用的样本图中的所有顶点的最大团大小。 3.4. 节点中心性度量我们现在回顾一下本文所研究的用于相关系数分析的中心性度量这些是基于邻居的度中心性(DegC)和特征向量中心性(EVC)度量以及基于最短路径的介数中心性(BWC)和接近中心性(ClC)度量。4.1. 程度中心性一个顶点的度中心度是该顶点在图中的邻居数,可以通过计算入射到该顶点上的边数来计算。如果A是一个图的n n邻接矩阵,使得A[i,j]=1,如果有一条边连接v i和v j(对于无向图),并且A[i,j]= 1,j]=0,如果没有边连接v i和v j。顶 点vi的 度中 心性 定量 定义 如下:DegC(v) =nA½i;j]. 图 五是考试题--图的邻接矩阵与对应于图中顶点数的单位列向量1的乘积作为图中所有顶点的度中心度的计算方法图2确定顶点最大团大小的精确算法(改编自[9])。最大团大小与中心性度量的相关性343×图3示例说明执行精确算法以确定顶点的最大团大小图4样本图中顶点的最大团大小4.2. 特征向量中心性一个顶点的特征向量中心度(EVC)是该顶点的度以及它的邻居的度的定量度量。对于自身具有高度数并且位于高度数顶点的邻域中的顶点可能具有较大的EVC。图中顶点的EVC值对应于图的邻接矩阵的主特征向量中的顶点的条目一个n-n邻接矩阵有n个特征值和相应的特征向量。主特征向量是特征向量,对应于邻接矩阵的最大特征值(主特征值),A.此外,如果方阵中的所有条目都是正的大于或等于零),主特征值以及主特征向量中的条目也是正的[15]。我们使用幂迭代方法[15]确定顶点的EVC。 根据这种方法,我们从单位向量X0=[1 1 1 1. . 11],并经历一系列迭代。在第(i + 1)次迭代期间计算的暂定特征向量如下给出:||A X i||得双曲余切值.||A X i||是由邻接矩阵和在第i次迭代期间计算的临时特征向量的乘积产生的向量的归一化值。我们继续迭代,直到标准化值||A X i||不会发生显著变化,并收敛到一个常数值(四舍五入到小数点后第二位时)。此时的归一化值也对应于邻接矩阵的主特征值,并且利用该归一化值计算的试验特征向量对应于邻接矩阵的主特征向量。我们用图6所示的例子来说明幂迭代方法的执行。如在图6中可以注意到的,即使顶点4和顶点6都是相同的,图5说明度中心性计算的示例。344N. 梅加纳坦-图6使用幂迭代法计算特征向量中心性的示例5具有相同的较大度(5)-顶点4的EVC大于顶点5的EVC-这可以归因于顶点4的邻居的度分布{3,3,3,4,5}相对于邻居的度分布{3,3,3,2,5}顶点54.3. 中介中心性一个顶点的介数中心性(BWC)是在所有顶点对上考虑的任何两个顶点之间通过该顶点的最短路径的分数之和。在本文中,我们使用著名的Brandes算法[5]的宽度优先搜索(BFS)-变体来确定顶点的BWC我们在图中的每个顶点上运行BFS算法,并确定每个BFS树中每个顶点的级别(从根开始的跳数/边数)。一棵BFS树的根在0级,从根到它自己的最短路径数是1。在以顶点r为根的BFS树上,顶点i在第l层的最短路数(l>0)是从根r到顶点i的每个邻居的最短路径的数目之和(在原始图),其在BFS树中的级别11处因为我们是在无向图上工作,所以从顶点i到顶点j的最短路径的总数(记为spij)只是以顶点i为根的最短路径树中从顶点i到顶点j的最短路径的数量,反之亦然。从顶点i到顶点j经过顶点k的最短路径的数目(记为spij(k))是在以i为根的最短路径树中从顶点i到顶点k的最短路径的数目和在以顶点j为根的最短路径树中从顶点j到顶点k的最短路径的数目中的最大值。以占据任意两个顶点之间的最短路径的相对较大的部分,并且与顶点4相比引起相对较大的BWC值(即使顶点4具有较大的EVC值)。此外,即使顶点3具有比顶点1更大的度数,顶点1的BWC也显著大于顶点3的BWC。这可以归因于顶点1位于从顶点0和2到顶点4、5、6和7的最短路径上;另一方面,顶点3仅位于2和5之间的最短路径上。4.4. 接近中心性一个顶点的贴近中心度(ClC)是从该顶点到图中所有其他顶点的最短路径之和的倒数我们通过在每个顶点上运行BFS算法并对这些BFS树中从根顶点到每个其他顶点的最短路径的数量求和来确定顶点的CLC图8示出了计算顶点的CIC我们观察到具有较大度的顶点更可能具有到其余顶点的较低跳数的最短路径,从而导致较大的CLC值。5. 相关系数测度我们现在讨论三个众所周知的相关系数度量,它们用于评估最大团大小与第4节中提出的四个中心性度量之间的相关性。这些是基于乘积矩的Pearson很好。所有这三个指标都评估程度因此,BWC(k)=Pkksp.i.j.国际新闻社两个数据集或性能图7示出了计算ver-BWC的示例。图中使用的同一图表中的Tices。三比六我们可以观察到顶点0、6和7的介数值都是零,因为任何两个顶点之间都没有最短路径经过它们。我们观察到,即使顶点4和5具有相同的较大度,顶点5的邻居的平均度也略低于顶点5的邻居因此,顶点5更有可能度量(在我们的情况下,最大集团大小和四个中心性度量中的每一个)[14]。对于所有三个测量值获得的相关系数值范围为-1到1。接近于1的相关系数值对于两个度量中的一个具有较大值的顶点更可能对于另一个度量也具有较大值),而接近-1的值指示最大团大小与中心性度量的相关性345图7介数中心度计算示例图8说明接近中心度计算的示例更强的负相关(即,对于两个度量之一具有较大值的顶点更可能对于另一度量具有较小值接近0的相关系数值由顶点引起的两个度量的值彼此独立)。我们将采用Evans[16]提出的范围(四舍五入到两位小数)来表示各种相关性水平表1所示用于各种相关性水平的颜色代码也显示在该表中。为了简单起见,我们将两个数据集分别称为M和C,分别对应于最大团大小和中心性。 我们将使用图的结果。图4 -8 示 出 了 在 三 个 测 量 中 的 每 一 个 下计算相关系数的示例。346N. 梅加纳坦-ð Þ ¼ - 你好6Pd-表1相关系数值的范围和相应的相关水平。5.1. 皮尔逊两个数据集的基于皮尔逊积矩的相关系数定义为两个设Mavg和Cavg表示n个顶点的图的最大团大小和中心性度量的平均值,设Mi和Ci分别表示顶点i的最大团大小和中心性度量的值.皮尔逊相关系数(指示PCC)定量地定义为如等式(1)中所示。(一).术语乘积矩与公式分子中两个度量的平均(一阶矩)调整值的乘积相关。图9呈现了针对图1和图2中使用的示例图获得的最大团大小(M)和度中心性(C)值的PCC的计算。三比八我们获得的相关系数值为0.5(见图9),表明示例图的两种度量之间存在中度正相关。为n个顶点的图分配从1到n的秩值,即使顶点ID的范围从0到n1。为了根据性能指标的值列表获得顶点的排名,我们首先对值进行排序(按升序)。如果有任何平局,我们打破平局,支持具有较低ID的顶点;因此,我们将能够获得每个顶点相对于每个度量的暂定但唯一的秩值。我们确定顶点的最终排名如下:对于具有唯一性能度量值的顶点对于性能度量值相同的顶点,最终排名将被指定为其暂定排名的平均值图10示出了在图11和图12中使用的示例图中基于顶点的最大团大小和度中心性值来计算顶点的试验性和最终排名。图3-9以及示出了Spear-man的基于等级的相关系数的计算。n2SCC M;C111:2nn2-1PnM-MÞðC-CÞi¼iavgiavg1PCCM;CqPð1Þi¼1Mi-M avgi¼1Ci-Cavg5.2. SpearmanSpearman为了计算两个数据集M和C的SCC,我们将顶点i的原始分数Mi和Ci转换为秩Mi和Ci,并使用下面所示的公式(2),其中di=mi c i是两个数据集中顶点i的秩之间的差。我们遵循教会-图 10,我们观察到顶点之间的联系,最大团大小和度中心性。帐篷-通过打破有利于具有较低ID的顶点的联系来获得主动排名在最大团大小(M)的情况下,我们观察到4个顶点0 -3具有相同的M值3,它们的暂定排名是1-4;这4个顶点中的每个顶点的最终排名(2.5)因此是1,2,3和4的平均值。同样,四个顶点4 -7具有相同的M值4,它们的暂定排名是5-8;因此,这四个顶点中的每一个的最终排名(6.5)是5、6、7和8的平均值。在度中心性(D)的情况下,我们观察到度为3的顶点之间的联系(暂定排名为2,4和5;最终排名:3.5 -平均为2,4和5),图9示例说明Pearson相关系数的计算最大团大小与中心性度量的相关性3472ð Þ ¼ ð Þ图10示例说明斯皮尔曼相关系数的计算度为5的顶点(暂定排名为7和8;最终排名:7.5-平均为7和8)。 斯皮尔曼的基于排名的相关系数(SCC)计算的最大集团大小和度中心的示例图使用图。 3- 9是0.565。我们观察到SCC值略大于图9中获得的PCC值,但是,两种测量的相关性水平仍然落在适度正相关的范围内。5.3. Kendall任何两个性能指标(比如M和C)的肯德尔一致性相关系数(Kendall'sconcordancebasedcorrelationcoefficient,KCC)是相似性的度量(也称为相似性度量)。一致性)在图[14]中的顶点所引起的度量值的排序中。我们定义一对不同的顶点vi和vj为协调的,如果{Mi>Mj和Ci>Cj}或{MiMj和CiCj}。<<换句话说,如果这两个顶点中的任何一个顶点严格地具有与另一个顶点相比更大的两个度量M和C的值,则这对顶点vi和vj我们定义一对不同的顶点vi和vj为不协调的,如果{Mi>Mj和CiCj}或{MiMj和Ci>Cj}。<<换句话说,如果顶点对于两个性能度量中的仅一个具有较大值,则顶点对vi和vj是不一致的如果{Mi=Mj}或{Ci=Cj}或{Mi=Mj且Ci=Cj},则一对不同的顶点vi和vj既不协调也不基于Kendall对于n个顶点的图,如公式(3)所示计算KCC。KCC M;C#conc:pairs-#disc:pairs:31nn-1图11示出了图11和图12中使用的示例图的最大团大小和度中心之间的肯德尔修正系数的计算。三比九一个图在8个顶点中,可以考虑的不同对的总数是8(8 -1)/2= 28,并且在这些中,10对被分类为一致的,2对被分类为不一致的。其余16对在图中既不一致也不不一致(表示为N/A)。我们得到一个相关系数0.286,属于弱正相关范围,低于相关系数值(下降在适度正相关的范围内)与皮尔逊我们还观察到KCC在我们所有的理论和现实复杂网络实验中返回最低的相关系数值(第8节)。因此,KCC可以被解释为提供相关系数值的下限和最大团大小与所考虑的中心性度量之间的相关性水平。6. 真实世界网络图我们考虑了一套十个真实世界的网络图,我们的相关性分析。我们在下面列出并识别这些图表以节点度变化的递增顺序,以称为谱半径比的度量的形式捕获对于节点度(表示为ksp)[17]。图的结点度谱半径比是图的邻接矩阵的主特征值与平均结点度的主特征值之比。ksp值始终大于或等于1.0。值越大,节点度的变化越大。本文中考虑的真实世界网络的ksp从随机网络到无标度网络)。 随机网络呈现出泊松式的度分布,节点度的变化较小;它们的ksp值通常接近1.0。无标度网络的节点度变化更大(特别是像美国机场网络这样的网络,一些枢纽-高度节点,其余节点是程度相对低得多)-导致较大的Ksp值。下面简要介绍真实世界的网络图[18-我们还用它们的ID(范围从1到10,如下所列)以及两个字符的缩写来识别这些网络-与ksp值一起列出。(1) 美国橄榄球网络(FN;ksp= 1.01):这是一个由115支美国大学橄榄球队(节点)组成的网络,这些球队在2000年秋季赛季进行了比赛;如果相应的球队在过去至少有一次比赛,那么两个节点之间就有一条边(2) 海豚网络(DN;ksp= 1.40):这是一个由62只海豚(节点)组成的网络,它们生活在新西兰的怀疑峡湾;如果在观察期间看到相应的海豚相互移动,那么两个节点之间就会有一条边。348N. 梅加纳坦图11 Kendall相关系数的计算示例(3) US Politics Book Network(PN;ksp= 1.42):这是一个由105本在Amazon.com上出售的与美国政治相关的书籍(节点)组成的网络;如果购买两本书中的一本的客户也购买了另一本书,则两个节点之间存在边缘,反之亦然。(4) 空手道网络(KN;ksp= 1.47):这是20世纪70年代美国大学空手道俱乐部的34名成员(节点)的网络;如果在观察期间看到相应的成员相互作用,则两个节点之间存在边缘(5) C. Elegans神经网络(NN;ksp= 1.68):这是一个由两性小杆线虫神经网络中的297个神经元(节点)组成的网络;如果相应的神经元相互作用(以化学突触,间隙连接和神经肌肉接头的形式),则两个节点之间存在边缘。(6) 单词邻接网络(WN;ksp= 1.73):这是查尔斯·狄更斯的小说《大卫·科波菲尔》中的112个形容词和名词(节点)(7) 悲惨世界网络(LN;ksp= 1.82):这是小说《悲惨世界》中77个角色(节点)的网络;如果相应的角色在小说中至少一个章节中一起出现,则两个节点之间存在边。(8) 引文图绘制网络(CN; ksp=2.24):这是一个由311篇论文(节点)组成的网络,这些论文发表在1994年至2000年的图表绘制(GD)会议论文集上,并被GD'2001会议发表的论文引用。如果其中一篇论文引用了另一篇论文作为参考,则两个节点之间存在边缘。尽管这个网络被建模为有向图,为了简单和与所考虑的其余网络的一致性,我们将该网络建模为无向图。(9) Erdos Collaboration Network(EN;ksp= 2.28):这是一个由472位作者(节点)组成的网络,他们要么直接与Paul Erdos一起发表文章,要么通过一系列合作者与Paul Erdos合作。如果对应的作者共同创作了至少一个出版物,则在两个节点之间存在边(10) 美国机场网络(AN:ksp=3.22):这是1997年美国332个机场(节点)的网络。如果在相应的机场之间存在直飞连接,则在两个节点之间存在边。表2给出了基于PCC、SCC和KCC测量的最大团大小和四个中心性度量中的每一个获得我们根据表1中列出的颜色代码对这些表中的相关性水平进行颜色编码。整体走势最大团大小与中心性度量的相关性349表2真实世界网络图的最大团大小和中心性度量之间的相关系数值。表2中显示的结果是,与基于最短路径的中心性度量(介数和接近中心性)相比,基于邻居的中心性度量(度中心性和特征向量中心性)表现出相对更强的正相关性在三个相关性度量中的每一个下,对于每个中心性度量,观察到十个真实世界网络中的至少九个的相关系数值是正的。关于节点度的谱半径比的相关性随值增加的趋势,我们观察到总体趋势是最大团大小和中心性度量之间的相关性强度随节点度变化的增加因此,由于现实世界的网络相对更无标度(这是现实中的情况),我们可以期望看到最大团大小和中心性度量之间的更好的强相关性,至少对于基于邻居的中心性度量。度中心性与最大集团大小之间存在强-非常强的正相关关系,在Pearson测度下,10个真实网络中有8个网络的度中心性与最大集团大小之间存在强-非常强的正相关关系,在Spearman测度下,10个网络中有9个网络的度中心性与最大集团大小之间存在强-非常强的正相关关系即使使用Kendall方案,我们也观察到度中心性对于十个网络中的四个网络表现出适度的正相关性,并且对于十个网络中的另外四个网络表现出强-非常强的正相关性。 在Pearson和Spearman相关系数测度下,10个真实网络中有7个的特征向量中心性表现出强-非常强的正相关性,在Ken- dall相关性测度下,10个网络中有5个的特征向量中 心 性 表 现 出 中等正相关性。基于最短路径的中心度度量的最佳情况下的性能是一个强-非常强的正相关性为5 - 6的十个现实世界的网络下斯皮尔曼的相关系数的措施。基于最短路径的中心度量在Kendall相关性测度下,与现实世界中10个最大团的大小有5 - 7个呈现出非常弱的负-弱正相关性.总体而言,我们可以说介数中心性与最大团大小的相关性最弱。在Pearson相关性测度下,我们观察到介数中心性对于十个网络中的五个网络表现出弱-非常弱的正相关性,对于随机网络型美国足球网络,与十个网络中的四个网络表现出适度的正相关性,并且表现出非常弱的负相关性。相对而言,接近中心性似乎表现出更好的相关性,具有最大团大小的lation。在Pearson和Spear-man的相关性度量下,10个真实世界网络中至少有5个的紧密中心性度量表现出强-非常强的相关性从图12中,我们观察到Pearson和Spearman的相关系数测量在最大团大小和三个中心性度量之间产生更高的相关系数值,除了介数中心性。同样,我们观察到肯德尔的相关系数测量作为最大集团大小和三个中心性度量之间的相关性的下限,除了介数中心性。对于介数中心性,我们观察到Pearson的相关系数对于大多数真实世界的网络来说是相对最低的,而Spearman的相关系数似乎是相对最大的。关于在三种测量下相关系数值的接近性(这可以通过检查数据点是否位于图12所示的曲线中的对角线上或对角线附近来确定),我们观察到,当用于评估最大团大小与本征向量中心性之间的相关性以及最大团大小与接近中心性之间的相关性时,Pearson另一方面,我们观察到的皮尔逊基于上述讨论,并从图1中的数据点的分布, 13,我们可以自信地得出结论,对于本文分析的大多数真实世界网络,在所有三种相关性度量下,度中心性度量与最大集团大小表现出最强的相关性。在图13中,我们观察到对应于特征向量中心性和接近中心性的大多数数据点在针对三个相关性度量中的每一个的度中心性由于介数中心性在所有情况下都导致相关系数的最小值,因此我们在这些图中没有使用BWC度量。7. 随机网络图在本节中,我们讨论了我们的相关性分析研究的结果,最大集团大小与。上的中心性指标350N. 梅加纳坦最大团大小与度中心性最大团大小与特征向量中心性最大团大小与中间中心性最大团大小与紧密中心性图12真实网络的相关系数值分布(从相关性度量的角度)。皮尔森相关性度量(Pearson 's Correlation Measure)图13真实世界网络的相关系数值分布(从中心性度量的角度)从著名的Erdos-Renyi(ER)模型生成的随机网络图在ER模型下,网络中任何两个节点之间都可能存在链接,概率为p。我们对100个节点的网络进行模拟,并将p链路值从0.01变化到0.50。对于每个p 链 接值,我们运行100次模拟,并对三个相关性度量中的每一个下的每个中心性度量的具有最大队列大小的相关系数的结果进行平均。对于给定的p链接值,我们考虑网络中的所有节点对,并在任意两个节点之间建立链接,如果随机数(范围为0. .1)为节点对生成的链路小于或等于p。p链接值越大,随机网络中生成的链接数量越多,节点度的变化越小(根据节点度的谱半径比测量)。对于固定数量的节点,具有更大数量的链路,网络的鲁棒性(关于由于链路故障而断开)也增加(如根据网络的代数连通性所测量的)。连通网络的代数连通度[21]是网络的拉普拉斯矩阵[14]的第二小特征值图14 ER模型graph.如果A和D分别是图的邻接矩阵和度矩阵,则拉普拉斯矩阵L是简单的A-D。 度矩阵也是一个方阵,其非对角元素全为零,对角元素对应于顶点的度。从图14中,我们观察到节点度的谱半径比随着p链路的增加而急剧下降(幂律式下降),而代数连通性则表现出中等的速率随着p链接的增加而增加。最大团大小与中心性度量的相关性351≈最大团大小与度中心性最大团大小与特征向量中心性最大团大小与中间中心性最大团大小与紧密中心性图15基于ER模型的随机网络的相关系数值分布(从相关性度量的关于所使用的相关性测量,从图15中,我们观察到Spearman的基于等级的相关性和Ken dall的基于一致性的相关性测量分别用作相关性水平的上限和下限。所有四个中心性度量在Pearson和Spearman相关性度量下产生相对更接近的相关系数值在真实世界网络的情况下,在所有三个相关性度量下,中间中心性导致最小的相关系数值因此,当我们仅绘制在特定相关性测量下的三个中心性度量的相关系数值时(图16),对于p个链路值大于或等于0.05(称为全连接状态:参见下面的讨论),我们观察到DegC、EVC和ClC与最大团大小的相关性水平的差异可以忽略不计,其中EVC引起稍大的相关系数值(对于p个链路P 0.1,最大差异在0.05内)。从图15中,我们观察到,对于具有从0.05开始的p个链接值的随机网络,相关性水平(对于任何中心性度量,在任何三个相关性测量)充其量是适度正的。度中心性和接近中心性度量对于范围为以下的p个链接值表现出强-非常强的正相关性(相关性水平随着p个链 接的增加而降低):0.01到0.04(当节点度的变化较大并且网络的连通性较低时的情形)。对于范围从0.01到0.04的p个链接值,特征向量中心性度量表现出弱-中等正相关性(相关性水平随着p个链接增加而增加),并且对于大于或等于0.04的p个链接0.05.与对于p个链接值大于或等于0.1观察到的相关性水平相比,介数中心性度量对于p个链接值0.01至0.09表现出相对较高的相关性水平因此,对于四个中心性度量中的至少三个,从相对较高或较低水平的正相关性到最多适度正相关性水平的转变(此后保持不变)发生在p link值为0.05时(对于n=100个节点的网络,p link=0.05 - ln(n)/n),这可以被称为随机网络被认为处于完全连接状态的临界概率[22],并且具有没有孤立节点或集群的单个巨型分量。 对于p链路P1/n(即, plinkP 0.01 for n=100 nodes)和p link
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- BSC绩效考核指标汇总 (2).docx
- BSC资料.pdf
- BSC绩效考核指标汇总 (3).pdf
- C5000W常见问题解决方案.docx
- BSC概念 (2).pdf
- ESP8266智能家居.docx
- ESP8266智能家居.pdf
- BSC概念 HR猫猫.docx
- C5000W常见问题解决方案.pdf
- BSC模板:关键绩效指标示例(财务、客户、内部运营、学习成长四个方面).docx
- BSC概念.docx
- BSC模板:关键绩效指标示例(财务、客户、内部运营、学习成长四个方面).pdf
- BSC概念.pdf
- 各种智能算法的总结汇总.docx
- BSC概念 HR猫猫.pdf
- bsc概念hr猫猫.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)