社交網絡中個體價值分析

王志斌，黃　蔚

(華北計算技術研究所信息技術應用系統部，北京　100083)

社交網絡中個體價值分析

王志斌，黃蔚

(華北計算技術研究所信息技術應用系統部，北京100083)

社交網絡中個體價值分析，就是利用網絡爬蟲抓取社交網絡中數據，對數據過濾分析，抽象成圖結構，發現排名最高的節點（個體）。本文基于PageRank算法模型，應用“黃金分割線”方法和“二八定律”對其進行改進，并用在社交網絡中，定義以人為核心的個體價值，這樣PageRank模型就有了新的應用領域，同時也有了一個新的名字“PeopleRank”。本文將復雜的社交網絡抽象成一種圖結構，圖中節點代表用戶，圖中邊的鏈入鏈出代表了用戶之間的“粉絲”和“關注”關系。利用“PeopleRank”模型，構建矩陣，對矩陣進行迭代計算，最后得到一個收斂的結果，根據結果的大小確定在社交網絡中個體的重要性。

社交網絡；個體價值；PeopleRank；

本文著錄格式：王志斌，黃蔚. 社交網絡中個體價值分析[J]. 軟件，2016，37（8）：120-124

0　引言

隨著互聯網蓬勃發展，社交網絡改變了人們的生活方式。如今人們會更多的利用社交網絡，獲取信息和分享信息。通過社交網絡，我們每個個體，都成為了網絡的中心。我們的生活半徑，被無限放大，根據“六度理論”，我們通過6個朋友關系，就可以認識世界上任何一個人。如何從龐大的社交網絡中分析出個體的價值。

為了解決上述復雜的問題，本文把PageRank這個抽象的算法模型，應用到了社交網絡中，定義以人為核心的個體價值，同時在新的應用領域中也賦予了其新的名字PeopleRank。本文利用當下流行的大數據分析工具hadoop和spark針對實際例子，對其建模進行了設計與實現，具有較強的現實價值與意義。

1　相關概念介紹

1.1社交網絡介紹

社交網絡是一個系統：第一、系統中的主體是用戶（User），用戶可以公開或半公開個人信息；第二、用戶能創建和維護與其他用戶之間的連接（或朋友）關系及個人預分享的內容信息（如日志或照片等）；第三、用戶通過連接（或朋友）關系能瀏覽和評價朋友分享的信息。

社交網絡與傳統的Web網絡最大不同之處在于：傳統的Web網絡的主體是內容信息，依靠內容信息組織在一起，呈現給用戶；而社交網絡的主體是人，依靠人與人之間的朋友關系組織在一起。社交網絡必須具備三項基本功能，即允許用戶創建和維護朋友關系；上傳自己預分享的內容信息；瀏覽其他用戶分享的內容信息。但這三項功能在不同的社交網站上的體現形式可能存在較大差異，如Facebook 只允許用戶遍歷三層朋友關系，而人人網則沒有這個限制。

1.2社交網分類

社交網絡按照其功能屬性，大致可以把社交網絡分為如下類別：

交友網絡；這類社交網絡是現實社交圈子的映射，其朋友關系的真實性和關系維護的便捷性吸引了大量用戶的參與。這類網站國際上比較流行的有facebook、cyworld和myspace等；國內比較流行的有renren網和開心網。除此之外，面向商務人士的xing和linkedin、婚戀交友網也屬于此類網絡。

博客網絡；博客站點提供的最基本功能是博客的發布和用戶關注服務，用戶之間的關注關系就形成了社交網絡。博客網絡一般是有向網絡，即用戶A關注用戶B的博客，但用戶B未必關注用戶A的博客。較大的博客站點有Google blogger、Microsoft live spaces、twitter、新浪博客、騰訊Qzone、Live Journal、Twitter和Follow5等。

媒體分享網絡；這類網絡主要用于用戶發布、共享和檢索媒體資源，如視頻、圖片或書簽等。這些站點降低了信息發布的門檻，吸引大量用戶參與進來。此類站點除了提供資源發布和共享服務外，也提供交友服務。這些站點上的用戶形成的社交網絡一般也是有向網絡。

較大的站點有視頻分享網站愛奇藝和優酷土豆、圖片分享網站、網絡書簽站點CiteULike和delicious等。

即時通信網絡；即時通信系統是一種實時交流工具，系統中的每個用戶都有自己的聯系人（或好友）列表。根據用戶之間的好友關系可以構建即時通信系統中的社交網絡。有代表性的即時通信系統有MSN、QQ和微信等。

