基于在線社會網絡的演化模型的研究

黃藍會

基于在線社會網絡的演化模型的研究

黃藍會

針對在線社會網絡中用戶間的關系存在多種關系復合的情況，利用多子網復合復雜網絡的模型理論，將用戶關注關系網和用戶影評關系網進行復合，設計了一個基于在線社會網絡的網絡拓撲演化模型。該模型考慮了多關系間的相互影響。仿真結果證明，模型的網絡特征和同等實際網絡的網絡特征較為吻合。

在線社會網絡；網絡結構；網絡模型

0 引言

互聯網技術的快速發展推動了在線社會網絡的發展，博客、微博、社交網站等如雨后春筍般充斥了我們的生活。社會網絡屬于復雜網絡范疇，主要研究社會個體成員之間的關系，在這個網絡中用戶是節點,用戶之間的關系或交流是有向邊,這是互聯網應用拓撲的一般形式[1]。每個成員不僅可以瀏覽信息，更可以自己去創造、分享信息，成員之間的聯系可以是顯式的現實世界的好友關系，也可以是隱式的由于喜歡同一類物品，或者相同的興趣愛好形成的好友關系。在線社會網絡中信息的獲取、傳播快捷，參與人數多，并且聯系頻繁，參與人之間的關系經常變化，已有的在線社會演化模型與真實網絡的演化規律卻有如下3點不符合：（1）目前已有的在線社會網絡演化模型默認網絡規模是逐漸增長的，但現實世界中可能會因為用戶自身興趣改變、長時間不登陸等原因使得網絡規模不變甚至減小；（2）在線社會網絡模型當有新加入節點時，默認為優先考慮跟網絡中度較大的節點建立連接。但在現實網絡中，新注冊的用戶往往會選擇自己感興趣的用戶建立聯系；（3）目前的在線社會網絡演化模型用戶間的關系都是單一的，但是在線社會網絡與真實社會網絡一樣，網絡中的人與人之間往往存在多種關系。因此用傳統的網絡理論來研究在線社會網絡這種復雜網絡的網絡拓撲結構和演化規律已經行不通，本文從在線社會網絡的網絡演化模型入手，提出了多關系在線社會復合網絡演化模型，探索復雜網絡的形成機制。

1 相關研究

目前，在線社會網絡的研究主要是復雜網絡理論和數據挖掘技術。胡海波等對多種在線社會網絡的拓撲結構性質進行實證分析，指出在線社會網絡具有異配性[2]。Fu等對實名交友網站的一個連通的用戶社區進行實證分析，結果表明此連通子圖表現出小世界和無尺度特征，同時網絡具有同配性[3]。在線社會網絡的演化研究也是在線社會網絡研究的熱點之一。Homle等分析研究了瑞典著名的在線社交網絡Pusso-kram，闡述了網絡隨時間變化的特征[4]。Viswanath等研究了facebook用戶活動網絡的演化特性，發現盡管網絡規模會在初始階段迅速增大，但一些網絡拓撲特征值在2年后逐漸穩定[5]。Kumar等研究了雅虎在線社區Yahoo 1360，發現其網絡的密度隨時間先是迅速增加到達峰值，然后再緩慢較小，直到最后以穩定的速度增加[6]。Leskovec等系統的比較了Flickr、delicious等幾個著名的在線社會網絡，發現這些網絡都呈現出線性優先連接特征，即新加入的用戶與網絡中已經存在的老用戶連接的概率跟老用戶度數成正比[7]。

2 模型設計

2.1 模型特點分析

豆瓣網是目前國內用戶數量較大的書影音評價、推薦和交友網站。用戶之間朋友關系的形成有兩種途徑，一種是直接的，直接通過“關注”操作，關注某位豆瓣上感興趣的人，這樣以后該用戶的動態就可以直接在自己的“關注”主頁看到；另一種是隱含的，注冊用戶在豆瓣網可以給自己喜歡的書、電影、電視劇、音樂評分并寫評語，喜歡同一本書，同一部電影或者同一首音樂的用戶之間就形成了隱含的朋友關系。

