精华内容
下载资源
问答
  • 2022-01-27 17:51:37


        在图中,节点的中心性(Centrality)用于衡量节点在图中的重要性。接下来,以下面这张图的节点为例,介绍一些常用的节点中心性及其计算过程。
    在这里插入图片描述

    一、度中心性(Degree Centrality)

        如果有许多其他节点连接到某个节点,那么后者可以被认为是重要的。因此,可以基于一个节点的度测量它的中心性。更具体地说,对于节点 v i v_i vi,其度中心性可以定义为:
    c d ( v i ) = d ( v i ) = ∑ j = 1 N A i , j c_d(v_i)=d(v_i)=\sum_{j=1}^NA_{i,j} cd(vi)=d(vi)=j=1NAi,j
        由上面的公式可以知道,节点 v 1 v_1 v1 v 5 v_5 v5的度中心性都是3,而节点 v 2 v_2 v2 v 3 v_3 v3 v 4 v_4 v4的度中心性都是2。

    二、特征向量中心性(Eigenvector Centrality)

        度中心性认为与多个节点相邻的节点是重要的,且认为所有邻居的贡献度是一样的。然而,这些相邻节点本身的重要性是不同的,因此它们对中心节点的影响不同。给定一个节点 v i v_i vi,特征向量中心性用它的相邻节点的中心性来定义 v i v_i vi的中心性:
    c e ( v i ) = 1 λ ∑ j = 1 N A i , j ⋅ c e ( v j ) c_e(v_i)=\frac{1}{\lambda}\sum_{j=1}^NA_{i,j}{\cdot}c_e(v_j) ce(vi)=λ1j=1NAi,jce(vj)    也可以表达为矩阵的形式:
    c e ( v i ) = 1 λ A ⋅ c e c_e(v_i)=\frac{1}{\lambda}A{\cdot}c_e ce(vi)=λ1Ace    式中, c e ∈ R N c_e{\in}R^N ceRN是一个包含所有节点的特征向量中心性的向量,这个式子也可以表达为:
    λ ⋅ c e ( v i ) = A ⋅ c e \lambda{\cdot}c_e(v_i)=A{\cdot}c_e λce(vi)=Ace    显然, c e c_e ce是矩阵的特征向量, λ \lambda λ是其对应的特征值。一个邻接矩阵 A A A存在多对特征向量和特征值。中心性的值通常为正数,所以选择中心性需要考虑所有元素均为正数的特征向量。根据Perron-Frobenius定理,一个元素全为正的实方阵具有唯一的最大特征值,其对应的特征向量的元素全为正。因此可以选择最大的特征值 λ \lambda λ,将它的相应的特征向量作为中心性向量。
        通过上面的公式进行计算,可以算出示例图中最大的特征值是2.481,对应的特征向量[1, 0.675, 0.675, 0.806, 1]。因此, v 1 , v 2 , v 3 , v 4 , v 5 v_1,v_2,v_3,v_4,v_5 v1,v2,v3,v4,v5的特征向量中心性分别是1,0.675,0.675,0.806,1。注意 v 2 v_2 v2 v 3 v_3 v3 v 4 v_4 v4的度都是2,但是 v 4 v_4 v4的特征向量中心性比另外两个节点的都要高,因为它和 v 1 v_1 v1 v 5 v_5 v5两个高特征向量中心性的节点直接相连。

    三、Katz中心性(Katz Centrality)

        Katz中心性是特征向量中心性的一个变体,它不仅考虑了邻居的中心性,而且包含了一个常数来考虑中心节点本身。具体来说,节点 v i v_i vi的Katz中心性可以定义为:
    c k ( v i ) = α ∑ j = 1 N A i , j c k ( v j ) + β c_k(v_i)={\alpha}\sum_{j=1}^NA_{i,j}c_k(v_j)+\beta ck(vi)=αj=1NAi,jck(vj)+β    式中, β \beta β是一个常数。一个图中所有节点的Katz中心性可以用矩阵形式表示为:
    c k = α A c k + β ( I − α ⋅ A ) c k = β c_k={\alpha}Ac_k+\beta\\ (I-{\alpha}{\cdot}A)c_k=\beta ck=αAck+β(IαA)ck=β    式中, c k ∈ R N c_k{\in}R^N ckRN表示所有节点的Katz中心性的向量; β \beta β表示一个包含所有节点的常数项 β \beta β的向量; I I I表示单位矩阵。值得注意的是,如果令 α = 1 λ m a x {\alpha}=\frac{1}{\lambda_{max}} α=λmax1 β = 0 \beta=0 β=0,那么Katz中心性等价于特征向量中心性,其中 λ m a x {\lambda}_{max} λmax是邻接矩阵 A A A的最大特征值。 α \alpha α的选择对于Katz中心性非常关键:大的 α \alpha α值可能使矩阵 I − α ⋅ A I-{\alpha}{\cdot}A IαA变成病态矩阵,而小的 α \alpha α可能使中心性变得没有意义,因为它总是给所有节点分配非常相似的分数。在实践中,经常令 α < 1 λ m a x {\alpha}<\frac{1}{\lambda_{max}} α<λmax1,这就保证了矩阵 I − α ⋅ A I-{\alpha}{\cdot}A IαA的可逆性,那么 c k c_k ck可按如下方式计算:
    c k = ( I − α ⋅ A ) − 1 β c_k=(I-{\alpha}{\cdot}A)^{-1}\beta ck=(IαA)1β    令 β = 1 , α = 1 5 \beta=1,\alpha=\frac{1}{5} β=1,α=51,经过计算可得示例图中节点 v 1 v_1 v1 v 5 v_5 v5的Katz中心性都是2.16, v 2 v_2 v2 v 3 v_3 v3的Katz中心性是1.79, v 4 v_4 v4的Katz中心性是1.87。

    四、介数中心性(Betweeness Centrality)

        前面提到的几种中心性基于和相邻节点的连接。另一种度量节点重要性的方法是检查它是否在图中处于重要位置。具体来说,如果有许多路通过同一个节点,那么该节点处于图中的一个重要位置。节点 v i v_i vi的介数中心性的定义如下:
    c b ( v i ) = ∑ v s ≠ v i ≠ v t σ s t ( v i ) σ s t c_b(v_i)=\sum_{v_s{\neq}v_i{\neq}v_t}\frac{\sigma_{st}(v_i)}{\sigma_{st}} cb(vi)=vs=vi=vtσstσst(vi)    式中, σ s t \sigma_{st} σst表示所有从节点 v s v_s vs到节点 v t v_t vt的最短路的数目(此处不区分 v s v_s vs v t v_t vt); σ s t ( v i ) \sigma_{st}(v_i) σst(vi)表示这些路中经过节点 v i v_i vi的路的数目。为了计算介数中心性,需要对所有可能的节点对求和。因此,介数中心性的值会随着图的增大而增大。为了使介数中心性在不同的图中具有可比性,需要对它进行归一化(normalization)。一种有效的方法是将所有节点的中心性除以其中的最大值。由上面介数中心性的公式可知,当任意一对节点之间的最短路都通过节点 v i v_i vi时,介数中心性达到最大值,即 σ s t ( v i ) σ s t = 1 , ∀ v s ≠ v i ≠ v t \frac{\sigma_{st}(v_i)}{\sigma_{st}}=1,{\forall}v_s{\neq}v_i{\neq}v_t σstσst(vi)=1,vs=vi=vt。在一个无向图中,共有 ( N − 1 ) ( N − 2 ) 2 \frac{(N-1)(N-2)}{2} 2(N1)(N2)个不包含节点 v i v_i vi的节点对,所以介数中心性的最大值是 ( N − 1 ) ( N − 2 ) 2 \frac{(N-1)(N-2)}{2} 2(N1)(N2)。所以 v i v_i vi归一化后的介数中心性 c n b ( v i ) c_{nb}(v_i) cnb(vi)可以定义为:
    c n b ( v i ) = 2 × ∑ v s ≠ v i ≠ v t σ s t ( v i ) σ s t ( N − 1 ) ( N − 2 ) c_nb(v_i)=\frac{2{\times}\sum_{v_s{\neq}v_i{\neq}v_t}\frac{\sigma_{st}(v_i)}{\sigma_{st}}}{(N-1)(N-2)} cnb(vi)=(N1)(N2)2×vs=vi=vtσstσst(vi)    在示例图中,节点 v 1 v_1 v1 v 5 v_5 v5的介数中心性是 2 3 \frac{2}{3} 32,而它们归一化后的中心性是 1 4 \frac{1}{4} 41。节点 v 2 v_2 v2 v 3 v_3 v3的介数中心性是 1 2 \frac{1}{2} 21,而它们归一化后的中心性是 1 12 \frac{1}{12} 121。节点 v 4 v_4 v4的介数中心性和归一化的中心性均为0。

    更多相关内容
  • 文章目录点度中心性(degree centrality)中介中心性(betweenness centrality)接近中心性(closeness centrality)特征向量中心性(eigenvector centrality)有向图与PageRank小结 网络由节点(node)和连接它们...

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

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

    那么,什么样的节点是重要的呢?

    对节点重要性的解释有很多,不同的解释下判定中心性的指标也有所不同。

    点度中心性(degree centrality)

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

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

    图1:使用networkx绘制的蝴蝶结网络

    在上面的蝴蝶结网络中,节点D的连接数是6,和网络中的所有人都建立了直接联系,其他节点的连接数都是3,因此节点D的点度中心性最高。整个网络一共有7个节点,意味着每个人最多可以有6个社会关系。因此,节点D的点度中心性是6/6=1,其他节点的点度中心性是3/6=0.5。

    中介中心性(betweenness centrality)

    网络中两个非相邻成员之间的相互作用依赖于其他成员,特别是两成员之间路径上的那些成员。他们对两个非相邻成员之间的相互作用具有控制和制约作用。Freeman (1979)认为中间成员对路径两端的成员具有“更大的人际关系影响”。因此,中介中心性的思想是:如果一个成员位于其他成员的多条最短路径上,那么该成员就是核心成员,就具有较大的中介中心性。

    计算网络中任意两个节点的所有最短路径,如果这些最短路径中很多条都经过了某个节点,那么就认为这个节点的中介中心性高。回到上面的蝴蝶结网络,假设我们要计算节点D的中介中心性。

    首先,我们计算节点D之外,所有节点对之间的最短路径有多少条,这里是15条(在6个节点中选择两个节点即节点对的个数)。
    然后,我们再看所有这些最短路径中有多少条经过节点D,例如节点A要想找到节点E,必须经过节点D。经过节点D的最短路径有9条。
    最后,我们用经过节点D的最短路径除以所有节点对的最短路径总数,这个比率就是节点D的中介中心性。节点D的中介中心性是9/15=0.6。

    如果说点度中心性发现的是网络中的“名人”,那么中介中心性的现实意义是什么呢?

    Maksim Tsvetovat&Alexander Kouznetsov在《社会网络分析》一书中有两个例子:

    • 鲍勃徘徊在两个女人之间,他贪恋爱丽丝的美丽和谈吐,亦无法舍弃卡若琳娜的乐天和无忧无虑。但他必须小心谨慎,生怕自己在其中任何一个人面前露馅,这样的关系充满了压力和焦虑
    • 银行家以5%的利率接受A公司的存款,以7%的利率贷款给B公司,这样的关系给银行家带来了巨大的利益。它的前提是,市场中的A公司和B公司不能直接接触,或至少无法轻易地找到对方

    鲍勃和银行家的故事尽管截然不同,但他们都处于一种被称为被禁止的三元组(forbidden triad)的关系中,需要确保三元组的末端不能直接联系。没有联系就像网络中出现了一个洞,因此也被称为结构洞

    当网络中众多成员的接触或低成本接触都依赖我时,我就对其他成员有了控制和制约作用。我可以利用这种关系控制信息的流动,套取巨大的利益。当然,这样的关系也充满着压力和紧张。诚如Maksim Tsvetovat&Alexander Kouznetsov所言,商人的成功,不仅取决于他们对不对称信息的利用和经营能力,也需要对创造和维持套利机会带来的压力的高度容忍。

    接近中心性(closeness centrality)

    点度中心性仅仅利用了网络的局部特征,即节点的连接数有多少,但一个人连接数多,并不代表他/她处于网络的核心位置。接近中心性和中介中心性一样,都利用了整个网络的特征,即一个节点在整个结构中所处的位置。如果节点到图中其他节点的最短距离都很小,那么它的接近中心性就很高。相比中介中心性,接近中心性更接近几何上的中心位置。

    假设我们要计算节点D的接近中心性,首先我们计算从节点D到所有其他节点的最短距离。从图中可以判断,节点D到所有其他节点的距离均为1,距离之和为6。因此,节点D的接近中心性为(7-1)/6=1。分子为网络中节点总数减去1。也就是说,如果一个人可以直接跟网络中所有其他人联系,那么他/她的接近中心性就是1。对于其他节点,如节点A的接近中心性为(7-1)/9=0.667。

    接近中心性高的节点一般扮演的是八婆的角色(gossiper)。他们不一定是名人,但是乐于在不同的人群之间传递消息。

    特征向量中心性(eigenvector centrality)

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

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

    考虑下面的图,以及相应的5x5的邻接矩阵(Adjacency Matrix),A。

    邻接矩阵的含义是,如果两个节点没有直接连接,记为0,否则记为1。

    现在考虑x,一个5x1的向量,向量的值对应图中的每个点。在这种情况下,我们计算的是每个点的点度中心性(degree centrality),即以点的连接数来衡量中心性的高低。

    矩阵A乘以这个向量的结果是一个5x1的向量:

    A × x = ( − 1 1 1 0 1 − 1 0 0 1 1 − 1 0 1 0 1 − 1 0 0 0 1 ) ( 3 2 3 3 1 ) = ( 0 × 3 + 1 × 2 + 1 × 3 + 1 × 3 + 0 × 1 1 × 3 + 0 × 2 + 1 × 3 + 0 × 3 + 0 × 1 1 × 3 + 1 × 2 + 0 × 3 + 1 × 3 + 0 × 1 1 × 3 + 0 × 2 + 1 × 3 + 0 × 3 + 1 × 1 0 × 3 + 0 × 2 + 1 × 3 + 0 × 3 + 0 × 1 ) = [ 8 6 8 7 3 ] \mathbf{A} \times \mathbf{x}=\left(\begin{array}{cccc}{-1} & {1} & {1} & {0} \\ {1} & {-1} & {0} & {0} \\ {1} & {1} & {-1} & {0} \\ {1} & {0} & {1} & {-1} \\ {0} & {0} & {0} & {1}\end{array}\right)\left(\begin{array}{l}{3} \\ {2} \\ {3} \\ {3} \\ {1}\end{array}\right)=\left(\begin{array}{c}{0 \times 3+1 \times 2+1 \times 3+1 \times 3+0 \times 1} \\ {1 \times 3+0 \times 2+1 \times 3+0 \times 3+0 \times 1} \\ {1 \times 3+1 \times 2+0 \times 3+1 \times 3+0 \times 1} \\ {1 \times 3+0 \times 2+1 \times 3+0 \times 3+1 \times 1} \\ {0 \times 3+0 \times 2+1 \times 3+0 \times 3+0 \times 1}\end{array}\right)=\left[\begin{array}{c}{8} \\ {6} \\{8} \\ {7} \\ {3}\end{array}\right] A×x=1111011100101100001132331=0×3+1×2+1×3+1×3+0×11×3+0×2+1×3+0×3+0×11×3+1×2+0×3+1×3+0×11×3+0×2+1×3+0×3+1×10×3+0×2+1×3+0×3+0×1=86873
    结果向量的第一个元素是用矩阵A的第一行去“获取”每一个与第一个点有连接的点的值(连接数,点度中心性),也就是第2个、第3个和第4个点的值,然后将它们加起来。

    换句话说,邻接矩阵做的事情是将相邻节点的求和值重新分配给每个点。这样做的结果就是“扩散了”点度中心性。你的朋友的朋友越多,你的特征向量中心性就越高。

    我们继续用矩阵A乘以结果向量。如何理解呢?实际上,我们允许这一中心性数值再次沿着图的边界“扩散”。我们会观察到两个方向上的扩散(点既给予也收获相邻节点)。我们猜测,这一过程最后会达到一个平衡,特定点收获的数量会和它给予相邻节点的数量取得平衡。既然我们仅仅是累加,数值会越来越大,但我们最终会到达一个点,各个节点在整体中的比例会保持稳定。

    现在把所有点的数值构成的向量用更一般的形式表示:

    [ − 1 1 1 0 1 − 1 0 0 1 1 − 1 0 1 0 1 − 1 0 0 0 1 − ] [ x 1 x 2 x 3 x 4 x 5 ] = [ 0 ⋅ x 1 + 1 ⋅ x 2 + 1 ⋅ x 3 + 1 ⋅ x 4 + 0 ⋅ x 5 1 ⋅ x 1 + 0 ⋅ x 2 + 1 ⋅ x 3 + 0 ⋅ x 4 + 0 ⋅ x 5 1 ⋅ x 1 + 1 ⋅ x 2 + 0 ⋅ x 3 + 1 ⋅ x 4 + 0 ⋅ x 5 1 ⋅ x 1 + 0 ⋅ x 2 + 1 ⋅ x 3 + 0 ⋅ x 4 + 1 ⋅ x 5 0 ⋅ x 1 + 0 ⋅ x 2 + 0 ⋅ x 3 + 1 ⋅ x 4 + 0 ⋅ x 5 ] \left[\begin{array}{ccccc}{-} & {1} & {1} & {1} & {0} \\ {1} & {-} & {1} & {0} & {0} \\ {1} & {1} & {-} & {1} & {0} \\ {1} & {0} & {1} & {-} & {1} \\ {0} & {0} & {0} & {1} & {-}\end{array}\right]\left[\begin{array}{l}{x_{1}} \\ {x_{2}} \\ {x_{3}} \\ {x_{4}} \\ {x_{5}}\end{array}\right]=\left[\begin{array}{c}{0 \cdot x_{1}+1 \cdot x_{2}+1 \cdot x_{3}+1 \cdot x_{4}+0 \cdot x_{5}} \\ {1 \cdot x_{1}+0 \cdot x_{2}+1 \cdot x_{3}+0 \cdot x_{4}+0 \cdot x_{5}} \\ {1 \cdot x_{1}+1 \cdot x_{2}+0 \cdot x_{3}+1 \cdot x_{4}+0 \cdot x_{5}} \\ {1 \cdot x_{1}+0 \cdot x_{2}+1 \cdot x_{3}+0 \cdot x_{4}+1 \cdot x_{5}} \\ {0 \cdot x_{1}+0 \cdot x_{2}+0 \cdot x_{3}+1 \cdot x_{4}+0 \cdot x_{5}}\end{array}\right] 11101100111010110001x1x2x3x4x5=0x1+1x2+1x3+1x4+0x51x1+0x2+1x3+0x4+0x51x1+1x2+0x3+1x4+0x51x1+0x2+1x3+0x4+1x50x1+0x2+0x3+1x4+0x5
    我们认为,图中的点存在一个数值集合,对于它,用矩阵A去乘不会改变向量各个数值的相对大小。也就是说,它的数值会变大,但乘以的是同一个因子。用数学符号表示就是:

    M x = λ x \mathbf{M} \mathbf{x}=\lambda \mathbf{x} Mx=λx

    M × ( x 1 x 2 ⋯ x n ) = ( λ x 1 λ x 2 ⋯ λ x n ) \mathbf{M} \times\left(\begin{array}{c}{x_{1}} \\ {x_{2}} \\ {\cdots} \\ {x_{n}}\end{array}\right)=\left(\begin{array}{c}{\lambda x_{1}} \\ {\lambda x_{2}} \\ {\cdots} \\ {\lambda x_{n}}\end{array}\right) M×x1x2xn=λx1λx2λxn
    满足这一属性的向量就是矩阵M的特征向量。特征向量的元素就是图中每个点的特征向量中心性。

    特征向量中心性的计算需要读者具备矩阵乘法和特征向量的知识,但不影响这里读者对特征向量中心性思想的理解,不再赘述。

    有向图与PageRank

    PageRank是衡量有向网络中节点重要性的指标。

    我们将万维网抽象成有向图:(1)每个网页抽象成一个节点,假设有A、B、C、D四个节点;(2)用户通过超链接在网页之间跳转,这种跳转是有方向的(directed),从网页A跳转到网页B不代表可以从网页B链接到网页A,这种节点之间的有方向的连接被抽象成有方向的边。整个网络构成一个有向图。

    你可以很轻易地找到最受欢迎的网页。但是,PageRank的思想认为,指标最好还需要考虑到指向你的那些网页。也就是说,来自受欢迎的网页的跳转应该重于不太受欢迎的网页的跳转。这就是PageRank思想的精华,Google就是利用这一思想来给网站排名的。这里的思想依据和特征向量中心性其实是一致的。

    首先,我们假设用户停留在一个页面时,跳转到每个链接页面的概率是相同的。例如,用户停留在页面A,他可以跳转到B、C、D三个页面,我们假设用户跳转到每个页面的概率相同,也就是说用户跳转到每个页面的概率均为1/3。我们可以用下面的转移矩阵(Transition Matrix)来表示整个有向图的情况:

    M = [ 0 1 / 2 0 1 / 2 1 / 3 0 0 1 / 2 1 / 3 1 / 2 0 0 1 / 3 0 1 0 ] M=\left[\begin{array}{cccc}{0} & {1 / 2} & {0} & {1 / 2} \\ {1 / 3} & {0} & {0} & {1 / 2} \\ {1 / 3} & {1 / 2} & {0} & {0} \\ {1 / 3} & {0} & {1} & {0}\end{array}\right] M=01/31/31/31/201/2000011/21/200

    假设有向图中有n个节点,那么M就是一个n行n列的矩阵,其中的第i行第j列代表从页面j跳转到页面i的概率。例如,M矩阵的第一行代表从ABCD跳转到页面A的概率。

    然后,我们设每个页面的初始rank为1/4,4个页面的初始rank构成向量v:

    v = [ 1 / 4 1 / 4 1 / 4 1 / 4 ] v=\left[\begin{array}{c}{1 / 4} \\ {1 / 4} \\ {1 / 4} \\ {1 / 4}\end{array}\right] v=1/41/41/41/4
    用M第一行乘以向量v,得到的就是页面A最新rank的合理估计: 0 ∗ 1 / 4 + 1 / 2 ∗ 1 / 4 + 0 ∗ 1 / 4 + 1 / 2 ∗ 1 / 4 = 1 / 4 0*1/4+1/2*1/4+0*1/4+1/2*1/4=1/4 01/4+1/21/4+01/4+1/21/4=1/4。Mv的结果就是ABCD四个页面的新rank:

    M v = [ 1 / 4 5 / 24 5 / 24 1 / 3 ] M v=\left[\begin{array}{c}{1 / 4} \\ {5 / 24} \\ {5 / 24} \\ {1 / 3}\end{array}\right] Mv=1/45/245/241/3
    然后用M再乘以新的rank向量,又会产生一个新的rank向量。迭代这一过程,Mv结果各个值的相对大小会保持稳定。也就是说,其结果等于用一个标量乘以v。

    满足这一属性的向量就是矩阵M的特征向量。这里的结果会收敛在[1/4, 1/4, 1/5, 1/4],这就是A、B、C、D最后的PageRank。这一结果表明,相比于网页C, ABD更为重要。

    上述方程式假设上网者一定是通过网页上的链接进行跳转的,但实际上,上网者在每一步都有可能在地址栏随机输入一个网址,跳转到其他页面,而不是点击网页上的链接。或者,上网者可能到达一个没有任何链出页面的网页,这时他会随机到另外的页面进行浏览。

    想象有两个网页的简单例子,网页A链接到B,但B无法链接到A。转移矩阵如下:

    M = [ 0 0 1 0 ] M=\left[\begin{array}{ll}{0} & {0} \\ {1} & {0}\end{array}\right] M=[0100]
    不断迭代,最后我们得到的是一个0矩阵:

    M v = [ 0 0 1 0 ] [ 1 2 1 2 ] = [ 0 1 2 ] M v=\left[\begin{array}{ll}{0} & {0} \\ {1} & {0}\end{array}\right]\left[\begin{array}{l}{\frac{1}{2}} \\ {\frac{1}{2}}\end{array}\right]=\left[\begin{array}{l}{0} \\ {\frac{1}{2}}\end{array}\right] Mv=[0100][2121]=[021]
    考虑到B比A重要,这一结果是不合理的,它认为A和B同等重要。为了解决这个问题,我们引入 “心灵运输”(Teleportation) 的概念。它意味着上网者每一步都有可能随机输入一个网址(心灵运输),跳转到其他页面(这意味着每一步,网络上的每个网页都有一定的概率被访问到,它的概率为(1-d)/N,即上网者心灵运输的概率乘以每个网页被访问的概率),而不是点击网页上的链接。

    我们假设上网者在任何页面继续向下浏览的概率为d=0.85。d也被称为阻尼系数(damping factor)。1-d=0.15就是上网者停止点击,随机跳到新网址的概率,即心灵运输的概率。设网页总数为N,那么跳转到任一网页的概率为N。因此,调整后的方程式如下:

    v ′ = d M v + e 1 − d N v^{\prime}=d M v+e \frac{1-d}{N} v=dMv+eN1d
    其中的e为单位矩阵,这样才能与方程式的前半部分相加。

    v ′ = 0.8 × [ 0 0 1 0 ] [ 1 2 1 2 ] + 0.2 × [ 1 2 1 2 ] = [ 1 10 1 2 ] v^{\prime}=0.8 \times\left[\begin{array}{ll}{0} & {0} \\ {1} & {0}\end{array}\right]\left[\begin{array}{l}{\frac{1}{2}} \\ {\frac{1}{2}}\end{array}\right]+0.2 \times\left[\begin{array}{l}{\frac{1}{2}} \\ {\frac{1}{2}}\end{array}\right]=\left[\begin{array}{c}{\frac{1}{10}} \\ {\frac{1}{2}}\end{array}\right] v=0.8×[0100][2121]+0.2×[2121]=[10121]
    不断迭代后,两个网页的rank会收敛为:

    [ 1 10 1 2 ] 0.1 0.18 ] ⋯ [ 0.35 0.64 ] \left.\left[\begin{array}{c}{\frac{1}{10}} \\ {\frac{1}{2}}\end{array}\right] \begin{array}{l}{0.1} \\ {0.18}\end{array}\right] \cdots \left[\begin{array}{l}{0.35} \\ {0.64}\end{array}\right] [10121]0.10.18][0.350.64]

    小结

    • 点度中心性:一个人的社会关系越多,他/她就越重要
    • 中介中心性:如果一个成员处于其他成员的多条最短路径上,那么该成员就是核心成员
    • 接近中心性:一个人跟所有其他成员的距离越近,他/她就越重要
    • 特征向量中心性:与你连接的人社会关系越多,你就越重要
    • PageRank:来自受欢迎的网页的跳转应该重于不太受欢迎的网页的跳转
    展开全文
  • 复杂网络中心性1. 度中心度(Degree Centrality)2. 介数中心度(Betweenness...一个节点的节点度越大就意味着该节点的度中心性越高,该节点在网络中就越重要。 某个节点 度中心度 计算公式如下: DCi=kiN−1 DC_i=\fra

    1. 度中心性(Degree Centrality)

    度中心性(Degree Centrality)是在网络分析中刻画节点中心性(Centrality)的最直接度量指标。一个节点的节点度越大就意味着该节点的度中心性越高,该节点在网络中就越重要。

    某个节点 度中心性 计算公式如下:
    D C i = k i N − 1 DC_i=\frac{k_i}{N-1} DCi=N1ki
    其中:

    • k i k_i ki 表示现有的与节点 i i i 相连的边的数量
    • N − 1 N-1 N1 表示节点 i i i 与其他节点都相连的边的数量

    2. 介数中心性(Betweenness Centrality)

    节点介数是指一个网络里通过节点的最短路径条数

    某个节点的 介数中心性 的计算公式如下:
    B C i = ∑ s ≠ i ≠ t n s t i g s t BC_i=\sum_{s\neq i\neq t}\frac{n^i_{st}}{g_{st}} BCi=s=i=tgstnsti
    其中:

    • n s t i n^i_{st} nsti 表示经过节点 i i i ,且为最短路径的路径数量
    • g s t g_{st} gst 表示连接 s s s t t t 的最短路径的数量

    归一化(令结果 < 1)后,有:
    B C i = 1 ( N − 1 ) ( N − 2 ) / 2 ∑ s ≠ i ≠ t n s t i g s t BC_i=\frac{1}{(N-1)(N-2)/2}\sum_{s\neq i\neq t}\frac{n^i_{st}}{g_{st}} BCi=(N1)(N2)/21s=i=tgstnsti

    上图计算节点 1 1 1 的介数中心性:

    • 5 5 5 -> 4 4 4 ,最短路径为 ( 5 , 1 , 4 ) (5,1,4) (5,1,4), 该路径经过节点 1 1 1 ,所以 n 54 1 = 1 , g 54 = 1 n^1_{54}=1,g_{54}=1 n541=1,g54=1
    • 5 5 5 -> 3 3 3 ,最短路径为 ( 5 , 3 ) (5,3) (5,3), 该路径不经过节点 1 1 1,所以 n 53 1 = 0 , g 53 = 1 n^1_{53}=0,g_{53}=1 n531=0,g53=1
    • 5 5 5 -> 2 2 2 ,最短路径为 ( 5 , 1 , 2 ) , ( 5 , 3 , 2 ) (5,1,2),(5,3,2) (5,1,2),(5,3,2), 经过节点 1 1 1 的路径为 ( 5 , 1 , 2 ) (5,1,2) (5,1,2),所以 n 52 1 = 1 , g 52 = 2 n^1_{52}=1,g_{52}=2 n521=1,g52=2
    • 4 4 4 -> 3 3 3 ,最短路径为 ( 4 , 1 , 2 , 3 ) , ( 4 , 1 , 5 , 3 ) (4,1,2,3),(4,1,5,3) (4,1,2,3),(4,1,5,3), 两条路径都经过节点 1 1 1,所以 n 43 1 = 2 , g 43 = 2 n^1_{43}=2,g_{43}=2 n431=2,g43=2
    • 4 4 4 -> 2 2 2 ,最短路径为 ( 4 , 1 , 2 ) (4,1,2) (4,1,2), 该路径经过节点 1 1 1,所以 n 42 1 = 1 , g 42 = 1 n^1_{42}=1,g_{42}=1 n421=1,g42=1
    • 3 3 3 -> 2 2 2 ,最短路径为 ( 3 , 2 ) (3,2) (3,2), 该路径不经过节点 1 1 1,所以 n 32 1 = 0 , g 32 = 1 n^1_{32}=0,g_{32}=1 n321=0,g32=1
    • 最后得出 B ( 1 ) = 7 2 B(1)=\frac{7}{2} B(1)=27 ,对其归一化得 B ( 1 ) = 7 12 B(1)=\frac{7}{12} B(1)=127

    3. 接近中心性(Closeness Centrality)

    接近中心性用于衡量节点重要性

    某个节点的 接近中心性 C C i CC_i CCi 为:
    d i = 1 N − 1 ∑ j = 1 N d i j C C i = 1 d i d_i=\frac{1}{N-1}\sum^{N}_{j=1}d_{ij} \quad \quad CC_i=\frac{1}{d_i} di=N11j=1NdijCCi=di1
    其中 d i d_i di 表示节点 i i i 到其余各点的平均距离,平均距离的倒数就是接近中心度

    例:

    以上图节点 A A A 为例,图中点的个数 N = 11 N=11 N=11

    • A A A 相连的路径为 1 1 1 的共 4 4 4 个点,为 D , E , F , B D,E,F,B D,E,F,B
    • A A A 相连的路径为 2 2 2 的共 3 3 3 个点,为 G . C , H G.C,H G.C,H
    • A A A 相连的路径为 3 3 3 的共 3 3 3 个点,为 I , J , K I,J,K I,J,K
    • 可得 A A A 的平均距离为 d ( A ) = 1 10 ( 4 + 2 ∗ 3 + 3 ∗ 3 ) d(A)=\frac{1}{10}(4+2 *3+3*3) d(A)=101(4+23+33) A A A 的接近中心度为 C C ( A ) = 1 d ( A ) CC(A)=\frac{1}{d(A)} CC(A)=d(A)1
    展开全文
  • 1、点度中心性(degree centrality) 2、 特征向量中心性(eigenvector centrality) 3、中介中心性(betweenness centrality) 4、接近中心性(closeness centrality) 在图论和网络分析中,中心性(Centrality...

    目录

    1、点度中心性(degree centrality)

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

    3、中介中心性(betweenness centrality)

    4、接近中心性(closeness centrality)


    在图论和网络分析中,中心性(Centrality)是判断网络中节点重要性/影响力的指标

    1、点度中心性(degree centrality)

    在无向网络中,我们可以用一个节点的度数来衡量中心性。这一指标背后的假设是:重要的节点就是拥有许多连接的节点。

    DC = \frac{N_{degree}}{n-1}

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

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

     

    A= \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}

    现在考虑x,一个5x1的向量,向量的值对应图中的每个点。

    A \times X= \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ \end{bmatrix} = \begin{bmatrix} 0 \cdot x_1 + 1 \cdot x_2 + 1 \cdot x_3 + 1 \cdot x_4 + 0 \cdot x_5 \\ 1 \cdot x_1 + 0 \cdot x_2 + 1 \cdot x_3 + 0 \cdot x_4 + 0 \cdot x_5 \\ 1 \cdot x_1 + 1 \cdot x_2 + 0 \cdot x_3 + 1 \cdot x_4 + 0 \cdot x_5 \\ 1 \cdot x_1 + 0 \cdot x_2 + 1 \cdot x_3 + 0 \cdot x_4 + 1 \cdot x_5 \\ 0 \cdot x_1 + 0 \cdot x_2 + 0 \cdot x_3 + 1 \cdot x_4 + 0 \cdot x_5 \\ \end{bmatrix}

    邻接矩阵做的事情是将相邻节点的求和值重新分配给每个点。这样做的结果就是“扩散了”点度中心性。

    我们认为,图中的点存在一个数值集合,对于它,用矩阵A去乘不会改变向量各个数值的相对大小。也就是说,它的数值会变大,但乘以的是同一个因子。用数学符号表示就是:

    M\bf x=\lambda \bf x

    M\times \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \cdots \\ x_n \\ \end{bmatrix} = \begin{bmatrix} \lambda x_1 \\ \lambda x_2 \\ \lambda x_3 \\ \cdots \\ \lambda x_n \\ \end{bmatrix}

    满足这一属性的向量就是矩阵M的特征向量。特征向量的元素就是图中每个点的特征向量中心性。

    A\bf x=\lambda \bf x
    \bf x=c A \bf x
     

    其中c为一个比例常数,c=\lambda^{-1}{\bf{x}}=[x_1,x_2,x_3,\cdots,x_n]^T。记x_i是v_i的特征向量中心性度量,则:

    EC(i)=x_i=c\sum_{j=1}^n {a_{ij}x_j}

     如图,先求出该图所表示的邻接矩阵的特征值。选最大的一个特征值2.48,求出对应的特征向量。将其乘以-1,是没有影响的。于是得到了图中所示的特征向量中心性{1: 0.53, 2: 0.358, 3: 0.358, 4: 0.427, 5: 0.53}

    可以看到,1和5节点的特征向量中心性是比较大的,因为其本身的度就比较大。

    其次是2,3,4节点,它们自身的度都是2,但是特征向量中心性不一样。2连接了1,3连接了5,但是4连接了1和5,特征向量中心性与该节点的邻居节点重要性相关,所以4的特征向量中心性比2和3的大。

    3、中介中心性(betweenness centrality)

    中介中心性的思想是:如果一个成员位于其他成员的多条最短路径上,那么该成员就是核心成员,就具有较大的中介中心性。它是指网络中经过某点并连接这两点的最短路径占这两点之间的最短路径线总数之比。

    以经过某个节点的最短路径数目来刻画节点的重要性指标。计算公式:

    BC=\sum_{s,t\neq i} \frac{d_{st}(i)}{d_{st}}

    其中d_{st}表示s到t的最短路径数量,d_{st}(i)表示从s到t的最短路径中经过i节点的数量。s,t\neq i

    4、接近中心性(closeness centrality)

    反映在网络中某一节点与其他节点之间的接近程度。如果节点到图中其他节点的最短距离都很小,那么它的接近中心性就很高。相比中介中心性,接近中心性更接近几何上的中心位置。

    如果进行归一化处理,就是求这个节点到其他所有节点的平均最短距离。计算公式:

    d_i=\frac{\sum_{j\neq i} d_{ij}}{n-1}

    一个节点的平均最短距离越小,那么这个进行的接近中心性就越大。如果节点i和节点j之间没有路径可达,则定义d_{ij}为无穷大,其倒数为0。

    CC_i=\frac{1}{b_i}=\frac{n-1}{\sum_{j\neq i} d_{ij}}

    CC_i表示i节点的接近中心性,d_{ij}表示i到j的最短距离。CC_i值越大,i点的接近中心性越大。

    展开全文
  • 利用python求解度中心性

    千次阅读 2019-10-27 19:29:32
    利用networkx里面的函数degree_centrality(G)来求解图的度中心性。 代码如下: # -*- coding: utf-8 -*- """ Created on Sat Sep 14 18:01:27 2019 @author: Administrator """ ''' 程序的算法思想:需要读入一个...
  • 度中心性python实现

    千次阅读 2020-11-08 21:17:37
    def degreeCentrality(ndarray,N): DC = [] for i in range(N): k = 0 for j in range(N): if(ndarray[i][j] == 1): k+=1 DC.append(k/(N-1)) return DC
  • 网络分析中,经常会用到中心性这个概念。通常在中心性的分析角度上有两种出发点:中心度和中心势。...目前有四种中心性的分析方法,分别是:度中心性(degree centrality),间接中心性(betweenness centrali...
  • 社交网络分析中(SNA)的中心性(centrality) 度中心性(degree),接近中心性(closeness),中介中心性(betweenness) https://blog.csdn.net/qq_34588902/article/details/7715032 度中心性(degree)、接近中心性...
  • 中心性(Centrality)是社交网络分析(Social network analysis, SNA)中常用的一个概念,用以表达社交网络中每个点或者每个人在整个网络中与其他点或其他人之间的关联程度。比如,想知道某个人在网络社交圈中处于哪...
  • ] for i in range(N)] nx.draw(er,ps,node_color =color ,with_labels=True,node_size=300) plt.show() def centrality(G): #计算度中心性,降序 dc = nx.algorithms.centrality.degree_centrality(G) return sorted...
  • 各种度中心性的定义与区别

    千次阅读 2018-04-16 15:04:56
    作者:何燕杰 链接:...ps:知识储备度中心性(degree)设想一下,你在微信上有个账号,那么是不是意味着微信好友数量越多,那么你的社交圈子越广?(假设都是真实好友,不考虑微商神马的奇葩情况)比如我有20个好...
  • 度中心性的原理及案例

    千次阅读 2016-12-27 10:44:35
    http://blog.sina.com.cn/s/blog_72ef7bea0102v748.html
  • 利用python绘制热图、计算网络节点degree、kshell、介数中心性、接近中心性、特征向量中心性、PageRank,计算相关性含环境、代码、数据源
  • 中心性(centrality)

    千次阅读 2020-11-24 00:32:14
    单个结点中心性主要分为度中心性、特征向量的中心性、Katz中心性、PageRank、中间中心性、接近中心性。 度中心性 针对无向图,结点viv_ivi​的度中心性为Cd(vi)=diC_{d}\left ( v_{i}\right )=d_{i}Cd​(vi​)=di​...
  • 中心性算法 (Centrality Algorithms)

    千次阅读 2021-03-15 17:34:21
    中心性(Centrality)是社交网络分析(Social network analysis, SNA)中用以衡量网络中一个点或者一个人在整个网络中接近中心程度的一个概念,这个程度用数字来表示就被称作为中心。也就是说,通过了解一个节点的...
  • 1、Degree Centrality(度中心性) 1.1 定义 度中心性(Degree Centrality)是在网络分析中刻画节点中心性(Centrality)的最直接度量指标。一个节点的节点度越大就意味着这个节点的度中心性越高,该节点在网络中就越...
  • 想导出数据的中心性值,已经统计了网络直径,但是数据表格中没有中心性等数据。 找了很久发现在数据资料的最右边有个小灯泡 解决 它是显示设置,可以勾选想要的数据,之前没勾选,所以没显示 问题解决。 ...
  • 介数中心性和接近中心性指标, 虽然具有较好的刻画节点重要性的能力, 但计算复杂度太高, 难以在大规模网络上使用. 为了权衡算法的效率和效果, Chen 等人提出了一种基于半局部信息的节点重要性排序方法,简称半局部中心...
  • 《图算法》第五章 中心性算法-1

    千次阅读 2019-08-28 16:50:55
    中心性算法(centrality algorithm)用于理解图中特定节点的角色及其对网络的影响。之所以有用,是因为这些算法能够识别最重要的节点,并帮助我们了解群体动态,例如...度中心性(Degree Centrality)作为连通性的基线...
  • 度中心性(degree) 设想一下,你在微信上有个账号,那么是不是意味着微信好友数量越多,那么你的社交圈子越广?(假设都是真实好友,不考虑微商神马的奇葩情况)比如我有20个好友,那么意味着20个结点与我相连。...
  • 目录一、复杂网络中心度(一)PageRank 算法(二)度中心度(Degree Centrality)(三)接近度中心度(Closeness Centrality)(四)中间中心度(Betweenness Centrality)(五)特征向量中心度(Eigenvector ...
  • SNA(社会网络分析)——三种中心度总结

    万次阅读 多人点赞 2017-11-11 16:35:41
    一 简介 社会网络分析中,中心度表示点的中心度,中心势表示整个网络的中心度(趋势)。...点度中心势表示网络图的整体中心性。体现整体网的集中程度。星形网络图核心点点度中心度为n-1,其余点为1,中心势为1;完...
  • 直觉上我们感觉节点3应该是网络的中心,那么什么指标能够度量一个节点的中心性呢,在NetworkX库中应该如何计算呢,下面我们通过一个实例来看一下。 import matplotlib.pyplot as plt import networkx as nx G = nx....
  • 社交网络度量---中心性

    万次阅读 2017-04-20 12:46:03
    中心性定义了网络中一个结点的重要性。换句话说,我们要求的是,在社会网络中,谁是中心角色(具有影响力的用户) 举个例子,某个明星开通了微博,在短短数小时内,就有几十万的粉丝关注了他的微博。我们可以认为,...
  • SNA社会关系网络分析中,关键的就是通过一些指标的衡量来评价网络结构稳定、集中趋势等。主要有中心度以及中心势两大类指标。 以下的代码都是igraph包中的。 ——————————————...点度中心度 在某
  • 节点中心性度量

    万次阅读 多人点赞 2019-02-27 10:14:09
    中心性(centrality):哪个节点的影响力更大? 1.Centrality度量方法:Degree Degree是运用最广泛的centrality之一,因为它计算简单,可理解性强 局限:邻接节点的重要性没有考虑 举个例子,微博上某账户买僵尸粉...
  • 社交网络分析-中心性指标

    千次阅读 2019-09-12 04:45:50
    分析社交网络的首要方法是衡量网络中各节点的影响力和重要性。换句话说,我们要求的是,在社会网络中,谁是中心角色(具有影响力的用户) 在社会网络拓扑图中一般认为节点中...下面简单的介绍下几种中心性的度量...
  • 首先,中介中心性是个啥?它是一个对于图中顶点重要程度的度量标准。那么它度量哪个方面的重要程度呢? 我们可以使用身边社交网络来做一个例子。这个有点像是我们身边那种社交达人,我们认识的不少朋友可能都是通过...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 362,821
精华内容 145,128
关键字:

度中心性