社交網絡拓撲結構實證研究

徐焱

摘要：采用傳統統計方法很難直觀了解大規模社交網絡的結構特點和演化特征。通過對科學網博客域名下的網頁進行搜索，建立一個由244 662個博主和113 062對好友關系構成的復雜網絡——科學網博客博主好友關系網絡。采用復雜網絡理論進行研究，測算網絡度分布、平均路徑長度和聚類系數，發現該網絡具有無尺度屬性和小世界屬性，存在相對較多的集散節點，導致網絡的度分布冪指數小于正常范圍。通過逐步刪除高連接度節點，觀察網絡破碎程度，分析了集散節點在維持社交網絡鏈接中的重要性，建議重點關注10%的最高度節點，使網絡更加健壯。該研究有助于闡明在線社交網絡的自組織結構性質。

關鍵詞關鍵詞：在線社交網絡；復雜網絡；拓撲結構；集散節點

DOIDOI：10.11907/rjdk.172730

中圖分類號：TP319

文獻標識碼：A文章編號文章編號：16727800（2017）011017604

0引言

隨著Web 2.0技術的迅速發展，人們進入了在線社交網絡（Online Social Network，OSN）時代。在線社交網絡成為一種廣泛使用的人際交往方式，為用戶帶來了新的體驗，社交網絡研究得到了廣泛關注。

社交網站與一般信息網站的不同之處在于其擁有數量龐大的注冊用戶，而且用戶之間存在錯綜復雜的好友關系，這些好友關系將所有用戶連在一起，形成了一個龐大的好友網絡。隨著新用戶的注冊，陌生人之間隨時都可能形成新的好友關系，這個好友網絡在快速演化。研究這個龐大的好友網絡，從錯綜復雜的關系中理出頭緒，挖掘和發現新的知識，是研究工作的重點。

在線社交網絡涉及經濟、政治、娛樂、軍事、衛生、科技、體育和生活等領域，為知識共享、信息傳遞和人類交互提供了便捷的通信平臺，帶來了巨大的商業機會。在線社交網絡中大量信息來源不確定，存在一些不良、虛假或煽動性信息，可能對社會穩定產生很大的負面影響。隨著在線社交網絡的普及，網絡已經成為輿論傳播的重要途徑。因此，如何通過社會網絡監測控制輿論特別是恐怖行為的傳播，已經成為一個非常急迫的問題[1]。社交網絡包含大量的內容和鏈接數據，可以用于分析。鏈接數據本質是社會網絡和實體間通信的圖形結構。在線社交網絡拓撲結構的實證分析，有助于確定網絡的重要節點、社區、鏈路和演化區域，理解各種動態過程。

在線社交網絡具有復雜性、大規模、非線性和快速演化等特征，與一般網絡有很大區別。因此，與傳統信息系統相比，其挖掘目標和研究方法大不相同。

關于復雜網絡的研究方興未艾，1998年Strogatz和Watts[2]在《Nature》雜志上發表文章，提出了小世界（SmallWorld）網絡模型概念。1999年Barabasi和Albert[3]在《Science》上發表文章，提出了無尺度（ScaleFree）網絡概念，指出許多復雜網絡鏈接度分布具有典型的冪律形式。這兩項開創性研究掀起了一股研究復雜網絡熱潮。

著名科學家錢學森把復雜網絡定義為具有自相似、自組織、小世界、無尺度的網絡。復雜網絡在自然界、工程界、生物界和人類社會界中廣泛存在，如蛋白質網絡、食物鏈網絡、新陳代謝網絡、萬維網、Internet、電力網、鐵路網、航空網、演員合作網絡、朋友關系網、科學家合作網及金融網絡等都是復雜網絡。

復雜網絡的復雜性主要體現在節點數量巨大，而且節點之間的連接關系較為復雜，既不像隨機網絡那樣具有完全不確定的連接關系，也不像規則網絡那樣具有完全確定的連接關系，而是介于兩者之間[4]。復雜網絡及其演化研究已經成為多學科交叉的研究方向。

社交網絡擁有數量龐大的用戶，而且用戶之間的連接關系錯綜復雜，是一種典型的復雜網絡。因此，可以用復雜網絡理論研究社交網絡。