隱含朋友關系實際上是從用戶的行為角度出發，分析其興趣和愛好，經過相似度計算，得到用戶之間的相似度。根據相似度是否超過設定的閾值時來判斷用戶之問是否存在隱含關系[8]。豆瓣網中大部分是不熟悉的人，用戶利用相同興趣作為媒介，幫助用戶通過喜愛的資源找到興趣相似的其他用戶，然后通過他們找到更多適合自己的資源。本文以“豆瓣網”這個典型的在線社會網絡為實證網絡，利用多子網復合復雜網絡模型理論，將用戶關注關系子網和用戶影評相似關系子網進行復合，提出了一種基于多子網復合復雜網絡模型的多關系在線社會復合網絡拓撲演化模型。

在豆瓣網中，用戶采用1-10分的數字代表自己對某部電影的喜好程度。喜好同一部電影的用戶因為興趣愛好可能組成討論組或好友群，這種用戶間喜好一致組成的朋友關系比較穩定，如果形成了社區結構，新用戶很容易受到同社區其他用戶影響，具有局域世界網絡特性[9]。

2.2 模型描述

本文將豆瓣網用戶關注的人所構成的網絡稱之為豆瓣網用戶關注關系網，將豆瓣網用戶對電影的評價所構成的網絡稱之為豆瓣網用戶影評關系網。由于將全部用戶作為整體來研究不現實，因此本文采用自己設計的網絡爬蟲系統[10]來收集數據，首先選擇一個起始用戶，然后通過該用戶獲取他所關注的用戶，以此類推，最終得到的樣本數據如表1第二、三列所示：

表1 豆瓣網網絡拓撲基本特征值

網絡最大連接度Kmax 10 405 4 143 3 190 3 267網絡次最大連接度Ksec 8 644 3 137 2 497 2 677集聚系數與度的相關指數-2 -2.3 -2 -2連接度冪律指數r -2.12 -2.25 -2.3 -2.3

利用多子網復合復雜網絡模型的子網加載運算，將豆瓣網用戶關注關系網和豆瓣網用戶影評相似關系網組成新的豆瓣網用戶多關系復合網G={V，E，R，F)[8]。其中，V是豆瓣網用戶的集合，E是豆瓣網用戶關系有關系的邊集合，兩個用戶間具有關注關系或影評相似關系都認為有一個邊；關系集合R=A×B，A表示用戶間具有關注關系：B表示用戶間具有影評相似關系；F將邊集E與集合R中元素一一對應。G的向量復合網∑=(G，S，M)，S是二維關系向量空間，?s∈S，s=(關注關系，影評關系)，其中關注關系和影評相似關系的取值分別為l或者0（1表示邊上具有關系，0表示沒有關系）。

采用多子網復合復雜網絡模型的子網退縮運算，獲得豆瓣網用戶多關系復合網∑，同時具有關系A和關系B的子網∑’=(G’,S’,M’)，其中每個節點都模擬一個豆瓣網節點，如果兩個節點有連接邊，代表這兩個用戶既是關注關系，又是影評相似關系。本文將該最大連通子圖組成的網絡作為多關系復合網絡進行實證分析，網絡拓撲基本特征量如表1第四列所示。

模型定義復合網G=(V，E，R，F)中假設結點存在

基于多關系的在線社會網絡演化模型的建模步驟如下：

（1）假設復合網G=(V，E，R，F)中存在N種關系，其中穩固關系為N1種，不穩固關系為N2種，則R=R1×…×Ri×…×RN=<(r1,…,ri,…,rN)|ri∈Ri，l≤i≤N)且dom(ri)={0,1}(1≤i≤N)，其中1表示存在關系Ri，0表示不存在。

（2）構造初始網絡：構造具有m0個節點，e0條邊的多關系網絡，確保節點沒有孤立點并且網絡中的邊沒有重連，同時?vh，vi∈{m0}，∈{e0)，存在F()=(r1,…，ri,…，rN)且dom(ri)=1(1≤i≤N)。

3 實驗結果與分析

本文以豆瓣網為實證網絡，使用自己編寫的網絡數據抓取及解析程序，采用多次仿真取平均值的方法來獲得演化模型的網絡拓撲值。

首先獲取豆瓣網用戶關系網的基本特征量，利用關注不需要對方確認的特點，采集到的關系網絡屬于有向的在線社會網絡，最終得到一個包含115 460個節點，2 235 741條邊的復雜網絡，集聚系數為0.095，網絡平均最短路徑為6.120 ，度小于3的節點所占比例是36.3%，平均連接度為38.728 ，網絡最大連接度有10 405，網絡次最大連接度有8 644，集聚系數與度的相關指數是-2，連接度冪律指數為-2.12。

