5. HITS算法

與PageRank算法類似，HITS也是在網絡建模和權重排名中比較經典的算法。

有的時候我們希望把高centrality值賦予那些鏈接了很多重要節點的節點，例如綜述性的學術論文引用了該研究領域內的大量重要論文，於是這篇綜述也被認為很有價值。因為即使這篇論文沒有為該科研領域做出什麼突破，但它總結了已有成果，告訴大家去哪裡找做出了突出貢獻的論文。

於是我們擁有兩種節點：authorities（權威型）的節點包含了具有貢獻的原創信息，hubs（樞紐型）節點總結了很多信息，指向了很多authorities節點。Kleinberg是康奈爾大學一位十分牛B的年輕教授（70後年輕有為啊！），他提出了hyperlink-induced topic search (HITS)算法來量化計算authority centrality和hubs centrality。

在HITS中對於某個節點i，xi用來表示authority centrality，yi用來表示hubs centrality。每個節點既有authority屬性又有hubs屬性。節點若有高xi值則該節點被很多其他hub節點關注，如論文被大量引用、微博有很多粉絲。節點若有高yi值則該節點指向了很多其他authority節點，例如一篇綜述論文，又例如hao123.com這樣的網址導航站點（理解百度為什麼要收購hao123了吧）。

用數學語言描述如下：

（15）

或者矩陣表達式

（16）

合併演化得到

（17）

這意味着authority centrality為AAT的特徵向量，而hubs centrality為ATA的特徵向量。有趣的是AAT和ATA擁有相同的特徵值λ，大家可以自行證明。

繼續演化，我們對式（17）左乘一個AT，得到 ，也就是說

（18）

我們知道了x，也就可以計算得到y。

6. 社交網絡建模工具（Python）

最近比較忙，如果沒有需求，這個系列可能就不會再繼續寫下去了。下面用一個python程序來演示社交網絡的建模分析，以實際應用作為結束吧。

假設有這樣兩個文本文件sigcomm_author.txt和sigcomm_network.txt，文件內容如下：

sigcomm_network.txt:

1,2 (ID_1 與 ID_2 有合作發表論文)
3,4 (ID_3 與 ID_4 有合作發表論文)
4, 216 (ID_4 與ID_216 有合作發表論文)
…

sigcomm_author.txt:

1: Amer El Abbadi (ID_1: name)
2: Thomas Lui (ID_2: name)
…

這是一個學術圈的社交網絡，描述了發表論文的作者之間的一些合作關係。它一個無向圖，也就是說[ID_1, ID_2] 等同於 [ID_2, ID_1]。通過編寫程序，我們可以挖掘如下信息：

  • n: 節點數量（有多少個作者）
  • m: 邊的數量（有多少個論文合作關係）
  • 網絡中連接部的大小（節點互相連接形成網絡連接部，另外還可能有孤立的一些節點（自娛自樂么，比如我，發表了2篇論文，無人引用。。。）。其實就是所謂的人際圈子，一個圈子裡的作者們互相引用論文，而跨圈子引用可能就比較少，例如計算機專業的學術圈子會很少引用化學學科的論文。）
  • clustering coefficient群聚係數
  • 網絡直徑（兩兩節點間會有一條最短路徑，在所有的節點對中，最長的最短路徑有多長。六度空間理論嘛，不過Facebook最新研究表明只有不到5度，也就是以不超過5個人的關係你可以聯繫到這個世界上的任何一個人。）
  • 節點度分布（大概應該是冪律分布，有高連接度高影響力的人少，大部分人都是平庸的。）
  • 最短路徑長度分布（看看每個人的六度空間係數都是怎麼分布的）
  • degree centrality
  • eigenvector centrality

NetworkX是一個用Python語言開發的圖論與複雜網絡建模工具，內置了常用的圖與複雜網絡分析算法，包括我已經介紹過的degree centrality，eigenvector centrality等等。使用NetworkX可以方便的進行複雜網絡數據分析、仿真建模等工作。

一般Linux都默認自帶Python運行環境，Ubuntu下只需要執行以下命令即可獲得NetworkX庫進行程序開發。

sudo apt-get install python-setuptools
sudo easy_install networkx

Windows下則需要手動安裝，具體可以參考這個安裝步驟。環境都搭建好了之後就可以對社交網絡之間的關係進行分析了，查看這個入門指南。

回到上文提出的例子，在調用NetworkX提供的接口的基礎上，我們可以挖掘論文作者之間的關係，分析整個網絡的一些屬性。示例源代碼和測試數據都在 Github 上供圍觀，你也可以直接 下載ZIP包。

更新：

7. EdgeRank 和 GraphRank

不知道大家有沒有注意到，人人網手機版客戶端上會顯示朋友們的所有新鮮事，而 PC 網頁版上則會過濾掉一些。這是為了控制信息泛濫，防止某些人刷屏，其實也是還一種排序策略。

今天和“史上最牛學長” yewen 討論社交網絡中的 Feeds（新鮮事）呈現，了解到 Facebook 的一套排序算法。有了我之前介紹的這些算法的基礎，再去嘗試思考這些問題，應該還是比較容易理解的。推薦閱讀《亂彈 EdgeRank》。