图或网络中的中心性

2021/7/17 23:12:13

本文主要是介绍图或网络中的中心性,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

图或网络中的中心性

    • 一、点度中心性(degree centrality)
        • 计算:
    • 二、特征向量中心性(eigenvector centrality)
        • 计算:
    • 三、中介中心性(betweenness centrality)
        • 计算:
    • 四、接近中心性(closeness centrality)
        • 计算:

网络由节点(node)和连接它们的边(edge)构成。例如,微信好友的关系是相互的,如果我是你的好友,你也是我的好友。这样的网络称为无向网络(undirected graph/network)。但超链接并非如此,如果我的网站可以链接到维基百科,并不表示维基百科会链接到我的网站。这样的网络称为有向网络(directed graph/network)。

在图论和网络分析中,中心性(Centrality)是判断网络中节点重要性/影响力的指标。在社会网络分析中,一项基本的任务就是鉴定一群人中哪些人比其他人更有影响力,从而帮助我们理解他们在网络中扮演的角色。

那么,什么样的节点是重要的呢?对节点重要性的解释有很多,不同的解释下判定中心性的指标也有所不同。

一、点度中心性(degree centrality)

在无向网络中,我们可以用一个节点的度数(相当于你的微信好友数)来衡量中心性。在微博中,谢娜的粉丝数9千多万,她的点度中心性就很高。

这一指标背后的假设是:重要的节点就是拥有许多连接的节点。你的社会关系越多,你的影响力就越强。

计算:

节点i的点度中心性 = 该节点的度 / (所有节点的个数-1)

二、特征向量中心性(eigenvector centrality)

特征向量中心性的基本思想是,一个节点的中心性是相邻节点中心性的函数。也就是说,与你连接的人越重要,你也就越重要。

特征向量中心性和点度中心性不同,一个点度中心性高即拥有很多连接的节点,而特征向量中心性不一定高,因为所有的连接者有可能特征向量中心性很低。同理,特征向量中心性高并不意味着它的点度中心性高,它拥有很少但很重要的连接者也可以拥有高特征向量中心性。

计算:

  1. 计算邻接矩阵的特征值和特征向量
  2. 选择最大特征值所对应的特征向量
  3. 第i个节点的特征向量中心性等于特征向量中的第i个元素

三、中介中心性(betweenness centrality)

计算网络中任意两个节点的所有最短路径,如果这些最短路径中很多条都经过了某个节点,那么就认为这个节点的中介中心性高。即:如果一个成员处于其他成员的多条最短路径上,那么该成员就是核心成员。

计算:

betweenness = 经过该节点的最短路径 / 其余两两节点的最短路径

四、接近中心性(closeness centrality)

如果节点到图中其他节点的最短距离都很小,那么它的接近中心性就很高。相比中介中心性,接近中心性更接近几何上的中心位置。即:一个人跟所有其他成员的距离越近,他/她就越重要。

计算:

closeness = n-1 /该节点到其它节点的最短路径之和

参考:https://blog.csdn.net/yyl424525/article/details/103108506
https://www.cnblogs.com/miaobo/p/12485574.html



这篇关于图或网络中的中心性的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程