你和任何一個(gè)陌生人之間所間隔的人不會(huì)超過(guò)六個(gè)，也就是說(shuō)，最多通過(guò)五個(gè)人你就能夠認(rèn)識(shí)任何一個(gè)陌生人。——六度空間理論

1. 網(wǎng)絡(luò)與社交網(wǎng)絡(luò)

1.1 網(wǎng)絡(luò)模型

現(xiàn)實(shí)生活中，很多問(wèn)題都可以抽象成為一張網(wǎng)絡(luò)。

比如，我們最熟悉的社交圈，朋友與朋友之間的關(guān)系是如何構(gòu)建聯(lián)系的? 在小破站平臺(tái)中，為什么圖圖急需與大V的互關(guān)？

流行性傳染病是如何傳播的？

學(xué)術(shù)論文之間有什么引用關(guān)系？

再舉一個(gè)簡(jiǎn)單的例子，我們把學(xué)校及其各學(xué)院的網(wǎng)站比作節(jié)點(diǎn)，如果我們?cè)L問(wèn)學(xué)校的網(wǎng)站，那我們可以繼續(xù)找到學(xué)院的網(wǎng)站，一些學(xué)院的網(wǎng)站也有通往其他學(xué)院網(wǎng)站的點(diǎn)擊口，這樣的網(wǎng)站及其連接關(guān)系就構(gòu)成了一個(gè)網(wǎng)絡(luò)，不出意外的話，學(xué)校的網(wǎng)站是這個(gè)網(wǎng)絡(luò)中最核心的，因?yàn)樗梢赃B接到幾乎所有學(xué)院的網(wǎng)站。

隨著信息技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)科學(xué)在過(guò)去幾十年飛速發(fā)展，并給人類社會(huì)帶來(lái)了很大的便利。本次，圖圖就以社交網(wǎng)絡(luò)為例，帶大家了解網(wǎng)絡(luò)的基本知識(shí)。

1.2 社交網(wǎng)絡(luò)

圖1是一張經(jīng)典的社交網(wǎng)絡(luò)圖。在這個(gè)社交網(wǎng)絡(luò)中，我們用節(jié)點(diǎn)1-10表示社交圈里的10個(gè)人，而節(jié)點(diǎn)之間的連接則表示他們之間是朋友關(guān)系。

圍繞圖1，我們不禁發(fā)問(wèn)：

• 誰(shuí)的朋友最多？

• 誰(shuí)是這個(gè)網(wǎng)絡(luò)中的關(guān)鍵人物？

• 這個(gè)網(wǎng)絡(luò)的社交效果如何？

以上三個(gè)問(wèn)題中，前兩個(gè)問(wèn)題圍繞的是個(gè)體（節(jié)點(diǎn)），而后面一個(gè)問(wèn)題則是圍繞整個(gè)網(wǎng)絡(luò)。

接下來(lái)，我們就分網(wǎng)絡(luò)構(gòu)建、節(jié)點(diǎn)性質(zhì)和整體性質(zhì)這三部分來(lái)介紹。具體的脈絡(luò)如圖2所示。

2. 網(wǎng)絡(luò)構(gòu)建

2.1 網(wǎng)絡(luò)的數(shù)學(xué)表達(dá)

對(duì)于一個(gè)網(wǎng)絡(luò)，我們用鄰接矩陣的形式對(duì)它進(jìn)行表達(dá)。

鄰接矩陣A是一個(gè)N階的方陣，其中N是網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)。如圖3所示，三個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)的鄰接矩陣就需要填充9個(gè)元素，這些元素代表了節(jié)點(diǎn)間的連接關(guān)系。(矩陣A中的元素分別怎么填)

