【图论】节点的几种中心性

这篇具有很好参考价值的文章主要介绍了【图论】节点的几种中心性。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

参考资料:https://www.ultipa.cn/document/ultipa-graph-analytics-algorithms/degree/v4.0


本文主要内容是介绍图分析相关的概念与算法

中心性

节点度(Degree)

概述

节点度算法为每个节点计算与其相连的边的数量;当边上有权重时,则计算权重的总和。节点度是面向节点的浅层(≤ 1层)计算,是一种最简单、最高效的图算法,在科学计算、特征提取、超级节点识别等领域扮演着至关重要的角色。

基本概念

度的方向
节点的出边的数量称为节点的出度,节点的入边的数量称为节点的入度。如果忽略边的方向计算所有边的数量,就得到节点的度(或度中心性)。
接近中心性,图论
上图中红色节点的出度为 3,入度为 4,度为7。需要注意的是,有向的自环边会被看作一条出边和一条入边。

边权重
边权重可以是边的某一个属性值。指定了边权重时,节点度就是边权重的和;不指定边权重时,节点度也可以理解为所有边的权重均为 1 时的节点度。
接近中心性,图论
边加权后,上图中红色节点的出度为 1 + 0.2 + 2 = 3.2,入度为 0.5 + 0.3 + 2 + 1 = 3.8,度中心性为 3.2 + 3.8 = 7

特殊处理

孤点、不连通图
由于没有连接其他节点的边,孤点的节点度完全取决于其自环边。

自环边
自环边会被看作一条出边和一条入边。

有向边
有向边的方向是计算节点出度和入度的依据;计算度中心性时则会忽略边的方向。


接近中心性(Closeness Centrality)

接近中心性用来衡量节点在其连通分量中到其它各点的最短距离的平均值。该概念可以帮助选出连通分量内距离各点最近的点,因而被广泛用于关键社交节点发现、功能性场所选址等应用场景。
接近中心性,图论
接近中心性的取值范围是 [0,1],数值越大越靠近中心。

接近中心性在实际应用中有着多种定义,其原始概念是由 Alex Bavelas 于 1950 年提出的,相关资料如下:

  • A. Bavelas, Communication patterns in task-oriented groups (1950)

调和中心性(Harmonic Centrality)

调和中心性算法是接近中心性算法的变种。接近中心性衡量的是节点在其连通分量中到其它各点的平均最短距离,显然在不连通图中就无法体现节点在全图的中心性;调和中心性提出的“平均最短距离”则是对这些最短距离的倒数求和,这使它可以处理非连通图中会出现的无限值。调和中心性算法首先是由 M. Marchiori 和 V. Latora 于 2000 年提出的,然后由 A. Dekker 和 Y. Rochat 分别于 2005 年和 2009 年提出。
接近中心性,图论

调和中心性的取值范围是 [0,1],数值越大中心性越大。

算法的相关资料如下:文章来源地址https://www.toymoban.com/news/detail-765691.html

  • M. Marchiori, V. Latora, Harmony in the Small-World (2000) A. Dekker,
  • Conceptual Distance in Social Network Analysis (2005) Y. Rochat,
  • Closeness Centrality Extended to Unconnected Graphs: The Harmonic Centrality Index (2009)

图中心性(Graph Centrality)

图中心性用来衡量节点在其连通分量中到其它各点的最短距离的最大值。该概念与其它概念(如接近中心性、图直径等)一起可以综合判定一个点是否从真正意义上位于图的最中心。
接近中心性,图论
图中心性的取值范围是 [0,1],数值越大越靠近中心。
在接近中心性相同时,图中心性可作为判断哪个节点更靠近中心的辅助依据。


中介中心性

中介中心性(Betweenness Centrality)用来衡量点处于其它任意两点间最短路径之中的概率。该概念由 Linton C. Freeman 于 1977 年提出,能有效地计算出在图的多个部分间起重要桥梁、媒介作用的点。
接近中心性,图论
中介中心性的取值范围是 [0,1],数值越大中介作用越强。

相关资料如下:

  • L.C. Freeman, A Set of Measures of Centrality Based on Betweenness(1977)
  • L.C. Freeman, Centrality in Social Networks Conceptual Clarification (1978)

特征向量中心性(Eigenvector Centrality)

特征向量中心性算法度量的是节点影响的传递。来自高分值节点的关系对节点分值贡献大于来自低分值节点的关系,节点有高分值意味着它连接到许多高分值节点。特征向量中心性强调节点所处的周围环境,例如在疾病传播中,特征向量中心性较大的节点距离传染源更近的可能性更大,需要格外防范。

Google 著名的 PageRank 算法是特征向量中心性算法的一个变种,用来进行网页排名。

特征向量中心性的取值范围是 [0,1],数值越大中心性越大。


CELF