除了上述網絡以外，某些BBS（如天涯社區）和協同編輯站點（如百度百科）等也增加了關注或好友功能，這些站點上的用戶之間也可組成社交網絡。

上述站點所提供的服務之間有互補和重疊之處，如視頻分享網絡優酷上的用戶也可以指定自己的好友；Facebook和人人網上的用戶也可以發布自己的微博客，這使得我們很難在社交網絡的分類上給出嚴格的劃分。

1.3黃金分割

黃金分割線是一種古老的數學方法，黃金分割的創始人是古希臘的畢達哥拉斯，他在當時十分有限的科學條件下大膽斷言：一條線段的某一部分與另一部分之比，如果正好等于另一部分同整個線段的比即0.618，那么，這樣比例會給人一種美感。后來，這一神奇的比例關系被古希臘著名哲學家、美學家柏拉圖譽為“黃金分割律”。

1.4二八定律

二八定律又名80/20定律、帕列托法則（定律）也叫巴萊特定律、最省力的法則、不平衡原則等，被廣泛應用于社會學及企業管理學等。

1897年，意大利經濟學者帕累托偶然注意到19世紀英國人的財富和收益模式。在調查取樣中，發現大部分的財富流向了少數人手里。同時，他還從早期的資料中發現，在其他的國家，都發現有這種微妙關系一再出現，而且在數學上呈現出一種穩定的關系。于是，帕累托從大量具體的事實中發現：社會上20%的人占有80%的社會財富，即：財富在人口中的分配是不平衡的。

同時，人們還發現生活中存在許多不平衡的現象。因此，二八定律成了這種不平等關系的簡稱，不管結果是不是恰好為80%和20%（從統計學上來說，精確的80%和20%出現的概率很小）。習慣上，二八定律討論的是頂端的20%。而非底部的80%。人們所采用的二八定律，是一種量化的實證法，用以計量投入和產出之間可能存在的關系。[5]

2　社交網絡中個體價值分析

2.1算法模型

2.1.1PageRank算法介紹

PageRank是Google專有的算法，用于衡量特定網頁相對于搜索引擎索引中的其他網頁而言的重要程度。它由Larry Page和Sergey Brin在20世紀90年代后期發明。PageRank實現了將鏈接價值概念作為排名因素。

我們將Web做如下抽象：第一將每個網頁抽象成一個節點；第二如果一個頁面A有鏈接直接鏈向B，則存在一條有向邊從A到B（多個相同鏈接不重復計算邊）。因此，整個Web被抽象為一張有向圖。PageRank算法是基于這樣一種背景思想：被用戶訪問越多的網頁更可能質量越高，而用戶在瀏覽網頁時主要通過超鏈接進行頁面跳轉，因此我們需要通過分析超鏈接組成的拓撲結構來推算每個網頁被訪問頻率的高低。最簡單的，我們可以假設當一個用戶停留在某頁面時，跳轉到頁面上每個被鏈頁面的概率是相同的。

總而言之，一個頁面的“得票數”由所有鏈向它的頁面的重要性來決定，指向一個頁面的超鏈接相當于給該頁投一票。一個頁面的PageRank是由所有鏈向它的頁面（“鏈入頁面”）的等級指標經過遞歸算法得到的。一個有較多鏈入鏈接的頁面會有較高的等級，相反如果一個頁面沒有任何鏈入頁面，那么它沒有等級。也就是說從許多優質的網頁鏈接過來的網頁，必定還是優質網頁。

2.1.2PeopleRank算法介紹

基于PageRank的理論，我們以每個微博賬戶的“關注”為鏈出鏈接，“粉絲”為鏈入鏈接，我們把這種以人為核心的關系，叫PeopleRank。

1. PeopleRank之二八定律和黃金分割線

本文對數據進行抽象，并且構建圖，圖中有n個節點，假設起初圖中每個節點的權值都是1。統計圖中節點的“入度”，按照“入度”從大到小進行排名，遇到“入度”相同的按照“出度”從小到大進行排名，拿到排名最高的20%的節點。這20%的節點按照黃金分割比例進行切分，0.618這部分節點起始權值分別加(1-0.618)*0.8*1/n，(1-0.618)這部分節點的起始權值分別加0.618*0.8*1/n。

2. PeopleRank假設條件：

1）“明星”假設：本文假設“粉絲”數量多的前20%的人為“明星”人員。“明星”就應該產生傳遞大權值，在迭代計算開始時根據算法，它們會獲得較高的權值。

