文章目錄

• • • 點度中心性（degree centrality）
    • 中介中心性（betweenness centrality）
    • 接近中心性（closeness centrality）
    • 特征向量中心性（eigenvector centrality）
    • 有向圖與PageRank
    • 小結

網絡由節點（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的向量：

$$\mathbf{A}\times \mathbf{x}=?\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}??\begin{array}{l}3\\ 2\\ 3\\ 3\\ 1\end{array}?=?\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}?=?\begin{array}{c}8\\ 6\\ 8\\ 7\\ 3\end{array}?$$
結果向量的第一個元素是用矩陣A的第一行去“獲取”每一個與第一個點有連接的點的值（連接數，點度中心性），也就是第2個、第3個和第4個點的值，然后將它們加起來。

換句話說，鄰接矩陣做的事情是將相鄰節點的求和值重新分配給每個點。這樣做的結果就是“擴散了”點度中心性。你的朋友的朋友越多，你的特征向量中心性就越高。

我們繼續用矩陣A乘以結果向量。如何理解呢？實際上，我們允許這一中心性數值再次沿著圖的邊界“擴散”。我們會觀察到兩個方向上的擴散（點既給予也收獲相鄰節點）。我們猜測，這一過程最后會達到一個平衡，特定點收獲的數量會和它給予相鄰節點的數量取得平衡。既然我們僅僅是累加，數值會越來越大，但我們最終會到達一個點，各個節點在整體中的比例會保持穩定。

現在把所有點的數值構成的向量用更一般的形式表示：

$$?\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}??\begin{array}{l}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}?=?\begin{array}{c}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\end{array}?$$
我們認為，圖中的點存在一個數值集合，對于它，用矩陣A去乘不會改變向量各個數值的相對大小。也就是說，它的數值會變大，但乘以的是同一個因子。用數學符號表示就是：

$$\mathbf{M}\mathbf{x}=\lambda \mathbf{x}$$

$$\mathbf{M}\times ?\begin{array}{c}{x}_1\\ x_2\\ ?\\ x_n\end{array}?=?\begin{array}{c}\lambda x_1\\ \lambda x_2\\ ?\\ \lambda x_n\end{array}?$$
滿足這一屬性的向量就是矩陣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=?\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}?$$

假設有向圖中有n個節點，那么M就是一個n行n列的矩陣，其中的第i行第j列代表從頁面j跳轉到頁面i的概率。例如，M矩陣的第一行代表從ABCD跳轉到頁面A的概率。

然后，我們設每個頁面的初始rank為1/4，4個頁面的初始rank構成向量v：

$$v=?\begin{array}{c}1/4\\ 1/4\\ 1/4\\ 1/4\end{array}?$$
用M第一行乘以向量v，得到的就是頁面A最新rank的合理估計：$0?1/4+1/2?1/4+0?1/4+1/2?1/4=1/4$。Mv的結果就是ABCD四個頁面的新rank：

$$Mv=?\begin{array}{c}1/4\\ 5/24\\ 5/24\\ 1/3\end{array}?$$
然后用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=\left[\begin{array}{ll}0& 0\\ 1& 0\end{array}\right]$$
不斷迭代，最后我們得到的是一個0矩陣：

$$Mv=\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]$$
考慮到B比A重要，這一結果是不合理的，它認為A和B同等重要。為了解決這個問題，我們引入 “心靈運輸”（Teleportation） 的概念。它意味著上網者每一步都有可能隨機輸入一個網址（心靈運輸），跳轉到其他頁面（這意味著每一步，網絡上的每個網頁都有一定的概率被訪問到，它的概率為(1-d)/N，即上網者心靈運輸的概率乘以每個網頁被訪問的概率），而不是點擊網頁上的鏈接。

我們假設上網者在任何頁面繼續向下瀏覽的概率為d=0.85。d也被稱為阻尼系數（damping factor）。1-d=0.15就是上網者停止點擊，隨機跳到新網址的概率，即心靈運輸的概率。設網頁總數為N，那么跳轉到任一網頁的概率為N。因此，調整后的方程式如下：

$$v^{\prime }=dMv+e\frac{1?d}{N}$$
其中的e為單位矩陣，這樣才能與方程式的前半部分相加。

$$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]$$
不斷迭代后，兩個網頁的rank會收斂為：

$$\left[\begin{array}{c}\frac{1}{10}\\ \frac{1}{2}\end{array}\right]\begin{array}{l}0.1\\ 0.18\end{array}]?\left[\begin{array}{l}0.35\\ 0.64\end{array}\right]$$

小結

• 點度中心性：一個人的社會關系越多，他/她就越重要
• 中介中心性：如果一個成員處于其他成員的多條最短路徑上，那么該成員就是核心成員
• 接近中心性：一個人跟所有其他成員的距離越近，他/她就越重要
• 特征向量中心性：與你連接的人社會關系越多，你就越重要
• PageRank：來自受歡迎的網頁的跳轉應該重于不太受歡迎的網頁的跳轉

總結

以上是生活随笔為你收集整理的图或网络中的中心性：点度中心性、中介中心性、接近中心性、特征向量中心性、PageRank的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。