基于社會媒體網絡的聚類方法的研究

黃藍會

基于社會媒體網絡的聚類方法的研究

黃藍會

社會媒體網絡屬于典型的復雜網絡，將復雜網絡中的聚類分析方法應用到社會媒體網絡中的社團結構研究從而提出了將網絡中的節點轉化成代數空間上的數據對象，以及通過節點相似性系數來研究社團結構。最后通過仿真實驗證明，利用節點相似性系數得到的社團發現準確率較高。

在線社會網絡；社會媒體網絡；聚類分析；數據挖掘

0　引言

互聯網技術的快速發展推動了在線社會網絡的發展，博客、微博、社交網站等如雨后春筍般充斥著我們的生活。網絡將人類的社交層面拓展到了一個新的高度，最新統計表明Facebook用戶每天要觀看約500年時長的YouTube視頻，Twitter上每分鐘要分享700個YouTube視頻，截至2012年12月底，我國使用社交網站的用戶規模為2.75億，較上年底提升了12.6%，占網民比例近5成［1］。

在線社會網絡目前成為了互聯網一項最具影響的應用，根據應用類型不同，在線社會網絡可以分為社交網絡和社會媒體網絡（Social Media Network，簡稱SMN）兩大類［2］［3］。社交網絡一般是由現實生活中熟悉的親友組成的，具有雙向聯系，屬于強關系結構，典型的如QQ、人人網等，有顯示的朋友圈；社會媒體網絡典型的應用如新浪微博、豆瓣網等，他們之間大部分關系由“關注”形成，具有單向聯系，屬于弱關系結構。本文主要以豆瓣網為例，研究社會媒體網絡［4］。

社會媒體網絡也屬于復雜網絡，除了存在“小世界效應”和無標度性之外，還存在網絡社區結構（network community structure），這是復雜網絡拓撲結構的主要特征［5］，這種結構特征表明了復雜網絡中存在著社區結構，即社區內部節點之間關系相對緊密、社區之間節點關系相對稀疏［6］。社區結構也稱社區聚團或群組結構，挖掘社區結構的過程稱之為社區發現［7］［8］。

聚類分析（Clustering Analysis）是指將物理或抽象對象的集合分成由類似的對象組成的多個類（Class）或簇（Cluster）的分析過程，并使得同一個簇中的對象有極大的相似性，而不同簇間的對象則差別較大，評價相似性的標準主要是通過對象間距離來描述［9］［10］。

本文從聚類分析與社會媒體網絡的相似性著手，分析如何將社會媒體網絡的社團發現轉變成復雜網絡的聚類分析。

1　相關研究

聚類分析目前是數據挖掘領域的一個研究方向，聚類算法主要有如下幾個大類：（1）基于劃分的方法，主要通過將數據集劃分成多個類，每個類至少有一個對象，典型算法有k.medoids算法［11］；（2）基于層次的方法，主要是針對給定的數據集進行層次分解，根據層次分解的過程又分為凝聚算法和分裂算法，典型算法有URE［12］；（3）基于密度的方法，主要用來過濾孤立節點，發現任意形狀的類，典型算法有OPTICS［13］。

2　聚類方法設計

2.1聚類方法分析

聚類分析中存在如下特點：屬于同一類的對象之間相似性高，不同類之間的相似性低，而在社會媒體網絡中的社團結構特點是同一社團的內部節點連接緊密，不同社團之間的節點連接松散［14］。從聚類分析和社團結構的定義上發現，它們兩者有很多類似的地方，如聚類分析的類與社會媒體網絡的社團結構類似從定義上看，社會媒體網絡中的社團結構概念與聚類分析中的類概念非常相似，社團之間的聯系與聚類分析中類的相似性研究規律相似。因此，本文將聚類分析中的方法應用到社會媒體網絡中的社團結構研究中，必須解決如何將社會媒體網絡中的節點用數據結構這種方式表示，以及節點間的聯系如何轉換成用聚類分析中的相似度來衡量。

2.2數據結構設計

Hu等人提出了在復雜網絡中利用信號傳播將網絡中的節點轉化成代數空間上的數據對象的方法［15］。這個方法將網絡中的節點視作能發送、接受和記錄信號。步驟如下：首先選擇任意一個節點作為起點，該節點的信號量設為非空，其他節點信號量設為0。然后將源節點的信號發送給鄰居節點，鄰居節點接收到信號后再將其發送給自己的鄰居節點，從而實現在網絡中的傳播。根據網絡節點只影響鄰居節點的特點，認為節點所處社團的其他鄰居節點的信號量會增加明顯，而社團之外的節點信號量影響較小。

根據Hu的思想，本文設置這樣的假設，將網絡中的每個節點看作一個信號節點，具有n維向量，n個節點就有n個n維向量，將這n個向量標準化后投射到代數空間后，認為每個向量即為代數空間中的一個數據。節點間信號的傳播過程用公式V=（I+A）T來表示，其中I表示單位矩陣，A表示鄰接矩陣，T是信號傳遞的次數，矩陣V的i列Vi=（vil，vi2，…，vin）表示網絡的第i個節點作為信號源節點經過T次傳播后對網絡的影響。對Vi進行標準化后得到Ui=（uil，ui2，…，uin），其中，，這樣就可以把這些代數空間中的U1，U2，…，Un看作是社會媒體網絡中的節點了。

2.3相似度算法設計