本文重點研究科學網博客，即Science Net Blog[5]。科學網博客是提供交流和共享科學信息的平臺，在中國擁有2萬多注冊用戶。通過網絡爬蟲抓取網站上的公開信息獲取數據，并將數據用于研究。研究重點是該網站內的社交網絡用戶，具體研究用戶關系圖中最大連接片的屬性，而不是整個用戶社區，這代表了構建復雜系統模型的新框架。通過計算科學網博客網絡的拓撲特性，包括度分布、平均聚類系數和平均路徑長度，進行詳細分析，證實了科學網博客既是無尺度網絡又是小世界網絡；此外，還證明了復雜網絡中重要節點的數量非常少，這意味著如果控制這些節點，消息的傳播將被控制。

1復雜網絡拓撲屬性

1.1拓撲屬性

（1）節點度和度分布。節點的度是網絡中一個節點連接到該網絡中其它節點的邊數，用k表示。網絡的度分布是該網絡中所有節點的度的概率分布[6]。

（2）路徑長度和平均路徑長度。路徑長度是從一個節點到另一個節點必須遍歷的最小邊數[7]。平均值長度是任何節點對之間的路徑長度平均值。

（3）聚類系數。聚類系數表示在一個網絡中同一個頂點的鄰居之間有邊連接的平均概率。按照Watts和Strogatz的定義，如果一個節點v有k個鄰居，其鄰點將可能存在的最大邊數是2，實際存在的邊數用Ei表示，則節點v的聚類系數定義為；所有節點的聚類系數的平均值定義為整個網絡的聚類系數C[2]。

1.2隨機、無規模和小世界網絡

20世紀60年代，鄂爾多斯（Red）和雷尼（Reyni）[8]發表了開創性的論文，之后隨機網絡被廣泛研究。隨機網絡圖通常通過隨機添加鏈接到靜態節點集來構造，這意味著每個節點以相等概率p隨機連接到圖形中。大規模隨機圖具有高斯度分布，隨機網絡的主要特征是平均路徑長度很短、聚類系數低。相反，規則網絡通常具有非常長的平均路徑和高聚類系數。

描述真實世界網絡的大多數圖形顯著偏離了簡單的隨機圖模型。Barabasi和Albert[3]發現一些網絡具有冪律形式的度分布：即節點具有度k的概率為Prob（k）～k-λ。度數指數λ通常在2～3之間，并且度分布的冪律衰減非常緩慢（“長尾”），這意味著網絡缺乏特征尺度，這樣的網絡稱為“無尺度”網絡。Barabasi和Albert提出了“BarabasiAlbert模型”，并展示了無尺度網絡可以源自一個過程，每個連接到網絡的節點優先連接那些度比較高的節點。endprint

Watts和Strogatz[2]發現了一些網絡介于規則網絡和隨機網絡之間。規則網絡的平均路徑長度很長，但是它的聚類系數很高；隨機網絡平均路徑長度小，但是聚類系數很低。而介于這兩者之間的網絡，具有較小的平均路徑和較高的聚類系數，這類網絡稱為小世界網絡。

社交網絡指社會個體成員之間通過社會關系結成的網絡體系，社交網絡由個體和個體間連接關系組成。在社交網絡中，節點代表社會環境中的人或其它實體，邊代表實體之間的相互作用、合作或相互影響。因此，社交網絡可被看作是一種特殊類型的復雜網絡，建模為無向圖G=（V，E），即每個節點v∈V和無向邊緣∈E。

2數據采集

本文針對科學網（http：//www.sciencenet.cn）中的科學網博客（http：//www.sciencenet.cn/blog）進行研究。科學網主要為網民提供快捷權威的科學新聞報道、豐富實用的科學信息服務以及交流互動，目標是建成最具影響力的全球華人科學社區。科學網博客采用實名注冊，博主多為一線研究人員，有院士、重點實驗室主任等知名學者，研究內容涉及生命科學、信息科學等多個領域，可在一定程度上反映不同領域的前沿研究。