CELF(Cost Effective Lazy Forward,具有成本效益的惰性前向选择)算法可以在一个有传播行为的网络中选取一些种子节点作为传播源头,以达到影响力最大化(Influence Maximumization, IM)的效果。CELF 算法由 Jure Leskovec 等人于 2007 年提出,它改进了传统基于 IC 模型的贪心算法,利用函数次模性,只在初始时计算所有节点的影响力,之后不再重复计算所有节点的影响力,因此具有更高的成本效益。CELF 算法的一个典型应用场景是预防流行病爆发,通过选择出一小组人进行监测,从而达到任何疾病在爆发的早期就能被发现的效果。

算法的相关资料如下:

  • J Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance, Cost-effective Outbreak Detection in Networks (2007)
  • D. Kempe, J. Kleinberg, E. Tardos, Maximizing the Spread of Influence through a Social Network (2003)

相似性(施工中)

杰卡德相似性

重叠相似度

余弦相似度

皮尔森相关系数

欧几里得距离

到了这里,关于【图论】节点的几种中心性的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • js几种打印方法的几种方法

    1. 引入插件: 首先,在您的 HTML 文件中引入 printJs 库。可以通过在 head 标签中添加以下代码来引入库文件: 这将从 CDN 加载 printJs 库的 JavaScript 文件和 CSS 文件。 2. 创建打印按钮: 在您的 HTML 文件中创建一个按钮,用于触发打印操作。例如: 3. 添加打印事件监听器: 在您的

    2024年02月13日
    浏览(52)
  • 【单源最短路 图论】882. 细分图中的可到达节点

    视频算法专题 单源最短路 图论 给你一个无向图(原始图),图中有 n 个节点,编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链,每条边之间的新节点数各不相同。 图用由边组成的二维数组 edges 表示,其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在

    2024年04月10日
    浏览(42)
  • 常见的几种排序

    🐶博主主页: @ᰔᩚ. 一怀明月ꦿ  ❤️‍🔥 专栏系列: 线性代数,C初学者入门训练,题解C,C的使用文章,「初学」C++ 🔥 座右铭: “不要等到什么都没有了,才下定决心去做” 🚀🚀🚀大家觉不错的话,就恳求大家点点关注,点点小爱心,指点指点🚀🚀🚀 目录 冒泡

    2024年02月15日
    浏览(41)
  • 常见的几种排序方式

    排序: 所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作 稳定性: 假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在

    2024年02月07日
    浏览(48)
  • python的几种输出方式

    1.输出百分比方法 2. print(f “{}”) 的用法 3. .format格式   4. 加号拼接(针对字符串) 扩展知识 -格式化输出 字符 含有 %s 字符串 %d 有符号十进制整数,%06d表示输出的整数显示位数字,不足的地方使用0补全 %f 浮点数,%.02f表示小数点后只显示两位 %% 输出%  %s:代表字符串的占

    2024年04月15日
    浏览(52)
  • 创建线程的几种方式

    线程和进程的区别: 进程是操作系统进行资源分配的最小单元。 线程是操作系统进行任务分配的最小单元,线程隶属于进程。 如何开启线程? 1、继承Thread类,重写run方法。 2、实现Runnable接口,实现run方法。 3、实现Callable接口,实现call方法。通过FutureTask创建一个线程,获

    2024年02月03日
    浏览(58)
  • 常见的几种排序算法

    目录 一、插入排序 1、直接插入排序 1.1、排序方法 1.2、图解分析 1.3、代码实现 2、希尔排序 2.1、排序方法 2.2、图解分析 2.3、代码实现 二、选择排序 1、直接选择排序 1.1、排序方法 1.2、图解分析 1.3、代码实现 2、堆排序 2.1、排序方法 2.2、图解分析 2.3、代码实现 三、交换

    2024年02月09日
    浏览(47)
  • 生成矩阵的几种方法

    生成矩阵的几种方法 在 MATLAB 中,生成矩阵有许多种方法。下面介绍几种比较常用的方法。 使用 zeros 或 ones 函数 可以使用 MATLAB 中的 zeros 或 ones 函数来创建一个特定大小的全零或全一矩阵。这两个函数的语法如下: 其中,m 和 n 分别表示矩阵的行数和列数。例如,要创建一

    2024年02月04日
    浏览(49)
  • 空间直线的几种方程

    两相交平面方程组联立 由对称式方程导出: 把两个平面法向量叉乘得到 方向向量,然后取一点即可。

    2024年02月15日
    浏览(43)
  • redis的几种集群方式

    https://www.zhihu.com/people/pan-zhi-74-31 Redis集群介绍Redis集群一般有四种方式,分别为:主从复制、哨兵模式、Cluster以及各大厂的集群方案。在3.0版本之前只支持单实例模式,3.0之后支持了集群方式。在3.0之前各大厂为了解决单实例Redis的存储瓶颈问题各自推出了自己的集群方案,

    2024年02月05日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包