聚類分析中常用的相似性方法有歐幾里德距離、余弦夾角，以及相似性系數方法。本文采用Zhou等提出的相異性指標［16］來衡量社會媒體網絡中節點間的相似性。本文根據這個理論，定義加權社會媒體網絡G=（V，E，W），其中V是非空節點集，E表示邊集，W表示邊上的權重值集，（vi，vj）表示節點vi和vj之間的連邊，邊（vi，vj）上的權重值用wij表示。衡量節點vi和vj網絡結構相似度的公式設置為：

通過2.2節關于數據結構的定義，設置數據集D（d1，d2，…，dN），數據對象di（i=1，2，…，n）和n維向量空間中的對象一一對應，兩個數據對象di，dj，的歐氏距離設置為：，對象間平均歐氏距離表示為：，其中m表示參加聚類的對象數目［17］。

根據上述的定義，本文將相似性系數應用到n維向量空間中的對象，如果節點i和節點j在復合網中有連邊，用Sim(di,dj)表示它們對應的多維向量對象之間的歐氏距離，節點i和節點j的相似性系數定義為：。如果節點i和節點j屬于同一社團時，那么節點i和節點j與節點k（節點k可以屬于同一個社區，也可以是不同社區）的歐式距離Sim（di，dk）和Sim（dj，dk）應該近似相等，由此計算出的節點i和節點j與網絡中其余n-2個節點之間歐式距離的差值的平均值就定義為這兩個節點的相似性系數。

3　實驗結果與分析

本文以豆瓣網為實證網絡，使用自己編寫的網絡數據抓取及解析程序［18］，采用多次仿真取平均值的方法來獲得演化模型的網絡拓撲值，生成具有社團關系R1和R2的社會媒體網絡仿真網絡，分別比較歐幾里德距離、余弦夾角，以及相似性系數這3個方法在進行社團劃分的準確率。設置仿真網絡包含100個節點，統計節點與其他社團間有連線，值用Cout表示。通過實驗發現，利用相似性系數來衡量社會媒體網絡節點間的相似性，準確率較高。如圖1所示：

圖1　社團劃分準確率比較

4　總結

社會媒體網絡屬于典型的復雜網絡，應用復雜網絡理論來研究用戶在網絡中的關系，從而分析社會媒體網絡的聚類方法，劃分社團結構，為后續社團個性化推薦奠定了研究基礎。

［1］ 王莉.在線社會網絡的動態社區發現及演化［J］.計算機學報，2015，38（2）：220-236

［2］ 徐恪，張賽，陳昊，李海濤.在線社會網絡的測量與分析［J］.計算機學報，2014， 37（1）：165-188

［8］ 王景麗等.基于復雜網絡的在線社交網絡演化模型研究［J］.智能系統學報，2015，10（6）：20-25

［9］ 張星等.基于交互相似度的細粒度社群挖掘方法［J］. 計

［10］ 算機科學，2014，41（4）：215-229

［11］ 王竹. 一種新型社交網絡建模方法［J］.計算機與現代化，2015，12：50-55

［12］ 張鑫. 復雜網絡中社區發現方法的研究［J］. 計算機工程與應用，2015，51（24）：1-7

［13］ 喬少杰等.大規模復雜網絡社區并行發現算法［J］.計算機學報，2015，38：1-14

［14］ 李嘉慧等.多尺度的社團結構穩定性分析［J］.計算機學報，2015，38（2）：301-311

［15］ Jain A K，Marty M N，Flynn P J.Data clustering：a review［J］.ACM computing surveys （CSUR），1999，3l（3）：264-323.

［16］ 秦李等. 復雜網絡的節點重要性綜合評價［J］.計算機科學，2015，42（2）：60-64

［17］ Kaufman L， Rousseau P J. Finding groups in data： an introduction to cluster analysis ［M］.Wiley.eom，2009.

［18］ Guha S， Rastogi R， Shim K. CURE： an efficient clustering algorithmforlarge databases［C］.ACMSIGMOD Record.

［19］ ACM，1998，27（2）：73-84.

［20］ Ankerst M， Breunig M M， Kriegel H P. OPTICS： ordering points toidentifythe clustering structur. ACM SIGMOD Recorde［J］，1999，28（2）：49—60

［21］ 黃玲.在電子商務中應用Web 數據挖掘的研究［D］.2014，1：3-5

［22］ Yanqing Hu， Menghui Li， Peng Zhang. Community detection bysignalingoncomplex networks ［J］. Phys. Rev.E，2008， 78：0161

［23］ Zhou H. Distance， dissimilarity index， and network community structure［J］. Physical review e，2003，67（6）：61-91

［24］ 賓晟. 基于多子網復合復雜網絡模型的多關系在線社會網絡研究［D］.2014，7：40-50

［25］ 黃藍會.基于在線社會網絡的網絡爬蟲的研究和設計［J］.電子設計工程，2014，22（6）：106-108

Research on Clustering Method Based on Social Media Network

Huang Lanhui
（Department of Computer Science， Baoji University of Arts and Science， Baoji 721016， China）

Social media network is a typical complex network. In this paper， the method of clustering analysis in complex networks is applied to the study of community structure in social media network. we put forward the data objects in the network， which are transformed into algebraic space， and using the similarity coefficient of nodes to study the structure of the community.Finally， the simulation results show that the accuracy of the association is found by using the node similarity coefficient.

Online Social Network； Social Media Network； Clustering Analysis； Data Mining

TP393

A

1007-757X（2016）06-0001-02

［26］ （2016.02.12）

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

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