愛華網(wǎng)SNS社交網(wǎng)絡(luò)在近幾年流行起來，并呈現(xiàn)出火爆的增長趨勢。在仿制國外Facebook、twitter等成功先例的基礎(chǔ)上，國內(nèi)的人人網(wǎng)、新浪微博等一系列社交網(wǎng)絡(luò)正風(fēng)生水起。
這些社交網(wǎng)站表面上看起來十分普通和其他網(wǎng)站別無二致，但我們可以研究它們背后更深層次的數(shù)學(xué)原理，從而更有利于推廣營銷。在后面的分析中，我會(huì)分別舉例，大家就會(huì)明白實(shí)際中的應(yīng)用價(jià)值。
我們需要考慮的是怎樣度量一個(gè)網(wǎng)絡(luò)。網(wǎng)絡(luò)其實(shí)就是一張圖，圖中有各個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)連接起來，形成邊。在社交網(wǎng)絡(luò)中，每個(gè)人就是一個(gè)節(jié)點(diǎn)，人們通過好友關(guān)系相互連接。節(jié)點(diǎn)是有權(quán)重的，就像人具有影響力一樣。
給你一張網(wǎng)絡(luò)拓?fù)鋱D，你怎樣挖掘這張圖所蘊(yùn)含的信息呢？你怎樣知道圖中哪一個(gè)節(jié)點(diǎn)是最重要的？事實(shí)上有很多方法，我們自己也可以定義度量的標(biāo)準(zhǔn)。經(jīng)常用到的有DegreeCentrality，Eigenvector Centrality，KatzCentrality，PageRank，Closeness Centrality，BetweennessCentrality，Transitivity……它們從簡單到復(fù)雜，從偏重某個(gè)屬性到綜合考慮，很多都在現(xiàn)實(shí)中合理地使用著，例如PageRank就是Google使用的網(wǎng)頁排名方法。
1. Degree Centrality（節(jié)點(diǎn)度）
這是對網(wǎng)絡(luò)最為簡單直白的一種度量：僅僅統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)有多少邊。它的現(xiàn)實(shí)意義在于有更多邊的節(jié)點(diǎn)具有更大的連接性，就像有更多好友的人具有更大的影響力。例如對一個(gè)產(chǎn)品做推廣營銷，我們發(fā)放免費(fèi)的試用樣品給消費(fèi)者，如果消費(fèi)者滿意他們就會(huì)購買，并且推薦給自己的朋友也去購買。這就是口碑影響力。作為廠家，我們當(dāng)然希望將樣品發(fā)放給更具影響力的人，因?yàn)樗麄兊囊痪滟澝罆?huì)傳遞到更多的節(jié)點(diǎn)上，為我們帶來更多的潛在客戶。我們知道，圖分為有向圖和無向圖，他們的區(qū)別在于節(jié)點(diǎn)之間的聯(lián)系是否是雙向的。例如Facebook或者人人網(wǎng)中的好友關(guān)系，就是一個(gè)無向圖，你是我的好友那么我也是你的好友；而twitter或者新浪微博則是一個(gè)有向圖，因?yàn)槲摇瓣P(guān)注”（follow）某些人，又有另外一些人“關(guān)注”我，這是一個(gè)從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)的關(guān)系，不具有可逆性。我們在討論DegreeCentrality時(shí)，對于有向圖來說，其實(shí)有in-degree centrality和out-degreecentrality兩種。例如在微博上很多人關(guān)注了李開復(fù)，也就是說有很多節(jié)點(diǎn)指向他，那么李開復(fù)就具有很高的in-degreecentrality.但是要小心，in-degree高的節(jié)點(diǎn)不一定是最有價(jià)值的，例如在論文參考文獻(xiàn)引用中，一篇文章的in-degree很高表示很多人引用了這篇論文。這篇文章可能提出了一個(gè)有價(jià)值的研究問題，但是卻犯了明顯的錯(cuò)誤，于是大家在寫這個(gè)研究方向的論文時(shí)都會(huì)說：“快去圍觀這篇文章，作者太SB了，哈哈哈哈……”
我們希望通過Degree Centrality來找出最有影響力的節(jié)點(diǎn)們。問題來了，想要獲得具有DegreeCentrality最高的前10個(gè)節(jié)點(diǎn)，我們需要知道整張圖的結(jié)構(gòu)才行。從數(shù)學(xué)上講，即需要得到圖的鄰接矩陣A，對于A中的每一行統(tǒng)計(jì)有多少個(gè)1，最后進(jìn)行排序取前k個(gè)即可得到DegreeCentrality值最高的前k個(gè)節(jié)點(diǎn)。這在實(shí)際中并不可行，你并不是Facebook的所有者或者人人網(wǎng)的管理員，你怎么知道整個(gè)社會(huì)網(wǎng)絡(luò)里誰的好友更多？
2. Eigenvector Centrality（特征向量）
這是對Degree Centrality的一種改進(jìn)版。我們希望得到節(jié)點(diǎn)重要性的估值，但什么是重要性？什么是影響力？在DegreeCentrality中，所有的鄰居節(jié)點(diǎn)都是平等的。而在實(shí)際情況中，不同的鄰居節(jié)點(diǎn)可能會(huì)有不同的價(jià)值。例如我有10個(gè)好友，他們都是普通人，而如果有一個(gè)人他也有10個(gè)好友，但是他的好友都是李嘉誠巴菲特奧巴馬們，顯然，我比不上他，自慚形穢了。
為此我們建立另一種模型：給鄰居節(jié)點(diǎn)打分，高分的鄰居會(huì)給予我更多積極的影響，使得我的得分也升高。設(shè)xi(t)為節(jié)點(diǎn)i在t時(shí)刻的centrality評估值（得分），centrality值越高說明這個(gè)節(jié)點(diǎn)越重要。則
（1）
或者表示為矩陣形式
（2）
其中A為圖的鄰接矩陣。不知道鄰接矩陣？回去復(fù)習(xí)線性代數(shù)離散數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)吧……
公式（1）比較好理解。基本思想其實(shí)就是說，節(jié)點(diǎn)j為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)（我所說的鄰居意思就是他們有邊相連），在t-1時(shí)刻，我們對j疊加求和，意思就是統(tǒng)計(jì)節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)的centrality值，然后累加，就是t時(shí)刻節(jié)點(diǎn)i的centrality值。這個(gè)公式對所有節(jié)點(diǎn)有效，如果我的鄰居們的centrality值改變了，我的值也會(huì)改變，所以這是一個(gè)不斷迭代的過程，直到最后所有節(jié)點(diǎn)的值在一個(gè)閾值內(nèi)進(jìn)行可忽略的波動(dòng)，即收斂。
第二個(gè)公式x(0)是0時(shí)刻初始化時(shí)所有節(jié)點(diǎn)的centrality值，它是一個(gè)數(shù)組。而
不斷迭代就可以得到公式（2）了。
于是x(0)可以看作是A的特征向量Vi的線性組合，我們可以選取合適的ci使得等式
（3）
成立。
結(jié)合（2）（3）兩個(gè)式子，我們得到
（4）
其中ki為矩陣A的特征值，k1為特征值中的最大值。
當(dāng)k>1時(shí)，，于是當(dāng)時(shí)，，或者直接表示為
（5）
這就是eigenvectorcentrality。我們?nèi)绻玫綀DA的鄰接矩陣的特征向量，那么這個(gè)向量x就是所有節(jié)點(diǎn)的eigenvectorcentrality值。我們只需解方程（5）即可。它的一個(gè)明顯的屬性就是，xi即節(jié)點(diǎn)i的eigenvectorcentrality，與該節(jié)點(diǎn)所有鄰居的eigenvector centrality之和成正比。即
（6）
所以，這正解決了我們之前的問題，它將我們鄰居的重要性施加到我們自己身上。有幾種情況會(huì)使得xi的值很大，一是節(jié)點(diǎn)有很多鄰居，二是它有一個(gè)重要鄰居（該鄰居擁有高eigenvectorcentrality值），或者以上兩種情況同時(shí)存在。
同樣的問題在這里也存在，那就是我們必須知道圖的鄰接矩陣，也就是整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。如果網(wǎng)絡(luò)中有100萬個(gè)節(jié)點(diǎn)，我們生成一個(gè)100萬×100萬的矩陣也是困難的。另外，還有可能出現(xiàn)下面的情況
這是一個(gè)有向圖，注意節(jié)點(diǎn)A，它沒有in-degree，也就是說沒有其他節(jié)點(diǎn)可以影響到它的centrality值。假如A的centrality值是0，那么它對它的3個(gè)鄰居的貢獻(xiàn)也為0，其中最上面的那個(gè)鄰居只有A對它施加影響，于是它的centrality值也為0，最后我們一步步地推斷，會(huì)發(fā)現(xiàn)整個(gè)圖所有節(jié)點(diǎn)的centrality值都是0，也就是說圖的鄰接矩陣A=0.這不是我們預(yù)想的那樣，因?yàn)槿绻覀兿Ｍ麑W(wǎng)頁做PageRank，這將導(dǎo)致所有頁面的PageRank值都一樣，沒法做排名了。
上邊提到兩種網(wǎng)絡(luò)模型，都有著這樣那樣的缺陷。下面我們繼續(xù)來改善建模。
3. Katz Centrality
Katz Centrality解決了之前的問題。它的原理與eigenvectorcentrality差不多，只是我們給每一個(gè)節(jié)點(diǎn)提供一個(gè)初始化的centrality值β，即對式（6）做簡單改變：
（7）
α 和 β 都是正常數(shù)。
使用矩陣表達(dá)式，我們得到：
（8）
（9）
我們只關(guān)心centrality值的相對性，也就是說不管你的centrality值是10還是100，我們只關(guān)注你的centrality值是不是大于我的centrality值，因?yàn)槲覀兿Ｍ业絚entrality值最大的前10個(gè)節(jié)點(diǎn)，目的是做排名。于是β可以設(shè)置為1，于是KatzCentrality表達(dá)為：
（10）
事實(shí)上α和β的比值體現(xiàn)了對鄰居節(jié)點(diǎn)centrality值的側(cè)重，如果α=0那么所有的節(jié)點(diǎn)的centrality值都是β=1了，完全不受鄰居的影響了。所以說這個(gè)公式更具有普遍性，這就是數(shù)學(xué)之美。
需要注意的是α不可以太大，當(dāng) 會(huì)導(dǎo)致，于是無法收斂。所以有.
要計(jì)算Katz centrality，就要做逆矩陣運(yùn)算 ，直接計(jì)算的復(fù)雜度為O(n3)。我們可以用迭代法
（11）
4. PageRank
Katzcentrality的一個(gè)缺陷就是，一個(gè)擁有高centrality值的節(jié)點(diǎn)會(huì)將它的高影響力傳遞給它的所有鄰居，這在實(shí)際生活中可能并不恰當(dāng)。比如說Google的網(wǎng)頁有很高的centrality值，同時(shí)Google也鏈接了海量的頁面。如果Google的網(wǎng)頁鏈接到了我的網(wǎng)頁，那我的網(wǎng)頁作為一個(gè)無名小卒centrality值豈不是有可能比Google還高？我們希望Katzcentrality能夠由節(jié)點(diǎn)的out-degree稀釋，或者說我的centrality值能平均分給我的鄰居，而不是給每個(gè)鄰居都得到我的整個(gè)centrality值。用數(shù)學(xué)語言表達(dá)為
（12）
對比公式（7）就很容易理解這里對Katz centrality做的修改了。
對于沒有外鏈的節(jié)點(diǎn)（例如很多鏈接指向了一張圖片，但圖片是沒有out-degree指向別處的），將其值設(shè)為1.我們將式（12）寫為矩陣形式：
（13）
其中D是對角矩陣，.同樣設(shè)β=1，上式可以變形為
（14）
這就是著名的PageRank算法。
同樣，α的取值也是有范圍的，它應(yīng)該小于AD-1最大的特征值的倒數(shù)。對于無向圖來說，這個(gè)值是1，對于有向圖來說就不一定了。Google的搜索引擎將α設(shè)為0.85。同樣，要執(zhí)行這個(gè)算法，我們需要知道整個(gè)圖的拓?fù)浣Y(jié)構(gòu)。
5. HITS算法
與PageRank算法類似，HITS也是在網(wǎng)絡(luò)建模和權(quán)重排名中比較經(jīng)典的算法。
有的時(shí)候我們希望把高centrality值賦予那些鏈接了很多重要節(jié)點(diǎn)的節(jié)點(diǎn)，例如綜述性的學(xué)術(shù)論文引用了該研究領(lǐng)域內(nèi)的大量重要論文，于是這篇綜述也被認(rèn)為很有價(jià)值。因?yàn)榧词惯@篇論文沒有為該科研領(lǐng)域做出什么突破，但它總結(jié)了已有成果，告訴大家去哪里找做出了突出貢獻(xiàn)的論文。
于是我們擁有兩種節(jié)點(diǎn)：authorities（權(quán)威型）的節(jié)點(diǎn)包含了具有貢獻(xiàn)的原創(chuàng)信息，hubs（樞紐型）節(jié)點(diǎn)總結(jié)了很多信息，指向了很多authorities節(jié)點(diǎn)。Kleinberg是康奈爾大學(xué)一位十分牛B的年輕教授（70后年輕有為啊?。?，他提出了hyperlink-inducedtopic search (HITS)算法來量化計(jì)算authority centrality和hubscentrality。
在HITS中對于某個(gè)節(jié)點(diǎn)i，xi用來表示authoritycentrality，yi用來表示hubscentrality。每個(gè)節(jié)點(diǎn)既有authority屬性又有hubs屬性。節(jié)點(diǎn)若有高xi值則該節(jié)點(diǎn)被很多其他hub節(jié)點(diǎn)關(guān)注，如論文被大量引用、微博有很多粉絲。節(jié)點(diǎn)若有高yi值則該節(jié)點(diǎn)指向了很多其他authority節(jié)點(diǎn)，例如一篇綜述論文，又例如hao123.com這樣的網(wǎng)址導(dǎo)航站點(diǎn)（理解百度為什么要收購hao123了吧）。
用數(shù)學(xué)語言描述如下：
（15）
或者矩陣表達(dá)式
（16）
合并演化得到
（17）
這意味著authority centrality為AAT的特征向量，而hubscentrality為ATA的特征向量。有趣的是AAT和ATA擁有相同的特征值λ，大家可以自行證明。
繼續(xù)演化，我們對式（17）左乘一個(gè)AT，得到，也就是說
（18）
我們知道了x，也就可以計(jì)算得到y。
6. 社交網(wǎng)絡(luò)建模工具（Python）
最近比較忙，如果沒有需求，這個(gè)系列可能就不會(huì)再繼續(xù)寫下去了。下面用一個(gè)python程序來演示社交網(wǎng)絡(luò)的建模分析，以實(shí)際應(yīng)用作為結(jié)束吧。
假設(shè)有這樣兩個(gè)文本文件sigcomm_author.txt和sigcomm_network.txt，文件內(nèi)容如下：
sigcomm_network.txt:
1,2 (ID_1 與 ID_2 有合作發(fā)表論文)
3,4 (ID_3 與 ID_4 有合作發(fā)表論文)
4, 216 (ID_4 與ID_216 有合作發(fā)表論文)
…sigcomm_author.txt:
1: Amer El Abbadi (ID_1: name)
2: Thomas Lui (ID_2: name)
…
這是一個(gè)學(xué)術(shù)圈的社交網(wǎng)絡(luò)，描述了發(fā)表論文的作者之間的一些合作關(guān)系。它一個(gè)無向圖，也就是說[ID_1, ID_2] 等同于 [ID_2,ID_1]。通過編寫程序，我們可以挖掘如下信息：
NetworkX是一個(gè)用Python語言開發(fā)的圖論與復(fù)雜網(wǎng)絡(luò)建模工具，內(nèi)置了常用的圖與復(fù)雜網(wǎng)絡(luò)分析算法，包括我已經(jīng)介紹過的degreecentrality，eigenvectorcentrality等等。使用NetworkX可以方便的進(jìn)行復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)分析、仿真建模等工作。
一般Linux都默認(rèn)自帶Python運(yùn)行環(huán)境，Ubuntu下只需要執(zhí)行以下命令即可獲得NetworkX庫進(jìn)行程序開發(fā)。
sudo apt-get install python-setuptoolssudo easy_install networkx
Windows下則需要手動(dòng)安裝，具體可以參考這個(gè)安裝步驟。環(huán)境都搭建好了之后就可以對社交網(wǎng)絡(luò)之間的關(guān)系進(jìn)行分析了，查看這個(gè)入門指南。
回到上文提出的例子，在調(diào)用NetworkX提供的接口的基礎(chǔ)上，我們可以挖掘論文作者之間的關(guān)系，分析整個(gè)網(wǎng)絡(luò)的一些屬性。示例源代碼和測試數(shù)據(jù)下載。
-------------------------小結(jié)：優(yōu)化后的PAGERANK算法，可以利用測算網(wǎng)頁中相互連接的重要性來判斷網(wǎng)頁重要等級的模型，來延伸到計(jì)算社交網(wǎng)絡(luò)中意見領(lǐng)袖的尋找中，當(dāng)然，也可以通過這種方法推算內(nèi)容型站點(diǎn)，如輕博客中人們對內(nèi)容交互后的“內(nèi)容重要等級/內(nèi)容喜愛程度”，對于游戲而言，如果能夠發(fā)現(xiàn)游戲社交中的核心領(lǐng)袖，甚至能夠反推出交互過程中行為的重要程度，那么就可以幫助運(yùn)營做出及時(shí)決策改進(jìn)，這也是一個(gè)很好的方向。