2）數量假設：如果一個用戶節點接收到的其他用戶“關注”的數量越多，那么這個用戶越重要。也就是說他的“粉絲”數量越多，這個用戶越重要。

3）質量假設：用戶P的“粉絲”質量不同，質量高的“粉絲”，關注用戶P，能給用戶P傳遞更多的權重。所以越是質量高的“用戶”關注用戶P，則用戶P越重要。例如：李開復“關注”了用戶P，或名人關注了用戶P和一個“僵尸”關注了用戶P相比，他們質量是不一樣的，李開復關注用戶P得到的PeopleRank的值越高。

3. 衡量PeopleRank的3個指標：

1）粉絲數，用戶P的“粉絲”數量越多，這個用戶越重要。

2）粉絲是否有較高PeopleRank值，PeopleRank值也就是一個重要性值。

3）粉絲關注了多少人，也就是關注用戶P的人，還關注了其他多少人。因為粉絲關注人的時候要把他的權重進行傳遞。一個粉絲只關注了一個人，他就將自身的權重百分之百傳給這個人，如果這個粉絲關注了n個人，那么他傳給每個人的權重就是1/n乘以權重值。

2.1.3PeopleRank算法原理

PeopleRank算法建立在隨機沖浪者模型上，其基本思想是：社交網絡中主體的重要性排序是由主體間的鏈接關系所決定的，算法是依靠主體間的鏈接結構來評價每個主體的等級和重要性，一個主體的PR值不僅考慮指向它的鏈接主體數，還有指向它的主體本身的重要性。

PeopleRank具有兩大特性：第一、PR值的傳遞性，主體A指向主體B時，A的PR值也部分傳遞給B。第二、重要性的傳遞性，一個重要主體比一個不重要主體傳遞的權重要多。

PeopleRank算法將社交網絡看成一個圖(Graph)。圖的節點是用戶，圖中的邊是用戶之間的鏈接。PeopleRank會計算出用戶的重要程度，并且給出排名。

算法計算公式：