隨著時間的推進，科學網博客注冊用戶不斷增加，用戶間的關系逐漸復雜。本文利用網絡爬蟲爬取到該博客中共有244 662個博主和113 062對好友關系，采集的數據截至2012年3月。這244 662個博主組成的好友網絡中包含大量的孤立節點，即這些節點沒有任何好友關系，有一些很小的網絡碎片以及一個巨大的連接片。

因為孤立的節點與整個網絡中的其它節點沒有任何鏈接，無法傳播信息，因此不對網絡造成任何影響。同理，較小的網絡碎片之間存在的邊極少，因此傳播消息的范圍也很小，對整個網絡的影響幾乎為零。本文的研究對象就是由這個巨大連接片組成的子網絡，包含了20 236個博客用戶節點和113 014對好友關系。這個僅有8.27%節點的巨大連接片中的好友關系占到整個網絡的99.96%。

下面詳細分析這個社交網絡的拓撲結構，以及一些統計屬性，包括度數分布、平均最短路徑長度以及聚類系數，揭示在線社交網絡的內部特征。

3網絡結構拓撲分析

本節描述了網絡的拓撲特性，并與現實觀察到的網絡進行比較。

3.1度分布

許多復雜網絡的度分布都符合冪律分布，包括離線社交網絡。對科學網博主好友關系網絡中的最大連通子網進行研究，繪制網絡的度分布和度分布的對數分布圖，如圖1所示。

圖1博客網度分布與度的對數分布

通過統計發現該網絡的度分布符合冪律P（k）～k-γ，其中γ=1.5±0.1，即該網絡是無尺度網絡。但是，通過表1發現該無尺度網絡不同于現實世界中已經發現和驗證的無尺度網絡。現實世界中無尺度網絡的冪指數γ一般在2～3之間[9]，但是本網絡的冪律指數非常小，只有大約1.5。下面詳細研究這一現象。

經過研究發現，隨著γ的增長，網絡從異質向同質轉變。

現實網絡中，γ≤1是不存在的。當1<γ≤2時，網絡包含比較多的集散節點，即度較高的節點較多。當2<γ

≤3時，網絡中包含大量的度很小的節點和極少的集散節點；當γ>3時，網絡中絕大多數節點的度很相近，但是基本不存在集散節點。

當γ>3時，網絡中由于基本不存在集散節點，所以網絡消息傳輸率很低，這種網絡在現實生活中基本不存在。

當1<γ≤2時，集散節點較多，雖然此時消息傳輸率很高，但是維持這些集散節點花費的代價太大，所以此種網絡在現實生活中也很少。

當2<γ≤3時，網絡既能確保消息的傳輸率又不需要花費太高的代價，所以此種網絡在現實生活中最為常見，例如：蛋白質網絡、作家合作網、Internet路由網等等。

而本文研究的網絡是一個虛擬網絡，不受資源限制，即使有較多的集散節點也不需要花費人力物力進行維護，因此本研究網絡中γ<2并不奇怪。另外，還推測出該網絡的信息傳輸效率較高，因為它包含了相對較多的集散節點。

3.2平均路徑長度和聚類系數

計算網絡的平均路徑長度，即任意兩個節點之間最短路徑的平均值。本網絡中該值為3.29，這意味著在一個有兩萬多個節點的網絡中，從一個用戶到另一個用戶平均只需點擊4次就可到達。圖2顯示了最短路徑長度分布，很明顯，大部分的路徑長度在2～4之間。雖然博客網絡節點很多，規模很大，且很稀疏，但是它的平均路徑很短，這驗證了著名的“六度分隔”理論[10]。

圖2博客網最短路徑長度分布

無向網絡中聚類系數

Ci=2Eiki（ki-1）（1）

Ei是節點i的所有鄰居之間存在的邊數目，ki（ki-1）/2是節點i的鄰居間存在邊的最大數量，網絡的聚類系數C是所有Ci的平均值。本網絡中C=0.193，而相同規模的隨機網絡聚類系數Crand=/N=11.16/20 263=0.000 55，其中是所有節點度的平均值。很明顯，C比Crand大得多。

綜合這兩點可以得出，研究網絡的聚類系數比隨機網絡的聚類系數大得多，而比規則網絡的平均路徑長度小得多。因此，本網絡是具有小世界屬性的網絡。

