精华内容
下载资源
问答
  • 中心性(degree)、接近中心性(closeness)和中介中心性(betweenness)的理解
    万次阅读 多人点赞
    2017-08-13 21:28:00
    作者:何燕杰
    链接:https://www.zhihu.com/question/22610633/answer/143644471
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    ps:写在这里只是为了方便以后忘记后理解。

    度中心性(degree)

    设想一下,你在微信上有个账号,那么是不是意味着微信好友数量越多,那么你的社交圈子越广?(假设都是真实好友,不考虑微商神马的奇葩情况)比如我有20个好友,那么意味着20个结点与我相连。如果你有50个好友,那么意味着你的点度中心度比我高,社交圈子比我广。这个就是点度中心性的概念。

    当然,刚才这个情况是无向图的情形,如果是有向图,需要考虑的出度和入度的问题。

    在刚才的基础上拓展一下,假如我们要比较你在微博和微信上的点度中心度,刚才的方法是否适用?如果说使用微信与微博的人数差不多,那么的确可以。但是如果说用户数量不一样呢?那么我们需要考虑到去规模化的问题,这就是标准化的点度中心性的理念。

    接近中心性(closeness)

    对于了解图论的朋友而言,最短路这个概念一定不陌生。我们设想一个实际生活中的场景,比如你要建一个大型的娱乐商场,你可能会希望周围的顾客到达这个商场的距离都可以尽可能地短。这个就涉及到接近中心性的概念,接近中心性的值为路径长度的倒数。

    接近中心性需要考量每个结点到其它结点的最短路的平均长度。也就是说,对于一个结点而言,它距离其它结点越近,那么它的中心度越高。一般来说,那种需要让尽可能多的人使用的设施,它的接近中心度一般是比较高的。

    中介中心性(betweenness)

    这个度量很有意思。这个有点像是我们身边那种社交达人,我们认识的不少朋友可能都是通过他/她认识的,这个人起到了中介的作用。

    中介中心性指的是一个结点担任其它两个结点之间最短路的桥梁的次数。一个结点充当“中介”的次数越高,它的中介中心度就越大。如果要考虑标准化的问题,可以用一个结点承担最短路桥梁的次数除以所有的路径数量。


    百度百科解释:

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


    接近中心性(Closeness Centrality)。反映在网络中某一节点与其他节点之间的接近程度。将一个节点到所有其他节点的最短路径距离的累加起来的倒数表示接近性中心性。即对于一个节点,它距离其他节点越近,那么它的接近性中心性越大。


    中介中心性/中间中心性(Between Centrality) 。以经过某个节点的最短路径数目来刻画节点重要性的指标。


    特征向量中心性(Eigenvector Centrality)。一个节点的重要性既取决于其邻居节点的数量(即该节点的度),也取决于其邻居节点的重要性。



    更多相关内容
  • 中心性(centrality)

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

    参考资料

    1. 《社会媒体挖掘》

    中心性(centrality)用来度量结点在网络中的重要性。对于单个结点或由多个结点组成的群体都可以定义中心性。

    单个结点中心性

    单个结点中心性主要分为度中心性、特征向量的中心性、Katz中心性、PageRank、中间中心性、接近中心性。

    度中心性

    针对无向图,结点 v i v_i vi的度中心性为 C d ( v i ) = d i C_{d}\left ( v_{i}\right )=d_{i} Cd(vi)=di,即为结点的度;
    针对有向图,中心性既可以是入度(视为声望) C d ( v i ) = d i i n C_{d}\left ( v_{i}\right )=d_{i}^{in} Cd(vi)=diin,也可以是出度(视为合群性) C d ( v i ) = d i o u t C_{d}\left ( v_{i}\right )=d_{i}^{out} Cd(vi)=diout,还可以是二者的和 C d ( v i ) = d i i n + d i o u t C_{d}\left ( v_{i}\right )=d_{i}^{in}+d_{i}^{out} Cd(vi)=diin+diout

    特征向量中心性

    特征向量中心性是想结合结点邻居的中心性作为该结点的中心性:

    c e ( v i ) = 1 λ ∑ j = 1 n A j , i c e ( v j ) c_{e}\left ( v_{i}\right )=\frac{1}{\lambda }\sum_{j=1}^{n}A_{j,i}c_{e}\left ( v_{j}\right ) ce(vi)=λ1j=1nAj,ice(vj)

    其中, λ \lambda λ是个常量, c e ( v i ) c_{e}\left ( v_{i}\right ) ce(vi)是结点 v i v_{i} vi的中心性。
    将上式写成矩阵形式,特征向量中心性实际上是对网络的邻接矩阵 A A A进行特征分解,选择最大特征值对应的特征向量作为各结点的中心性。

    λ C e = A T C e \lambda C_{e}=A^{T}C_{e} λCe=ATCe

    其中, C e C_{e} Ce是邻接矩阵 A T A^{T} AT的特征向量, λ \lambda λ是对应的特征值。
    但是中心性要求大于0,所以引入Perron-Frobenius Theorem:
    假设 A ∈ R n × n A \in \textrm{R} ^{n\times n} ARn×n是[强]连通图的邻接矩阵,或者 A : A i , j > 0 A:A_{i,j}> 0 A:Ai,j>0(即一个正的 n × n n\times n n×n的矩阵),存在一个正实数(Perron-Frobenius特征值) λ m a x \lambda_{max} λmax,满足 λ m a x \lambda _{max} λmax是矩阵 A A A的特征值,并且 A A A的其余特征值均严格小于 λ m a x \lambda _{max} λmax λ m a x \lambda _{max} λmax所对应的特征向量为 v = ( v 1 , v 2 , ⋅ ⋅ ⋅ , v n ) \mathbf{v}=\left ( v_{1},v_{2},\cdot \cdot \cdot ,v_{n}\right ) v=(v1,v2,,vn),满足 ∀ v i > 0 \forall v_{i}> 0 vi>0

    Katz中心性

    对于入度为0的结点,其特征向量中心性为0。为了解决这个问题,加入了一个偏差项 β \beta β

    c K a t z ( v i ) = α ∑ j = 1 n A j , i c K a t z ( v j ) + β c_{Katz}\left ( v_{i}\right )=\alpha \sum_{j=1}^{n}A_{j,i}c_{Katz}\left ( v_{j}\right )+\beta cKatz(vi)=αj=1nAj,icKatz(vj)+β

    写为向量形式:

    C K a t z = α A T C K a t z + β 1 C_{Katz}=\alpha A^{T}C_{Katz}+\beta \textbf{1} CKatz=αATCKatz+β1

    移项得:

    C K a t z = β ( I − α A T ) − 1 ⋅ 1 C_{Katz}=\beta \left ( I-\alpha A^{T}\right )^{-1}\cdot \textbf{1} CKatz=β(IαAT)11

    注意:当 det ( I − α A T ) = 0 \textbf{det}\left ( I-\alpha A^{T}\right )=0 det(IαAT)=0时,矩阵 I − α A T I-\alpha A^{T} IαAT将不可逆。实际中,一般选择 α < 1 / λ \alpha < 1/\lambda α<1/λ以便正确计算中心性。

    PageRank

    PageRank则是在Katz中心性的基础上,对结点传递出的中心性对其出度作了归一化,这显然是合理的。

    C p ( v i ) = α ∑ j = 1 n A j , i C p ( v j ) d j o u t + β C_{p}\left ( v_{i}\right )=\alpha \sum_{j=1}^{n}A_{j,i}\frac{C_{p}\left ( v_{j}\right )}{d_{j}^{out}}+\beta Cp(vi)=αj=1nAj,idjoutCp(vj)+β

    表示为矩阵形式:

    C p = α A T D − 1 C p + β 1 C_{p}=\alpha A^{T}D^{-1}C_{p}+\beta \textbf{1} Cp=αATD1Cp+β1

    改写为:

    C p = β ( I − α A T D − 1 ) − 1 ⋅ 1 C_{p}=\beta \left ( I-\alpha A^{T}D^{-1}\right )^{-1}\cdot \textbf{1} Cp=β(IαATD1)11

    类似于Katz中心性,实际上,选取 α < 1 / λ \alpha < 1 / \lambda α<1/λ,其中 λ \lambda λ是矩阵 A T D − 1 A^{T}D^{-1} ATD1的最大特征值。在无向图中,由于矩阵 A T D − 1 A^{T}D^{-1} ATD1的最大特征值为 λ = 1 \lambda =1 λ=1,所以 α < 1 \alpha < 1 α<1

    中间中心性

    中间中心性计算其他结点间通过结点 v i v_{i} vi的最短路径数。

    C b ( v i ) = ∑ s ≠ t ≠ v i σ s t ( v i ) σ s t C_{b}\left ( v_{i}\right )=\sum_{s\neq t\neq v_{i}}^{}\frac{\sigma _{st}\left ( v_{i}\right )}{\sigma _{st}} Cb(vi)=s=t=viσstσst(vi)

    通俗地讲,结点 s s s与结点 t t t间存在许多条最短路径,共 σ s t \sigma _{st} σst,其中有 σ s t ( v i ) \sigma _{st}\left ( v_{i}\right ) σst(vi)条是通过结点 v i v_{i} vi的,如果这个数量越大,说明该结点越重要,极端情况下,所有路径都需要经过它,那么它也就是枢纽站,比值就为1。所以结点 v i v_{i} vi的最大值为:

    C b ( v i ) = ∑ s ≠ t ≠ v i 1 = 2 ( n − 1 2 ) C_{b}\left ( v_{i}\right )=\sum_{s\neq t\neq v_{i}}^{}1=2 \binom{n-1}{2} Cb(vi)=s=t=vi1=2(2n1)

    则归一化后的中间中心性:

    C b n o r m ( v i ) = C b ( v i ) 2 ( n − 1 2 ) C_{b}^{norm}\left ( v_{i}\right )=\frac{C_{b}\left ( v_{i}\right )}{2\binom{n-1}{2}} Cbnorm(vi)=2(2n1)Cb(vi)

    对无向图,有 ∑ s ≠ t ≠ v i σ s t ( v i ) σ s t = 2 ∑ s ≠ t ≠ v i , s < t σ s t ( v i ) σ s t \sum_{s\neq t\neq v_{i}}^{}\frac{\sigma _{st}\left ( v_{i}\right )}{\sigma _{st}}=2\sum_{s\neq t\neq v_{i},s< t}^{}\frac{\sigma _{st}\left ( v_{i}\right )}{\sigma _{st}} s=t=viσstσst(vi)=2s=t=vi,s<tσstσst(vi),所以中心性乘以2。

    接近中心性

    接近中心性的思想是,趋于中心的结点,满足与其他结点之间有最小平均最短路径。接近中心性定义为:

    C c ( v i ) = 1 l ˉ v i C_{c}\left ( v_{i}\right )=\frac{1}{\bar{l}_{v_{i}}} Cc(vi)=lˉvi1

    其中, l ˉ v i = 1 n − 1 ∑ v j ≠ v i l i , j \bar{l}_{v_{i}}=\frac{1}{n-1}\sum_{v_{j}\neq v_{i}}^{}l_{i,j} lˉvi=n11vj=vili,j是结点 v i v_{i} vi与其他结点之间的平均最短路径。最短路径越小,那么结点的中心性会越高。

    群体中心性

    群体中心性的定义与单个结点的中心性相差不大,就是将一个群体视为一个结点。

    群体度中心性

    群体度中心性,是群体外部的结点连接到群体内部结点的数目。

    C d g r o u p ( S ) = ∣ { v i ∈ V − S ∣ v i 连 接 到 v j ∈ S } ∣ C_{d}^{group}\left ( S\right )=\left | \left \{v_{i}\in V-S|v_{i}连接到v_{j}\in S\right \}\right | Cdgroup(S)={viVSvivjS}

    与度中心性相似,可以利用有向图中的入度或出度。同样,该值可以进行归一化。

    群体中间中心性

    和中间中心性相似,将群体中间中心性定义为:

    C b g r o u p ( S ) = ∑ s ≠ t , s ∉ S , t ∉ S σ s t ( S ) σ s t C_{b}^{group}\left ( S\right )=\sum_{s\neq t,s\notin S,t\notin S}^{}\frac{\sigma _{st}\left ( S\right )}{\sigma _{st}} Cbgroup(S)=s=t,s/S,t/Sσstσst(S)

    群体接近中心性

    群体接近中心性定义为:

    C c g r o u p ( S ) = 1 l ˉ S g r o u p C_{c}^{group}\left ( S\right )=\frac{1}{\bar{l}_{S}^{group}} Ccgroup(S)=lˉSgroup1

    其中, l ˉ S g r o u p = 1 ∣ V − S ∣ ∑ v i ∉ S l S , v j \bar{l}_{S}^{group}=\frac{1}{\left | V-S\right |}\sum_{v_{i}\notin S}^{}l_{S,v_{j}} lˉSgroup=VS1vi/SlS,vj l S , v j l_{S,v_{j}} lS,vj是群体 S S S与群体外的元素 v j v_j vj的最短路径的长度。该长度可以以多种方式定义,一种方法是寻找 S S S中距离 v j v_{j} vj最近成员元素,另一种是使用最大距离或平均距离。

    展开全文
  • 介数中心性和接近中心性指标, 虽然具有较好的刻画节点重要性的能力, 但计算复杂度太高, 难以在大规模网络上使用. 为了权衡算法的效率和效果, Chen 等人提出了一种基于半局部信息的节点重要性排序方法,简称半局部中心...

    介数中心性和接近中心性指标,  虽然具有较好的刻画节点重要性的能力,  但计算复杂度太高,  难以在大规模网络上使用.  为了权衡算法的效率和效果,  Chen 等人提出了一种基于半局部信息的节点重要性排序方法, 简称半局部中心性(semi-local  centrality).  首先定义N(w)为节点Vw的两层邻居度,其值等于从 Vw出发 2步内可到达的邻居的数目,  然后定义

    其中 表示节点 vj的一阶邻居节点的集合.  最终节点 vi的局部中心性定义为  

    可见,  半局部中心性涉及了节点的四阶邻居信息. 

    #%%
    import networkx as nx
    #定义图的节点和边 
    nodes=['1','2','3','4','5','6','7','8','9','10','11',
           '12','13','14','15','16','17','18','19','20',
           '21','22','23'] 
    edges=[('1','2',1),('1','3',1),('1','4',1),('1','5',1),
           ('1','6',1),('1','7',1),('1','8',1),('1','9',1),
           ('2','3',1),('3','4',1),('6','10',1),('7','8',1),
           ('8','9',1),('10','11',1),('10','23',1),('11','12',1),
           ('11','21',1),('11','23',1),('12','13',1),('12','14',1),
           ('12','15',1),('13','14',1),('13','15',1),('13','22',1),('14','15',1),
           ('14','23',1),('15','16',1),('16','17',1),('16','18',1),
           ('16','22',1),('17','18',1),('17','20',1),('17','21',1),
           ('18','19',1),('18','22',1),('19','20',1),('19','21',1),
           ('20','21',1),('20','23',1),('22','23',1)] 
    #%%
    #定义无向图 
    G = nx.Graph()
     
    #往图添加节点和边 
    G.add_nodes_from(nodes)
    G.add_weighted_edges_from(edges) 
    #%%
    N = {}
    Q = {}
    CL = {}
    for node in G.node:
        node_nei = list(G.neighbors(node))
        for n_i in node_nei:
            node_nei = node_nei + list(G.neighbors(n_i))
        node_nei = list(set(node_nei))
        N[node] = len(node_nei)-1
    
    for node in G.node:
        node_nei = list(G.neighbors(node))
        t = 0
        for n_i in node_nei:
            t = t + N[n_i]
        Q[node] = t
        
    for node in G.node:
        node_nei = list(G.neighbors(node))
        t = 0
        for n_i in node_nei:
            t = t + Q[n_i]
        CL[node] = t
    
    for node in G.node:
        print(node,'N-value:',N[node],'Q-value:',Q[node],'CL-value:',CL[node])
    

    结果: 

    1 N-value: 9 Q-value: 67 CL-value: 145
    2 N-value: 8 Q-value: 17 CL-value: 92
    3 N-value: 8 Q-value: 25 CL-value: 101
    4 N-value: 8 Q-value: 17 CL-value: 92
    5 N-value: 8 Q-value: 9 CL-value: 67
    6 N-value: 11 Q-value: 18 CL-value: 104
    7 N-value: 8 Q-value: 17 CL-value: 92
    8 N-value: 8 Q-value: 25 CL-value: 101
    9 N-value: 8 Q-value: 17 CL-value: 92
    10 N-value: 9 Q-value: 37 CL-value: 111
    11 N-value: 12 Q-value: 41 CL-value: 166
    12 N-value: 9 Q-value: 38 CL-value: 157
    13 N-value: 8 Q-value: 39 CL-value: 157
    14 N-value: 9 Q-value: 40 CL-value: 166
    15 N-value: 9 Q-value: 37 CL-value: 156
    16 N-value: 11 Q-value: 39 CL-value: 158
    17 N-value: 9 Q-value: 39 CL-value: 158
    18 N-value: 9 Q-value: 40 CL-value: 148
    19 N-value: 8 Q-value: 28 CL-value: 119
    20 N-value: 10 Q-value: 40 CL-value: 158
    21 N-value: 9 Q-value: 39 CL-value: 148
    22 N-value: 12 Q-value: 42 CL-value: 170
    23 N-value: 14 Q-value: 52 CL-value: 200

    参考:

    Duanbing Chen, Linyuan Lü, Ming-Sheng Shang, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(4):1777-1787.

    任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014(13):1175-1197.

    http://www.xiaowangyun.com/wyblog/detail/?id=121

     

     

    展开全文
  • 文章目录点度中心性(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:来自受欢迎的网页的跳转应该重于不太受欢迎的网页的跳转
    展开全文
  • 利用python绘制热图、计算网络节点degree、kshell、介数中心性、接近中心性、特征向量中心性、PageRank,计算相关性含环境、代码、数据源
  • 首先,中介中心性是个啥?它是一个对于图中顶点重要程度的度量标准。那么它度量哪个方面的重要程度呢? 我们可以使用身边社交网络来做一个例子。这个有点像是我们身边那种社交达人,我们认识的不少朋友可能都是通过...
  • 1、点度中心性(degree centrality) 2、 特征向量中心性(eigenvector centrality) 3、中介中心性(betweenness centrality) 4、接近中心性(closeness centrality) 在图论和网络分析中,中心性(Centrality...
  • 复杂网络中心性1. 度中心度(Degree Centrality)2. 介数中心度(Betweenness Centrality)3. 接近中心度(Closeness Centrality) 1. 度中心度(Degree Centrality) 度中心度(Degree Centrality)是在网络分析中...
  • 特征向量中心性

    千次阅读 2021-08-23 16:28:52
    特征向量中心性的基本思想是,一个节点的中心性是相邻节点中心性的函数。也就是说,与你连接的人越重要,你也就越重要。 特征向量中心性和点度中心性不同,一个点度中心性高即拥有很多连接的节点,但特征向量中心性...
  • 大数据处理中心什么意思 什么是数据处理中心(数据中心) (What Is A Data Processing Centre (Data Center)) A central data processing service is commonly used to fill a critical mission on computers and ...
  • 网络分析中,经常会用到中心性这个概念。通常在中心性的分析角度上有两种出发点:中心度和中心势。 &amp;amp;amp;amp;amp;npsb;&amp;amp;amp;amp;amp;npsb;中心度表示一个节点在网络中处于核心地位的程度;...
  • 原标题:cnc加工是什么意思 什么是cnc加工中心cnc加工是什么意思?CNC加工就是由计算机控制的数控机床对零部件产品进行加工,数控机床的工作原理就像机器人一样,它必须与程序配合使用,并遵循所有的说明。加工的材料...
  • 什么是云计算数据中心? 现在可能会有很多人对云计算、数据中心还有大数据等这类技术和名次感到模糊不清,云计算数据中心是一种基于云计算架构的,计算、存储及网络资源松耦合,完全虚拟化各种IT设备、模块化程度较...
  • 两地三中心什么意思

    千次阅读 2020-04-22 11:05:16
    两地三中心 随着IT应用的快速发展,金融,银行,政府等越来越多的用户要求核心业务7*24不断网,不断电持续运行,进而出现了两地三中心的方案,是一些大型企业因为大自然的灾害而在同城选择两个机房异地选择一个机房...
  • PUE是什么?说说数据中心和PUE

    万次阅读 2019-10-16 14:52:54
    1、什么是PUE? 从数据中心诞生的那天起,高耗能仿佛就成为数据中心的“原罪”。因此谈数据中心,就不能不谈PUE这个名词。PUE的英文全称是Power Usage Effectiveness,又叫电源使用效率。PUE是评价数据中心能源效率...
  • 利用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 """ ''' 程序的算法思想:需要读入一个...
  • 由于互联网的高度开放,使得数据中心也成为了互联网上的一个组成节点,同样也面临着其他节点受到的共同威胁:病毒、蠕虫、木马、后门及逻辑炸弹等。在少数别有用心的人眼中,数据中心保存的各种关键数据是无价之宝...
  • 中心性算法 (Centrality Algorithms)

    千次阅读 2021-03-15 17:34:21
    中心性(Centrality)是社交网络分析(Social network analysis, SNA)中用以衡量网络中一个点或者一个人在整个网络中接近中心程度的一个概念,这个程度用数字来表示就被称作为中心度。也就是说,通过了解一个节点的...
  • 【导读】本节通过对比三种数字货币的形式引出“什么是中心化”,并展示了比特币在去中心化方面的表现如何,最后,向大家阐述了比特币去中心化的原理。 中本聪解决了自己定义的难题“点对点的电子现金”,在这个...
  • 图论算法之中心性算法

    千次阅读 2019-12-12 11:42:27
    中心性算法 小童开始学习算法了~ Closeness Centrality 紧密中心性 (针对连通图) Wasserman and Faust 提出过另一种计算紧密性中心性的公式 (针对非连通图) Harmonic Centrality 调和中心性 (针对非连通图) ...
  • 中心化(Dapp)是什么意思?

    千次阅读 2020-09-27 16:36:22
    谈到去中心化的应用,许多人的第一反应就是用“去中心化”这个词卡住了,而这四个字又是我们提到区块链时必须捆绑起来才能说话的另一个词。还不如将“去中心化”的应用拆开来解释,这样就能更好的理解。 DApp,英文...
  • 什么是T4级数据中心

    千次阅读 2019-02-16 19:15:17
    前几天,我的BOSS问我T4数据中心的定义,我愣了半天,T4?英语四级?NO!是数据中心,第一反应是英语,估计也是被考试考怕了有阴影,那么T4数据中心究竟是怎样的一个标准...
  • http://blog.csdn.net/betarun/article/details/51168259 转载于:https://www.cnblogs.com/1995hxt/p/6825144.html
  • 1、Degree Centrality(度中心性) 1.1 定义 度中心性(Degree Centrality)是在网络分析中刻画节点中心性(Centrality)的最直接度量指标。一个节点的节点度越大就意味着这个节点的度中心性越高,该节点在网络中就越...
  • 什么是中心化交易平台?

    千次阅读 2021-10-12 17:41:21
    特别是在引入自动做市商模式 AMM 之后,DEX 有效解决了长久以来存在的流动不足的问题。虽然,现在的 DEX 还处在发展的初期,但是已经有挑战 CEX 的势头了。 DEX全称Decentralized exchange(去中心化交易所)是...
  • 接近中心性(Closeness Centrality) 中介中心性(Betweenness Centrality)
  • 什么要使用注册中心 有使用过ip:port地址直接调用服务的开发经历么?该段痛苦的经历在此处省略500字......,该种方式的缺点: 需要手动的维护所有的服务访问ip地址列表。 单个服务实现负载均衡需要自己搭建,...
  • 社交网络度量---中心性

    万次阅读 2017-04-20 12:46:03
    中心性定义了网络中一个结点的重要性。换句话说,我们要求的是,在社会网络中,谁是中心角色(具有影响力的用户) 举个例子,某个明星开通了微博,在短短数小时内,就有几十万的粉丝关注了他的微博。我们可以认为,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 967,650
精华内容 387,060
关键字:

中心性是什么

友情链接: CppCoursewareoftsu.rar