我們可以將網(wǎng)絡(luò)分為無(wú)權(quán)網(wǎng)絡(luò)和有權(quán)網(wǎng)絡(luò)。無(wú)權(quán)網(wǎng)絡(luò)與有權(quán)網(wǎng)絡(luò)的例子分別在圖4和圖5中展示。我們可以看到，無(wú)權(quán)網(wǎng)絡(luò)將每個(gè)節(jié)點(diǎn)之間的連接平等看待，而有權(quán)網(wǎng)絡(luò)的連接則是有一定重要度區(qū)別的。比如，在無(wú)權(quán)的社交網(wǎng)絡(luò)中，大家只有兩個(gè)關(guān)系，認(rèn)識(shí)或不認(rèn)識(shí)；而在有權(quán)的社交網(wǎng)絡(luò)中，大家互相認(rèn)識(shí)的程度也得以體現(xiàn)，誰(shuí)與誰(shuí)是非常熟悉的深交，誰(shuí)與誰(shuí)只是普通的朋友，在有權(quán)網(wǎng)絡(luò)中一目了然。因此，對(duì)于無(wú)權(quán)網(wǎng)絡(luò)來(lái)說(shuō)，a_ij=1表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j之間有連接，而a_ij=0則表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間沒(méi)有連接。而對(duì)于有權(quán)網(wǎng)絡(luò)來(lái)說(shuō)，每條連接的邊有值為w_ij的權(quán)重，因此a_ij=w_ij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有連接，并且邊的權(quán)重為w_ij；如果節(jié)點(diǎn)i到節(jié)點(diǎn)j之間沒(méi)有連接，則a_ij=0。不難看出，對(duì)于沒(méi)有方向的網(wǎng)絡(luò)來(lái)說(shuō)，其鄰接矩陣是一個(gè)對(duì)稱陣。

有了鄰接矩陣的概念，我們就可以把圖1中的社交網(wǎng)絡(luò)用數(shù)學(xué)的方式表達(dá)出來(lái)，其鄰接矩陣A如圖6所示。

2.2 在MATLAB中構(gòu)建網(wǎng)絡(luò)

拿到了網(wǎng)絡(luò)的鄰接矩陣，我們就可以到MATLAB當(dāng)中去生成網(wǎng)絡(luò)G。我們?cè)贛ATLAB中先錄入矩陣A，接下來(lái)用graph())函數(shù)去構(gòu)造網(wǎng)絡(luò)：

G=graph(A);

graph函數(shù)具體的用法案例：

• G=graph。返回一個(gè)沒(méi)有節(jié)點(diǎn)和邊的空網(wǎng)絡(luò)；

• G=graph(A)。就是我們剛剛使用的，返回一個(gè)鄰接矩陣A代表的網(wǎng)絡(luò)。

• G=graph(s,t)。利用鄰接表創(chuàng)建一個(gè)網(wǎng)絡(luò)，s和t分別代表一條邊的兩個(gè)端節(jié)點(diǎn)。圖7展示了圖1所示的社交網(wǎng)絡(luò)鄰接表，共有18條邊。當(dāng)然，如果我們想返回有權(quán)重的網(wǎng)絡(luò)，我們就給每條邊加一個(gè)權(quán)重，所有權(quán)重組成一個(gè)數(shù)組weights，使用G=graph(s,t,weights)。

接下來(lái)，我們就可以去分析網(wǎng)絡(luò)G的性質(zhì)啦~

3 節(jié)點(diǎn)性質(zhì)

3.1 度中心性

在第一部分，我們想知道在這個(gè)社交網(wǎng)絡(luò)中誰(shuí)的朋友最多，度中心性就是其刻畫方式。我們用k_i表示節(jié)點(diǎn)i連接網(wǎng)絡(luò)中其他節(jié)點(diǎn)的數(shù)目。因?yàn)橐粋€(gè)節(jié)點(diǎn)最多只可能與(N-1)個(gè)其他節(jié)點(diǎn)有連接關(guān)系，因此歸一化的度中心性公式為

3.2 中介中心性

顧名思義，中介在朋友間起到橋梁的作用，使得不是朋友的人也可以進(jìn)行溝通交流。網(wǎng)絡(luò)中誰(shuí)的中介中心性越大，誰(shuí)就能成為網(wǎng)絡(luò)中的樞紐角色。未歸一化的中介中心性數(shù)學(xué)公式為:

式中，g_st為從節(jié)點(diǎn)s到t的最短路徑數(shù)目，n_st^i為從節(jié)點(diǎn)s到t的最短路徑中經(jīng)過(guò)節(jié)點(diǎn)i的條數(shù)。

對(duì)于中介中心性，我們同樣繼續(xù)給出歸一化的公式。設(shè)想一種極端情況，如果這個(gè)節(jié)點(diǎn)在其他所有節(jié)點(diǎn)對(duì)的最短路徑上，同時(shí)其他節(jié)點(diǎn)對(duì)的最短路徑唯一，那么該節(jié)點(diǎn)的中介中心性就是最大的，值為