然后獲取豆瓣網用戶影評關系網的基本特征量，用戶對一部電影評分采用10分制，當兩個用戶對6部以上的電影的評分基本一致時，認為這兩個用戶對電影的興趣具有很大的相似性。這種關系可以利用二分圖定義，將參與評分的用戶作為主體節點，事件本身為事件節點，將影評網向電影節點作投影，得到關于影評相似關系的用戶網絡。最終得到網絡節點個數為114 122個，網絡邊數1 651 883，集聚系數0.042 ，網絡平均最短路徑7.270 ，度小于3的節點所占比例37.3%，平均連接度28.949 ，網絡最大連接度4 143，網絡次最大連接度3 137，集聚系數與度的相關指數-2.3，連接度冪律指數-2.25。

本文將仿真結果與實際網絡的主要網絡拓撲值進行對比，如表1第四、五列所示。根據演化模型仿真得到的網絡呈現無標度特性，與實際網絡在網絡邊數、集聚系數、網絡平均最短路徑、度為1、2、3的節點所占比例以及平均連接度等方面都較為吻合。

通過大量仿真實驗，將本文設計的基于多子網復合網絡的演化模型設計成和真實豆瓣網同等規模后比較多個網絡拓撲值，發現結果都較為吻合，說明該演化模型較真實的刻畫了在線社會網絡的小世界和無標度特性。

4 總結

復雜網絡目前被廣泛應用在計算機科學、社會學、統計學、物理學等領域，在線社會網絡屬于典型的復雜網絡，應用復雜網絡理論來研究用戶在網絡中的關系及行為，從而分析在線社會網絡的拓撲結構，對于后續研究在線社會網絡的聚類方法和社團結構奠定了理論研究基礎。

[1] 徐恪,張賽,陳昊,李海濤.在線社會網絡的測量與分析[J].計算機學報,2014, 37(1):165-188.

[2] 胡海波,王科,徐玲等. 基于復雜網絡理論的在線社會網絡分析[J]. 復雜系統與復雜性科學,2008,12(2):1-14.

[3] Fu F,Chen X,Liu L. Social dilemmas in all online social network：the stnlcture and evolution of cooperation[J]. Physics Letters A. 2007,371(1):58-64.

[4] Holme P，Edling C R，Liljeros F.Structure and time evolution of all Internetdating community[J]. Social Networks,2004,17(2):155-174.

[5] Viswanath B，Mislove A，Cha M.On the evolution of user interaction in Facebook Proceedings ofthe 2nd ACMworkshop on online social networks[C].2009,37-42.

[6] Kumar R，Novak J，Tomkins A.Structure and evolution of online social networks. Proceedings of the 12th ACM SIGKDD international. conference onKnowledge discoveryand data mining[C]. 2006, 611-617.

[7] Leskovec J，Backstrom L，Kumar R.Microscopic evolution of social networks. Proceeding of the 14th ACM SIGKDD international conference onKnowledge discoveryand data mining[C]. 2008,462-470.

[8] 賓晟. 基于多子網復合復雜網絡模型的多關系在線社會網絡研究[D].山東:山東科技大學,2014.

[9] Li Xiang,Chen Guanrong. Alocal—worldevolvingnet workmodel[J]. Physica A,2003,328:274-286.

[10] 黃藍會.基于在線社會網絡的網絡爬蟲的研究和設計[J].電子設計工程,2014,22(6):106-108.

Research on Evolution Model Based on Online Social Evolution Network

Huang Lanhui
(Department of Computer Science, Baoji University of Arts and Science, Baoji 721016, China)

In the online social network, there are many kinds of relationships. By using the model of multi-subnet composited complex network model and re-integrating the relationship between the Douban user concer and Douban user film review, this paper designs a network topology evolution model based on online social network. The model takes the interactions of multiple relationships into account. By network characteristics contrast between a large number of simulation results and the actual network, with the same scale it shows that the model can simulate the basic characteristics of the actual multi-relationship online social network.

Online Social Network; Network Structure; Network Model

TP393

A

1007-757X(2016)09-0005-03

2016.02.12）

國家自然科學基金（No.61379030）；陜西省教育廳專項科研項目（15JK1028）

黃藍會（1980-），女，岳陽人，寶雞文理學院，計算機學院，講師，碩士，研究方向：物聯網應用，數據挖掘，寶雞 721016