【摘 要】在社交網(wǎng)絡(luò)中常用到圖論來分析解決實際問題，本文闡述了圖形理論在社交網(wǎng)絡(luò)應(yīng)用的理論基礎(chǔ)，同時通過案例分析如何基于圖論理論建立社交網(wǎng)絡(luò)模型和進行應(yīng)用評估。

【關(guān)鍵詞】社交網(wǎng)絡(luò)；圖論；模型；應(yīng)用

一、圖論與社交網(wǎng)絡(luò)

圖論〔Graph Theory〕是數(shù)學(xué)的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點代表事物，用連接兩點的線表示相應(yīng)兩個事物間具有這種關(guān)系。圖論起源于著名的哥尼斯堡七橋問題。[1]

社交網(wǎng)絡(luò)源自網(wǎng)絡(luò)社交，網(wǎng)絡(luò)社交的起點是電子郵件。互聯(lián)網(wǎng)本質(zhì)上就是計算機之間的聯(lián)網(wǎng)，早期的E-mail解決了遠程的郵件傳輸?shù)膯栴}，至今它也是互聯(lián)網(wǎng)上最普及的應(yīng)用，同時它也是網(wǎng)絡(luò)社交的起點。BBS則更進了一步，把“群發(fā)”和“轉(zhuǎn)發(fā)”常態(tài)化，理論上實現(xiàn)了向所有人發(fā)布信息并討論話題的功能，隨著網(wǎng)絡(luò)社交的悄悄演進，一個人在網(wǎng)絡(luò)上的形象更加趨于完整，這時候社交網(wǎng)絡(luò)出現(xiàn)了。

二、社交網(wǎng)絡(luò)分析的圖形方法

數(shù)學(xué)和圖形技術(shù)通常被用來以系統(tǒng)性方式描述社交網(wǎng)絡(luò)，用以描述和解釋社交網(wǎng)絡(luò)分析的數(shù)學(xué)科學(xué)就是圖形理論。相關(guān)社交網(wǎng)絡(luò)分析的的基本概念和測量方法均來自圖形理論。圖形理論的一個巨大優(yōu)勢是可以應(yīng)用于計算的數(shù)學(xué)準則，也因此可以應(yīng)用于商業(yè)問題。在社交網(wǎng)絡(luò)中每個人可以看做一個點，朋友關(guān)系看做連接兩點之間的線。這樣整個社交網(wǎng)絡(luò)就形成一個復(fù)雜網(wǎng)絡(luò)圖，社交網(wǎng)絡(luò)本身就是一個復(fù)雜的人際關(guān)系網(wǎng)絡(luò)。物以類聚，人以群分，采集社交網(wǎng)絡(luò)人際關(guān)系數(shù)據(jù)，進行聚類分析，發(fā)現(xiàn)群組。

三、社交網(wǎng)絡(luò)分析

分析社交網(wǎng)絡(luò)，主要是研究社會實體的關(guān)系連結(jié)以及這些連結(jié)關(guān)系的模式、結(jié)構(gòu)和功能。社交網(wǎng)絡(luò)分析被用于描述和測量行動者之間的關(guān)系或通過這些關(guān)系流動的各種有形或無形的東西，比如信息、資源等。根據(jù)分析的著眼點不同，社交網(wǎng)絡(luò)分析可以分為兩種基本視角：關(guān)系取向(relationalapproach)和位置取向(positional approach)。關(guān)系取向關(guān)注行動者之間的社會性粘著關(guān)系，通過社會連結(jié)(socialconnectivity)本身――如密度、強度、對稱性、規(guī)模等――來說明特定的行為和過程。位置取向則關(guān)注存在于行動者之間的、且在結(jié)構(gòu)上處于相等地位的社會關(guān)系的模式化。它討論的是兩個或兩個以上的行動者和第三方之間的關(guān)系所折射出來的社會結(jié)構(gòu)，強調(diào)用“結(jié)構(gòu)等效”來理解人類行為。

(一)關(guān)系距離及中心性分析

1.度(degree)

度指的是社會網(wǎng)絡(luò)圖中鄰點的個數(shù)。

2.密度(density)

密度指的是圖中各個點之間關(guān)系的緊密程度，是實際分布圖與完備圖的差距。在一個群體的結(jié)構(gòu)型態(tài)分析中，密度是一項重要變量，因為一個團體可以有緊密團體，也可以有疏離團體，一般來說，關(guān)系緊密的團體有效的合作行為較多，信息流通較容易，團體工作績效也會較好，而關(guān)系十分疏遠的團體則常有信息不通、情感支持太少、集體滿意程度較低等問題。社交網(wǎng)絡(luò)圖(無向圖)的密度公式如下：

其中n為圖中節(jié)點的數(shù)目，L為圖中線的數(shù)目。

3.中心度(centrality)