因此，歸一化的中介中心性公式為

3.3 MATLAB計(jì)算

我們?cè)贛ATLAB中計(jì)算相應(yīng)節(jié)點(diǎn)指標(biāo)的值，基于上一節(jié)生成的網(wǎng)絡(luò)G，代碼如下：

n=numnodes(G);?

deg=degree(G);?

nordeg=deg./(n-1);?

bet=centrality(G,'betweenness');?

norbet=bet./((n-1)*(n-2)/2);

因此，我們計(jì)算得出的社交網(wǎng)絡(luò)案例的節(jié)點(diǎn)性質(zhì)結(jié)果如表1所示。

從表1中不難看出：

• 節(jié)點(diǎn)4有最大的度，其代表的人朋友最多。

• 節(jié)點(diǎn)8雖然度中心性不高，只有3個(gè)朋友，但他的中介中心性是最高的，在整個(gè)社交網(wǎng)絡(luò)中起到關(guān)鍵的橋梁和樞紐作用。

4 整體性質(zhì)

還記得引入部分的最后一個(gè)問(wèn)題嗎，這個(gè)網(wǎng)絡(luò)的社交效果如何。在網(wǎng)絡(luò)整體性質(zhì)部分，我們主要介紹平均路徑長(zhǎng)度來(lái)解決上述疑惑。

要想知道網(wǎng)絡(luò)的平均路徑長(zhǎng)度，我們先引入最短路徑的概念。網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)i和j之間的最短路徑，是連接其邊數(shù)最少的路徑，這條路徑的長(zhǎng)度用d_ij來(lái)表示。那么，網(wǎng)絡(luò)整體的平均路徑長(zhǎng)度L為

接下來(lái)，我們就在MATLAB中把它計(jì)算出來(lái)，代碼如下：

d=distances(G);?

L=sum(sum(d))/(n*(n-1));

在代碼中，我們首先計(jì)算了網(wǎng)絡(luò)中的最短路徑矩陣d，再利用該矩陣進(jìn)行平均路徑長(zhǎng)度的計(jì)算。對(duì)于圖1的社交網(wǎng)絡(luò)，計(jì)算結(jié)果為1.978。也就是說(shuō)，平均來(lái)講，一個(gè)人要接觸網(wǎng)絡(luò)中的另一個(gè)人需要大約2段路程，經(jīng)過(guò)1個(gè)第三方介紹。

在這個(gè)社交圈里，兩個(gè)人之間的平均距離還不到2，互相之間來(lái)往的方便程度是非常高的，我們不得不感嘆，這個(gè)世界是真小??！

上述的案例讓我們發(fā)現(xiàn)，其實(shí)社交網(wǎng)絡(luò)中人與人的間隔還是很小的。在網(wǎng)絡(luò)科學(xué)領(lǐng)域，有一個(gè)六度空間理論的猜想。這個(gè)理論指出，

世界上互不相識(shí)的人其實(shí)只需要很少的中間人就能夠建立起聯(lián)系，具體量化來(lái)說(shuō)，我們和任何一個(gè)陌生人之間所間隔的人一般不會(huì)超過(guò)六個(gè)。

這樣奇妙的“小世界現(xiàn)象”，是不是激發(fā)了你探索網(wǎng)絡(luò)科學(xué)的興趣呢？好了，以上就是我們對(duì)網(wǎng)絡(luò)的一些基本知識(shí)介紹?？磥?lái)，網(wǎng)絡(luò)科學(xué)對(duì)分析一些系統(tǒng)的整體性質(zhì)和系統(tǒng)內(nèi)各要素之間的關(guān)系是非常有益處的，它可以幫助我們完成從發(fā)現(xiàn)問(wèn)題、分析問(wèn)題到解決問(wèn)題的全過(guò)程。希望大家看了今天的內(nèi)容都有所收獲！

• 獲取本文中完整代碼，請(qǐng)關(guān)注微信公眾號(hào)“圖通道”回復(fù)“全家桶”進(jìn)行查找??；

• 查看原文：請(qǐng)關(guān)注微信公眾號(hào)“圖通道”；