上述公式里，p1,p2,p3...pn代表n個不同的用戶，M(i)是“關注”pi的所有用戶的集合，L(j)是pj用戶的粉絲數。d (0

2.2構造算法實例

2.2.1PeopleRank算法模型

以4個節點的數據為例。

1. 起始權值確認：1、2、3、4節點權值分別為1、1、1、1.1236

1）ID=1的節點鏈向2,3,4節點，所以一個用戶從ID=1的節點關注2,3,4的概率各為1/3。

2）ID=2的節點鏈向3,4節點，所以一個用戶從ID=2的節點關注3,4的概率各為1/2。

3）ID=3的節點鏈向4節點，所以一個用戶從ID=3的節點關注4的概率為1。

4）ID=4的節點鏈向2節點，所以一個用戶從ID=4的節點關注2的概率為1.1236。

圖1　4個節點圖

2. 構造鄰接表：

3. 構造鄰接矩陣(方陣):

列：源節點

行：目標節點

4. 轉換為概率矩陣(轉移矩陣)

5. 阻尼系數概率矩陣

增加阻尼系數后，ID=1的節點，就有值了PR(1)=(1-d)/n=(1-0.85)/4=0.0375，即無外鏈節點的最小值。

6. 實現矩陣的迭代計算

結果說明：

1）ID=1的節點，PR值是最小，因為沒有指向ID=1的節點。

2）ID=2的節點，PR值是0.3738930，權重很高，因為1和4都指向2，4權重較高，并且4只有一個鏈接指向到2，權重傳遞沒有損失。

3）ID=3的節點，PR值是0.2063759，雖有1和2的指向了3，但是1和2還指向的其他節點，權重被分散了，所以ID=3的節點PR并不高。

4）ID=4的節點，PR值是0.3822311，權重最高，因為被1,2,3都指向了。

2.2.2PeopleRank算法實例

1. 測試數據集：weibo.csv

數據集說明：25個用戶，66個關系，關注和粉絲的關系。第一列為用戶ID，第二列也是用戶ID。第一列用戶，關注了第二用戶。

2. 用R語言構建PeopleRank的算法原型

1）構建鄰接矩陣。

2）變換概率矩陣。

3）遞歸計算矩陣特征值。

4）標準化結果。

5）對結果排序輸出。

6）R語言算法模型。

用戶18有4個粉絲為別是6,7,10,19（粉絲數）。4個粉絲的PeopleRank排名，是3,5,8,20（粉絲是否有較高PeopleRank值）。粉絲的關注數量，是6,3,2,1（粉絲關注了多少人）。因此，通過對上面3個指標的綜合打分，用戶18是評分最高的用戶。

3　結束語

本文將PageRank模型應用于社交網絡，定義以人為核心的個體價值。本文以微博數據為例，基于PageRank模型給微博中每個用戶進行行評分。傳統的評分規則是，第一簡單求和：評分=關注數+粉絲數+微博數，第二加權求和：評分=a*關注數+b*粉絲數+c*微博數。和這兩種傳統方法相比，基于PageRank的模型評分結果，更符合我們的評分標準了。并且本文用到了大數據分析工具hadoop和spark，能滿足對海量數據的計算需求。

今后還有許多后續工作，將在以下方面做進一步的研究：

（1）目前PeopleRank模型只進行了起始節點權值確定。沒有對整個迭代過程進行考慮。還可以把黃金分割和二八定律用到迭代過程中，或者通過部分關系明確的數據（相當于一個圖中的子圖）得到一部分訓練集，然后一步一步加入所有數據，直到計算完圖中所有節點為止，但是考慮還不是很成熟，是接下來要研究的重點；

（3）本文沒有跟蹤用戶的行為，進行數據分析判斷用戶的傾向，這將導致對用戶的排名不完全符合實際情況。

[1] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters.

[2] S. Brin, L. Page, ‘The Anatomy of a Large-Scale Hypertextual Web Search Engine’.

[3] Wang S, Liu Z, Sun Q, Zou H, Yang F. Towards an accurate evaluation of quality of cloud service in service-oriented cloud computing. Journal of Intelligent Manufacturing, 2014, 25(2): 283-291.

[4] Jon M. Kleinberg, ‘Authoritative sources in a hyperlinked environment’, Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.

[5] (美)克里斯·安德森 譯者: 喬江濤. 長尾理論: 中信出版社, 2006年12月

[6] 張振華, 劉瑞芳. 微博社交網絡中面向機構的用戶挖掘[J].軟件, 2013, 34(1): 121-124.

[7] 山名早人, 近藤秀和, 「解說: 搜索引擎Google」(概要), 信息處理42卷8號(2001年8月), pp.775-780.

[8] 趙佳男. 基于社交網絡(SNS)的非正式學習模式的研究[J].軟件, 2014, 35(4): 175-177, 180.

[9] 劉耀庭: 社會關系網絡結構研究[D]. 浙江. 浙江大學, 2008.

[10] 張晨辰， 趙方. 社交網絡服務系統核心功能的設計與實現[J]. 軟件, 2013, 34(12): 92-98.

[11] 李冠辰. 一個基于hadoop的并行社交網絡挖掘系統[J]. 軟件, 2013, 34(12): 127-131.

[12] 劉華婷, 郭仁祥, 姜浩. 關聯規則挖掘Apriori算法的研究與改進[J]. 計算機應用與軟件, 2009(1): 146-149.

[13] 王珊, 王會舉, 覃雄派等. 架構大數據: 挑戰、現狀與展望[J]. 計算機學報, 2011, (10): 1741-1752.

[14] 汪小帆, 李翔, 陳關榮. 復雜網絡理論及其應用[M]. 北京:清華大學出版社, 2006.

Analysis of Individual Value in Social Networks

WANG Zhi-bin, HUANG Wei
(Application System Department, North China Institute of Computing Technology, Beijing, China)

The analysis of individual value in the social network is to use the web crawler to grab the data in the social network, to filter the data, to abstract the graph structure, and to find the highest ranking node (individual). This paper is based on PageRank algorithm, using the golden section line method” and the “Pareto Law” and is used in the social network. Based on the definition to the individual value of human as the core, this model can used in the new fields, and it is called “PeopleRank”. In this paper, the complex social network is abstracted into a graph structure, and the nodes in the graph represent the users, and the edges of the graph represent the relationship between the “fans” and“concerns”. Using the “PeopleRank” model, the matrix is constructed, and the matrix is calculated iteratively. Finally, a convergent result is obtained. According to the obtained results, the importance of the individual in the social network can be determined.

SNS (Social Networking Services); Individual values; PeopleRank

TP391

A

10.3969/j.issn.1003-6970.2016.08.026

王志斌(1989-），男，碩士研究生，大數據。

通訊聯系人： 黃蔚，研究員級高級工程師，大數據。