社交網(wǎng)絡中個體價值分析

王志斌，黃　蔚

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

社交網(wǎng)絡中個體價值分析

王志斌，黃蔚

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

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

社交網(wǎng)絡；個體價值；PeopleRank；

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

0　引言

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

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

1　相關概念介紹

1.1社交網(wǎng)絡介紹

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

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

1.2社交網(wǎng)分類

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

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

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

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

較大的站點有視頻分享網(wǎng)站愛奇藝和優(yōu)酷土豆、圖片分享網(wǎng)站、網(wǎng)絡書簽站點CiteULike和delicious等。

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

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

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

1.3黃金分割

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

1.4二八定律

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

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

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

2　社交網(wǎng)絡中個體價值分析

2.1算法模型

2.1.1PageRank算法介紹

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

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

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

2.1.2PeopleRank算法介紹

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

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

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

2. PeopleRank假設條件：

1）“明星”假設：本文假設“粉絲”數(shù)量多的前20%的人為“明星”人員?！懊餍恰本蛻摦a(chǎn)生傳遞大權值，在迭代計算開始時根據(jù)算法，它們會獲得較高的權值。

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

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

3. 衡量PeopleRank的3個指標：

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

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

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

2.1.3PeopleRank算法原理

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

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

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

算法計算公式：

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

2.2構造算法實例

2.2.1PeopleRank算法模型

以4個節(jié)點的數(shù)據(jù)為例。

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

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

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

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

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

圖1　4個節(jié)點圖

2. 構造鄰接表：

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

列：源節(jié)點

行：目標節(jié)點

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

5. 阻尼系數(shù)概率矩陣

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

6. 實現(xiàn)矩陣的迭代計算

結果說明：

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

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

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

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

2.2.2PeopleRank算法實例

1. 測試數(shù)據(jù)集：weibo.csv

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

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

1）構建鄰接矩陣。

2）變換概率矩陣。

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

4）標準化結果。

5）對結果排序輸出。

6）R語言算法模型。

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

3　結束語

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

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

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

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

[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] 張振華, 劉瑞芳. 微博社交網(wǎng)絡中面向機構的用戶挖掘[J].軟件, 2013, 34(1): 121-124.

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

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

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

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

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

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

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

[14] 汪小帆, 李翔, 陳關榮. 復雜網(wǎng)絡理論及其應用[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-），男，碩士研究生，大數(shù)據(jù)。

通訊聯(lián)系人： 黃蔚，研究員級高級工程師，大數(shù)據(jù)。