3.3集散節點重要性

在電力網絡中，對重要的斷路器、發電單元等進行監控和保護，可以有效防止由級聯故障引起的大范圍停電，從而避免大的經濟損失；在大規模計算機網絡中，可以對關鍵節點的服務器有針對性地進行備份，既能有效節省資源，又可保證網絡的魯棒性；在傳染病、病毒傳播網絡中，可以優先治療、隔離病源，有效防止病毒的傳播和擴散；在發掘復雜網絡社區時，可以通過集散節點確定社區中心。社交網絡的結構很大程度上依賴于高連接度的節點，而這些高連接度的集散節點與信息傳播、蓄意攻擊的脆弱性和隨機攻擊的魯棒性都有很大關系[11]。下面研究在線社交網絡中解散節點對整個網絡的影響。

研究方法是逐步移除具有高連接度的節點，然后計算剩下的最大連通片大小，剩下的最大連通片大小就是信息能在網絡上傳播的最大范圍。隨著高連接度節點移除，最大的連通網絡開始分解成較小的網絡碎片。逐步移除Top1%到Top10%的高連接度節點。當移除1%的節點后，最大連通網絡是原網絡大小的68%；移除5%后，是原網絡的40%；移除10%，此時最大連通網絡是原網絡的10%。另外計算了移除20%的情況，此時，整個網絡破碎成幾千個很小的網絡，而最大的網絡只有18個節點。圖3顯示分解后最大連通網絡的大小。

圖3移除一定比例節點與最大連通網絡規模的關系

本研究網絡中只需關注10%的節點，這種情況下，即使受到蓄意攻擊，網絡也不會癱瘓；即使有人發布恐怖消息，消息傳播的范圍也不會超過網絡規模的10%。如果關注網絡中20%的節點，雖然監控效果會更好，但是付出的代價太大。所以，選擇監控10%的節點時監控效果最好，而代價又是可以承受的。

4結語

本文對科學網博客采集的數據集進行了在線社交網絡實證研究。數據顯示社會網絡的度分布具有無尺度網絡特征——冪律。然而它具有比現實世界網絡更小的冪律指數。本文驗證了社交網絡具有非常短的平均路徑長度和較高的聚類系數，符合小世界網絡特征。研究了最短路徑長度的頻率，證明了該網絡符合著名的“六度分離”理論。關注整個網絡10%的節點時，網絡將更加健壯。本研究有助于了解在線社交網絡的拓撲特征。今后將研究如何建立網絡的圖結構和動態演化，探討影響網絡增長的因素等。

參考文獻參考文獻：

[1]V KREBS. Mapping networks of terrorist cells[J]. Connections，2002，24（3）：4352.

[2]D J WATTS， S H STROGATZ.Collective dynamics of “smallworld” networks[J].Nature，1998（393）：440442.

[3]A L BARABASI， R ALBERT. Emergence of scalling in random networks[J].Science，1999（286）：509512.

[4]王林，戴冠中.復雜網絡的Scalefree性、Scalefree現象及其控制[M].北京：科學出版社，2009：511.

[5]科學網[EB/OL].http：//www.sciencenet.cn/blog.

[6]LAN AMARAL， A SCALA， M BARTHELEMY，et al. Stanley[EB/OL]. http：//ishare.iask.sina.com.cn/f/23802485.html，Classes of small.

[7]E BULLMORE， O SPORNS. Complex brain networks： graph theoretical analysis of structural and functional systems[J].Nature Reviews Neuroscience，2009（3）：186198.

[8]P ERDOS， A RENYI. On random graphs[J].Publications Mathematics，1959（6）：290297.

[9]R ALBERT， A L BARAB′ASI.Statistical mechanics of complex network[J].Reviews of Modern Physics，2002（74）：4797.

[10]艾伯特拉斯洛，巴拉巴西.網絡鏈接新科學[M].長沙：湖南科學技術出版社，2007.

[11]P HOLM， B J KIM， C N YOON，et al.Attack vulnerability of complex networks[J]. Physical Review E，2002（65）：254259.

責任編輯（責任編輯：杜能鋼）endprint