如果一個行動者與很多其他行動者有直接的關(guān)聯(lián)，該行動者就居于中心地位。因此在無向社會網(wǎng)絡(luò)圖中，一個點的度就是該點的中心度。在有向圖中，中心度包括內(nèi)中心度(in-centrality)和外中心度(out-centrality)，三分別對應(yīng)“入度”和“出度”。A. Bavelas最先對中心度的形式特征進行了開創(chuàng)性研究，驗證了如下假設(shè)，即行動者越處于網(wǎng)絡(luò)的中心位置，其影響力越大。

中心度分為三種形式：程度中心性、親近種新型、中介中心性。

(1)程度中心性常用來衡量誰在團體中是最主要的中心地位。無向圖計算公式為：

(2)中介中心性指標

衡量了節(jié)點作為媒介的能力。中介中心性高的節(jié)點掌握了信息流以及商業(yè)機會，進而可以控制兩群節(jié)點，獲得中介利益。社會網(wǎng)絡(luò)分析中衡量一個人作為橋的程度的指標就是中介中心性。

是節(jié)點j到節(jié)點k的捷徑數(shù)，是節(jié)點j到節(jié)點k的快捷方式上有節(jié)點i的快捷方式數(shù)，g是網(wǎng)絡(luò)節(jié)點數(shù)。

(3)群體中介性公式：

含義是，一個圖形中，中介性最高的節(jié)點的中介性與其他人中介性的差距。差距越大，群體中介行數(shù)值越高，表示此團體分成數(shù)個小團體而太依靠某個節(jié)點傳話，這個節(jié)點特別重要。

(二)小團體(子群)分析

派系(subgroup)是社群中的一小群人關(guān)系特別緊密，以至于結(jié)合成一個次團體。在一個社交網(wǎng)絡(luò)圖中，派系指的是至少包含三個點的最大完備子圖。該定義意味著：

派系的成員至少包含三個點；派系是“完備”的，即任何兩點之間都是直接相關(guān)，都是鄰接的；派系是“最大”的，不能再向該派系加入新點，否則將改變“完備”這個性質(zhì)。

1.成分(component)

如果一個點集的任何兩點都可以通過一定的路徑相連，這樣的點集叫做成分(component)。很顯然，派系比成分要嚴格得多，一個成分中的所有點之間不要求都是鄰接的，而派系中的點都必須鄰接。

2.n-派系(n-cliques)

對于一個總圖來說，如果其中的一個子圖滿足如下條件，就稱之為n-派系：在該子圖中，任何兩點之間在總圖中的最短距離最大不超過n。其形式化定義為：

其中d(i，j)是點i和點j之間的距離。

四、案例分析對象及問題

本文研究主要以人人網(wǎng)為例。人人網(wǎng)為整個中國互聯(lián)網(wǎng)用戶提供服務(wù)的SNS社交網(wǎng)站，給不同身份的人提供了一個互動交流平臺，提高用戶之間的交流效率，通過提供發(fā)布日志、保存相冊、音樂視頻等站內(nèi)外資源分享等功能，搭建了一個功能豐富高效的用戶交流互動平臺。對于在人人網(wǎng)中，能否找到一種方法自動地為我的所有好友進行分組。

(一)解決方案思路

人人網(wǎng)是一個復(fù)雜的人際關(guān)系網(wǎng)絡(luò)，物以類聚，人以群分。對于解決本案例中的問題，首先是采集社交網(wǎng)絡(luò)人際關(guān)系數(shù)據(jù)，進行聚類分析，發(fā)現(xiàn)群組。

其次是選擇開發(fā)語言――Python，是一種解釋型的，面向?qū)ο蟮摹в袆討B(tài)語義的高級程序設(shè)計語言。自從20世紀90年代初Python語言誕生至今，它逐漸被廣泛應(yīng)用于處理系統(tǒng)管理任務(wù)和Web編程。具有優(yōu)雅、明確、簡單的特點。能完成系統(tǒng)編程、用戶圖形接口、Internet腳本、組件集成、數(shù)據(jù)庫編程、快速原型、數(shù)值計算與科學(xué)計算編程、游戲、圖像、人工智能、XML、機器人等功能。

再次是熟練掌握復(fù)雜網(wǎng)絡(luò)處理程序庫：

1.Boost Graph Library――準C++標準庫

代碼結(jié)構(gòu)良好、靈活、高運行效率，沒有提供復(fù)雜網(wǎng)絡(luò)分析算法，可幫助 C++ 開發(fā)人員將實際工程問題轉(zhuǎn)化成圖論問題。

2.QuickGraph――.NET平臺下的BGL

BGL在.NET平臺下的實現(xiàn)，提供有方向和無方向的.NET圖形結(jié)構(gòu)圖和算法庫。

3.Igraph――C語言寫的復(fù)雜網(wǎng)絡(luò)分析庫

包括圖論各種經(jīng)典算法以及網(wǎng)絡(luò)分析算法，它提供了一些非常有效的挖掘功能，提供Python、R語言接口。

