本文關(guān)鍵詞：社交網(wǎng)絡(luò)分析及案例詳解，由筆耕文化傳播整理發(fā)布。

　　【摘 要】在社交網(wǎng)絡(luò)中常用到圖論來(lái)分析解決實(shí)際問(wèn)題，本文闡述了圖形理論在社交網(wǎng)絡(luò)應(yīng)用的理論基礎(chǔ)，同時(shí)通過(guò)案例分析如何基于圖論理論建立社交網(wǎng)絡(luò)模型和進(jìn)行應(yīng)用評(píng)估。
　　【關(guān)鍵詞】社交網(wǎng)絡(luò)；圖論；模型；應(yīng)用
　　一、圖論與社交網(wǎng)絡(luò)
　　圖論〔Graph Theory〕是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。圖論起源于著名的哥尼斯堡七橋問(wèn)題。[1]
　　社交網(wǎng)絡(luò)源自網(wǎng)絡(luò)社交，網(wǎng)絡(luò)社交的起點(diǎn)是電子郵件�；ヂ�(lián)網(wǎng)本質(zhì)上就是計(jì)算機(jī)之間的聯(lián)網(wǎng)，早期的E-mail解決了遠(yuǎn)程的郵件傳輸?shù)膯?wèn)題，至今它也是互聯(lián)網(wǎng)上最普及的應(yīng)用，同時(shí)它也是網(wǎng)絡(luò)社交的起點(diǎn)。BBS則更進(jìn)了一步，把“群發(fā)”和“轉(zhuǎn)發(fā)”常態(tài)化，理論上實(shí)現(xiàn)了向所有人發(fā)布信息并討論話題的功能，隨著網(wǎng)絡(luò)社交的悄悄演進(jìn)，一個(gè)人在網(wǎng)絡(luò)上的形象更加趨于完整，這時(shí)候社交網(wǎng)絡(luò)出現(xiàn)了。
　　二、社交網(wǎng)絡(luò)分析的圖形方法
　　數(shù)學(xué)和圖形技術(shù)通常被用來(lái)以系統(tǒng)性方式描述社交網(wǎng)絡(luò)，用以描述和解釋社交網(wǎng)絡(luò)分析的數(shù)學(xué)科學(xué)就是圖形理論。相關(guān)社交網(wǎng)絡(luò)分析的的基本概念和測(cè)量方法均來(lái)自圖形理論。圖形理論的一個(gè)巨大優(yōu)勢(shì)是可以應(yīng)用于計(jì)算的數(shù)學(xué)準(zhǔn)則，也因此可以應(yīng)用于商業(yè)問(wèn)題。在社交網(wǎng)絡(luò)中每個(gè)人可以看做一個(gè)點(diǎn)，朋友關(guān)系看做連接兩點(diǎn)之間的線。這樣整個(gè)社交網(wǎng)絡(luò)就形成一個(gè)復(fù)雜網(wǎng)絡(luò)圖，社交網(wǎng)絡(luò)本身就是一個(gè)復(fù)雜的人際關(guān)系網(wǎng)絡(luò)。物以類聚，人以群分，采集社交網(wǎng)絡(luò)人際關(guān)系數(shù)據(jù)，進(jìn)行聚類分析，發(fā)現(xiàn)群組。
　　三、社交網(wǎng)絡(luò)分析
　　分析社交網(wǎng)絡(luò)，主要是研究社會(huì)實(shí)體的關(guān)系連結(jié)以及這些連結(jié)關(guān)系的模式、結(jié)構(gòu)和功能。社交網(wǎng)絡(luò)分析被用于描述和測(cè)量行動(dòng)者之間的關(guān)系或通過(guò)這些關(guān)系流動(dòng)的各種有形或無(wú)形的東西，比如信息、資源等。根據(jù)分析的著眼點(diǎn)不同，社交網(wǎng)絡(luò)分析可以分為兩種基本視角：關(guān)系取向（relationalapproach）和位置取向（positional approach）。關(guān)系取向關(guān)注行動(dòng)者之間的社會(huì)性粘著關(guān)系，通過(guò)社會(huì)連結(jié)（socialconnectivity）本身  如密度、強(qiáng)度、對(duì)稱性、規(guī)模等  來(lái)說(shuō)明特定的行為和過(guò)程。位置取向則關(guān)注存在于行動(dòng)者之間的、且在結(jié)構(gòu)上處于相等地位的社會(huì)關(guān)系的模式化。它討論的是兩個(gè)或兩個(gè)以上的行動(dòng)者和第三方之間的關(guān)系所折射出來(lái)的社會(huì)結(jié)構(gòu)，強(qiáng)調(diào)用“結(jié)構(gòu)等效”來(lái)理解人類行為。
　　（一）關(guān)系距離及中心性分析
　　1.度（degree）
　　度指的是社會(huì)網(wǎng)絡(luò)圖中鄰點(diǎn)的個(gè)數(shù)。
　　2.密度（density）
　　密度指的是圖中各個(gè)點(diǎn)之間關(guān)系的緊密程度，是實(shí)際分布圖與完備圖的差距。在一個(gè)群體的結(jié)構(gòu)型態(tài)分析中，密度是一項(xiàng)重要變量，因?yàn)橐粋�(gè)團(tuán)體可以有緊密團(tuán)體，也可以有疏離團(tuán)體，一般來(lái)說(shuō)，關(guān)系緊密的團(tuán)體有效的合作行為較多，信息流通較容易，團(tuán)體工作績(jī)效也會(huì)較好，而關(guān)系十分疏遠(yuǎn)的團(tuán)體則常有信息不通、情感支持太少、集體滿意程度較低等問(wèn)題。社交網(wǎng)絡(luò)圖（無(wú)向圖）的密度公式如下：
　　其中n為圖中節(jié)點(diǎn)的數(shù)目，L為圖中線的數(shù)目。
　　3.中心度（centrality）
　　如果一個(gè)行動(dòng)者與很多其他行動(dòng)者有直接的關(guān)聯(lián)，該行動(dòng)者就居于中心地位。因此在無(wú)向社會(huì)網(wǎng)絡(luò)圖中，一個(gè)點(diǎn)的度就是該點(diǎn)的中心度。在有向圖中，中心度包括內(nèi)中心度（in-centrality）和外中心度（out-centrality），三分別對(duì)應(yīng)“入度”和“出度”。A. Bavelas最先對(duì)中心度的形式特征進(jìn)行了開(kāi)創(chuàng)性研究，驗(yàn)證了如下假設(shè)，即行動(dòng)者越處于網(wǎng)絡(luò)的中心位置，其影響力越大。
　　中心度分為三種形式：程度中心性、親近種新型、中介中心性。
　�。�1）程度中心性常用來(lái)衡量誰(shuí)在團(tuán)體中是最主要的中心地位。無(wú)向圖計(jì)算公式為：
　�。�2）中介中心性指標(biāo)
　　衡量了節(jié)點(diǎn)作為媒介的能力。中介中心性高的節(jié)點(diǎn)掌握了信息流以及商業(yè)機(jī)會(huì)，進(jìn)而可以控制兩群節(jié)點(diǎn)，獲得中介利益。社會(huì)網(wǎng)絡(luò)分析中衡量一個(gè)人作為橋的程度的指標(biāo)就是中介中心性。
　　是節(jié)點(diǎn)j到節(jié)點(diǎn)k的捷徑數(shù)，是節(jié)點(diǎn)j到節(jié)點(diǎn)k的快捷方式上有節(jié)點(diǎn)i的快捷方式數(shù)，g是網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。
　　（3）群體中介性公式：
　　含義是，一個(gè)圖形中，中介性最高的節(jié)點(diǎn)的中介性與其他人中介性的差距。差距越大，群體中介行數(shù)值越高，表示此團(tuán)體分成數(shù)個(gè)小團(tuán)體而太依靠某個(gè)節(jié)點(diǎn)傳話，這個(gè)節(jié)點(diǎn)特別重要。
　　（二）小團(tuán)體（子群）分析
　　派系（subgroup）是社群中的一小群人關(guān)系特別緊密，以至于結(jié)合成一個(gè)次團(tuán)體。在一個(gè)社交網(wǎng)絡(luò)圖中，派系指的是至少包含三個(gè)點(diǎn)的最大完備子圖。該定義意味著：
　　派系的成員至少包含三個(gè)點(diǎn)；派系是“完備”的，即任何兩點(diǎn)之間都是直接相關(guān)，都是鄰接的；派系是“最大”的，不能再向該派系加入新點(diǎn)，否則將改變“完備”這個(gè)性質(zhì)。
　　1.成分（component）
　　如果一個(gè)點(diǎn)集的任何兩點(diǎn)都可以通過(guò)一定的路徑相連，這樣的點(diǎn)集叫做成分（component）。很顯然，派系比成分要嚴(yán)格得多，一個(gè)成分中的所有點(diǎn)之間不要求都是鄰接的，而派系中的點(diǎn)都必須鄰接。
　　2.n-派系（n-cliques）
　　對(duì)于一個(gè)總圖來(lái)說(shuō)，如果其中的一個(gè)子圖滿足如下條件，就稱之為n-派系：在該子圖中，任何兩點(diǎn)之間在總圖中的最短距離最大不超過(guò)n。其形式化定義為：
　　其中d（i，j）是點(diǎn)i和點(diǎn)j之間的距離。
　　四、案例分析對(duì)象及問(wèn)題
　　本文研究主要以人人網(wǎng)為例。人人網(wǎng)為整個(gè)中國(guó)互聯(lián)網(wǎng)用戶提供服務(wù)的SNS社交網(wǎng)站，給不同身份的人提供了一個(gè)互動(dòng)交流平臺(tái)，提高用戶之間的交流效率，通過(guò)提供發(fā)布日志、保存相冊(cè)、音樂(lè)視頻等站內(nèi)外資源分享等功能，搭建了一個(gè)功能豐富高效的用戶交流互動(dòng)平臺(tái)。對(duì)于在人人網(wǎng)中，能否找到一種方法自動(dòng)地為我的所有好友進(jìn)行分組。 　　（一）解決方案思路
　　人人網(wǎng)是一個(gè)復(fù)雜的人際關(guān)系網(wǎng)絡(luò)，物以類聚，人以群分。對(duì)于解決本案例中的問(wèn)題，首先是采集社交網(wǎng)絡(luò)人際關(guān)系數(shù)據(jù)，進(jìn)行聚類分析，發(fā)現(xiàn)群組。
　　其次是選擇開(kāi)發(fā)語(yǔ)言  Python，是一種解釋型的，面向?qū)ο蟮摹в袆?dòng)態(tài)語(yǔ)義的高級(jí)程序設(shè)計(jì)語(yǔ)言。自從20世紀(jì)90年代初Python語(yǔ)言誕生至今，它逐漸被廣泛應(yīng)用于處理系統(tǒng)管理任務(wù)和Web編程。具有優(yōu)雅、明確、簡(jiǎn)單的特點(diǎn)。能完成系統(tǒng)編程、用戶圖形接口、Internet腳本、組件集成、數(shù)據(jù)庫(kù)編程、快速原型、數(shù)值計(jì)算與科學(xué)計(jì)算編程、游戲、圖像、人工智能、XML、機(jī)器人等功能。
　　再次是熟練掌握復(fù)雜網(wǎng)絡(luò)處理程序庫(kù)：
　　1.Boost Graph Library  準(zhǔn)C++標(biāo)準(zhǔn)庫(kù)
　　代碼結(jié)構(gòu)良好、靈活、高運(yùn)行效率，沒(méi)有提供復(fù)雜網(wǎng)絡(luò)分析算法，可幫助 C++ 開(kāi)發(fā)人員將實(shí)際工程問(wèn)題轉(zhuǎn)化成圖論問(wèn)題。
　　2.QuickGraph  .NET平臺(tái)下的BGL
　　BGL在.NET平臺(tái)下的實(shí)現(xiàn)，提供有方向和無(wú)方向的.NET圖形結(jié)構(gòu)圖和算法庫(kù)。
　　3.Igraph  C語(yǔ)言寫(xiě)的復(fù)雜網(wǎng)絡(luò)分析庫(kù)
　　包括圖論各種經(jīng)典算法以及網(wǎng)絡(luò)分析算法，它提供了一些非常有效的挖掘功能，提供Python、R語(yǔ)言接口。
　　4.NetworkX  全面支持復(fù)雜網(wǎng)絡(luò)分析的Python包包括圖論經(jīng)典算法和復(fù)雜網(wǎng)絡(luò)分析算法，具有文檔清晰易讀、程序結(jié)構(gòu)組織較好，執(zhí)行效率比igraph要低很多，便于用戶對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行創(chuàng)建、操作和學(xué)習(xí)。利用networkx可以以標(biāo)準(zhǔn)化和非標(biāo)準(zhǔn)化的數(shù)據(jù)格式存儲(chǔ)網(wǎng)絡(luò)、生成多種隨機(jī)網(wǎng)絡(luò)和經(jīng)典網(wǎng)絡(luò)、分析網(wǎng)絡(luò)結(jié)構(gòu)、建立網(wǎng)絡(luò)模型、設(shè)計(jì)新的網(wǎng)絡(luò)算法、進(jìn)行網(wǎng)絡(luò)繪制等。
　�。ǘ┥缃痪W(wǎng)絡(luò)數(shù)據(jù)采集
　　社交網(wǎng)絡(luò)數(shù)據(jù)的采集主要是通過(guò)運(yùn)營(yíng)商開(kāi)放平臺(tái)API，用網(wǎng)絡(luò)爬蟲(chóng)爬取頁(yè)面。
　　開(kāi)放平臺(tái)（Open Platform）在軟件業(yè)和網(wǎng)絡(luò)中，，開(kāi)放平臺(tái)是指軟件系統(tǒng)通過(guò)公開(kāi)其應(yīng)用程序編程接口（API）或函數(shù)（function）來(lái)使外部的程序可以增加該軟件系統(tǒng)的功能或使用該軟件系統(tǒng)的資源，而不需要更改該軟件系統(tǒng)的源代碼。
　　網(wǎng)絡(luò)爬蟲(chóng)（又被稱為網(wǎng)頁(yè)蜘蛛，網(wǎng)絡(luò)機(jī)器人，在FOAF社區(qū)中間，更經(jīng)常的稱為網(wǎng)頁(yè)追逐者），是一種按照一定的規(guī)則，自動(dòng)的抓取萬(wàn)維網(wǎng)信息的程序或者腳本。另外一些不常使用的名字還有螞蟻，自動(dòng)索引，模擬程序或者蠕蟲(chóng)。網(wǎng)頁(yè)爬蟲(chóng)所用的網(wǎng)頁(yè)搜索策略主要有廣度優(yōu)先搜索策略、最佳優(yōu)先搜索策略、深度優(yōu)先搜索策略，網(wǎng)頁(yè)分析算法有網(wǎng)絡(luò)拓?fù)涞姆治鏊惴ê途W(wǎng)頁(yè)分析算法等。
　　（三）簡(jiǎn)單網(wǎng)絡(luò)爬蟲(chóng)過(guò)程分析
　　1.模擬用戶登錄，保存Cookie。所謂Cookie，可以簡(jiǎn)單認(rèn)的為是在瀏覽器端記錄包括登錄狀態(tài)在內(nèi)的各種屬性值的容器名稱。
　　圖1保存人人網(wǎng)cookie
　　2.指定抓取入口
　　圖2人人網(wǎng)抓取入口
　　3.次級(jí)頁(yè)面自動(dòng)發(fā)現(xiàn)
　　圖3次級(jí)頁(yè)面
　　4.已爬地址處理。通過(guò)以上方式可以抓取到網(wǎng)頁(yè)，但還要從這些頁(yè)面中解析出需要的文本信息，如，標(biāo)題、內(nèi)容、URL鏈接地址等。之后提出這些信息組成一個(gè)document對(duì)象，通過(guò)Lucene將document對(duì)象加入到索引，提供用戶搜索用。在實(shí)際項(xiàng)目中通常使用HTML解析器（如，HTMLParser）來(lái)提取網(wǎng)頁(yè)內(nèi)容。
　　5.信息采集強(qiáng)度控制，主要包括多線程數(shù)和停歇時(shí)間。
　　五、結(jié)論
　　本文主要介紹了圖論在社交網(wǎng)絡(luò)上的應(yīng)用，通過(guò)對(duì)圖論和社交網(wǎng)絡(luò)分析基礎(chǔ)知識(shí)的分析，探討了在社交網(wǎng)絡(luò)中如何用圖論理論來(lái)分析解決實(shí)際問(wèn)題。重點(diǎn)采集了“人人網(wǎng)”人際關(guān)系數(shù)據(jù)，進(jìn)行聚類分析，發(fā)現(xiàn)群組，對(duì)數(shù)據(jù)進(jìn)行可視化，生成了“人人網(wǎng)社交網(wǎng)絡(luò)圖”。探討了在社交網(wǎng)絡(luò)中常用到圖論來(lái)分析解決實(shí)際問(wèn)題。指出社交網(wǎng)絡(luò)信息是一類重要的分析對(duì)象，其中蘊(yùn)含著豐富的社會(huì)網(wǎng)絡(luò)信息。
　　參考文獻(xiàn)：
　　[1]Carlos Andro Reis Pinherio[著]，漆晨曦等[譯].社交網(wǎng)絡(luò)分析及案例詳解[M].人民郵電出版社，2013.01.
　　[2]王桂平，王玨，任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用.北京大學(xué)出版社，2011.11.
　　[3]徐俊明.圖論及其應(yīng)用.中國(guó)科學(xué)技術(shù)大學(xué)出版社，2010.03.
　　[4]王樹(shù)禾.圖論.科學(xué)出版社，2009.08.
　　[5]殷劍宏、吳開(kāi)亞.中國(guó)科學(xué)技術(shù)大學(xué)出版社，2004.01.

  本文關(guān)鍵詞：社交網(wǎng)絡(luò)分析及案例詳解，由筆耕文化傳播整理發(fā)布。