workX――全面支持復(fù)雜網(wǎng)絡(luò)分析的Python包包括圖論經(jīng)典算法和復(fù)雜網(wǎng)絡(luò)分析算法，具有文檔清晰易讀、程序結(jié)構(gòu)組織較好，執(zhí)行效率比igraph要低很多，便于用戶對復(fù)雜網(wǎng)絡(luò)進行創(chuàng)建、操作和學(xué)習(xí)。利用networkx可以以標準化和非標準化的數(shù)據(jù)格式存儲網(wǎng)絡(luò)、生成多種隨機網(wǎng)絡(luò)和經(jīng)典網(wǎng)絡(luò)、分析網(wǎng)絡(luò)結(jié)構(gòu)、建立網(wǎng)絡(luò)模型、設(shè)計新的網(wǎng)絡(luò)算法、進行網(wǎng)絡(luò)繪制等。

(二)社交網(wǎng)絡(luò)數(shù)據(jù)采集

社交網(wǎng)絡(luò)數(shù)據(jù)的采集主要是通過運營商開放平臺API，用網(wǎng)絡(luò)爬蟲爬取頁面。

開放平臺(Open Platform)在軟件業(yè)和網(wǎng)絡(luò)中，開放平臺是指軟件系統(tǒng)通過公開其應(yīng)用程序編程接口(API)或函數(shù)(function)來使外部的程序可以增加該軟件系統(tǒng)的功能或使用該軟件系統(tǒng)的資源，而不需要更改該軟件系統(tǒng)的源代碼。

網(wǎng)絡(luò)爬蟲(又被稱為網(wǎng)頁蜘蛛，網(wǎng)絡(luò)機器人，在FOAF社區(qū)中間，更經(jīng)常的稱為網(wǎng)頁追逐者)，是一種按照一定的規(guī)則，自動的抓取萬維網(wǎng)信息的程序或者腳本。另外一些不常使用的名字還有螞蟻，自動索引，模擬程序或者蠕蟲。網(wǎng)頁爬蟲所用的網(wǎng)頁搜索策略主要有廣度優(yōu)先搜索策略、最佳優(yōu)先搜索策略、深度優(yōu)先搜索策略，網(wǎng)頁分析算法有網(wǎng)絡(luò)拓撲的分析算法和網(wǎng)頁分析算法等。

(三)簡單網(wǎng)絡(luò)爬蟲過程分析

1.模擬用戶登錄，保存Cookie。所謂Cookie，可以簡單認的為是在瀏覽器端記錄包括登錄狀態(tài)在內(nèi)的各種屬性值的容器名稱。

圖1保存人人網(wǎng)cookie

2.指定抓取入口

圖2人人網(wǎng)抓取入口

3.次級頁面自動發(fā)現(xiàn)

圖3次級頁面

4.已爬地址處理。通過以上方式可以抓取到網(wǎng)頁，但還要從這些頁面中解析出需要的文本信息，如，標題、內(nèi)容、URL鏈接地址等。之后提出這些信息組成一個document對象，通過Lucene將document對象加入到索引，提供用戶搜索用。在實際項目中通常使用HTML解析器(如，HTMLParser)來提取網(wǎng)頁內(nèi)容。

5.信息采集強度控制，主要包括多線程數(shù)和停歇時間。

五、結(jié)論

本文主要介紹了圖論在社交網(wǎng)絡(luò)上的應(yīng)用，通過對圖論和社交網(wǎng)絡(luò)分析基礎(chǔ)知識的分析，探討了在社交網(wǎng)絡(luò)中如何用圖論理論來分析解決實際問題。重點采集了“人人網(wǎng)”人際關(guān)系數(shù)據(jù)，進行聚類分析，發(fā)現(xiàn)群組，對數(shù)據(jù)進行可視化，生成了“人人網(wǎng)社交網(wǎng)絡(luò)圖”。探討了在社交網(wǎng)絡(luò)中常用到圖論來分析解決實際問題。指出社交網(wǎng)絡(luò)信息是一類重要的分析對象，其中蘊含著豐富的社會網(wǎng)絡(luò)信息。

參考文獻：

[1]Carlos Andro Reis Pinherio[著]，漆晨曦等[譯].社交網(wǎng)絡(luò)分析及案例詳解[M].人民郵電出版社，2013.01.

[2]王桂平，王玨，任嘉辰.圖論算法理論、實現(xiàn)及應(yīng)用.北京大學(xué)出版社，2011.11.

[3]徐俊明.圖論及其應(yīng)用.中國科學(xué)技術(shù)大學(xué)出版社，2010.03.

[4]王樹禾.圖論.科學(xué)出版社，2009.08.

[5]殷劍宏、吳開亞.中國科學(xué)技術(shù)大學(xué)出版社，2004.01.

總結(jié)

以上是生活随笔為你收集整理的c语言社交网络,图论在社交网络中的应用研究的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。