基于社會(huì)媒體網(wǎng)絡(luò)的聚類方法的研究

黃藍(lán)會(huì)

基于社會(huì)媒體網(wǎng)絡(luò)的聚類方法的研究

黃藍(lán)會(huì)

社會(huì)媒體網(wǎng)絡(luò)屬于典型的復(fù)雜網(wǎng)絡(luò)，將復(fù)雜網(wǎng)絡(luò)中的聚類分析方法應(yīng)用到社會(huì)媒體網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)研究從而提出了將網(wǎng)絡(luò)中的節(jié)點(diǎn)轉(zhuǎn)化成代數(shù)空間上的數(shù)據(jù)對(duì)象，以及通過節(jié)點(diǎn)相似性系數(shù)來研究社團(tuán)結(jié)構(gòu)。最后通過仿真實(shí)驗(yàn)證明，利用節(jié)點(diǎn)相似性系數(shù)得到的社團(tuán)發(fā)現(xiàn)準(zhǔn)確率較高。

在線社會(huì)網(wǎng)絡(luò)；社會(huì)媒體網(wǎng)絡(luò)；聚類分析；數(shù)據(jù)挖掘

0　引言

互聯(lián)網(wǎng)技術(shù)的快速發(fā)展推動(dòng)了在線社會(huì)網(wǎng)絡(luò)的發(fā)展，博客、微博、社交網(wǎng)站等如雨后春筍般充斥著我們的生活。網(wǎng)絡(luò)將人類的社交層面拓展到了一個(gè)新的高度，最新統(tǒng)計(jì)表明Facebook用戶每天要觀看約500年時(shí)長(zhǎng)的YouTube視頻，Twitter上每分鐘要分享700個(gè)YouTube視頻，截至2012年12月底，我國(guó)使用社交網(wǎng)站的用戶規(guī)模為2.75億，較上年底提升了12.6%，占網(wǎng)民比例近5成［1］。

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

社會(huì)媒體網(wǎng)絡(luò)也屬于復(fù)雜網(wǎng)絡(luò)，除了存在“小世界效應(yīng)”和無標(biāo)度性之外，還存在網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)（network community structure），這是復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的主要特征［5］，這種結(jié)構(gòu)特征表明了復(fù)雜網(wǎng)絡(luò)中存在著社區(qū)結(jié)構(gòu)，即社區(qū)內(nèi)部節(jié)點(diǎn)之間關(guān)系相對(duì)緊密、社區(qū)之間節(jié)點(diǎn)關(guān)系相對(duì)稀疏［6］。社區(qū)結(jié)構(gòu)也稱社區(qū)聚團(tuán)或群組結(jié)構(gòu)，挖掘社區(qū)結(jié)構(gòu)的過程稱之為社區(qū)發(fā)現(xiàn)［7］［8］。

聚類分析（Clustering Analysis）是指將物理或抽象對(duì)象的集合分成由類似的對(duì)象組成的多個(gè)類（Class）或簇（Cluster）的分析過程，并使得同一個(gè)簇中的對(duì)象有極大的相似性，而不同簇間的對(duì)象則差別較大，評(píng)價(jià)相似性的標(biāo)準(zhǔn)主要是通過對(duì)象間距離來描述［9］［10］。

本文從聚類分析與社會(huì)媒體網(wǎng)絡(luò)的相似性著手，分析如何將社會(huì)媒體網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)轉(zhuǎn)變成復(fù)雜網(wǎng)絡(luò)的聚類分析。

1　相關(guān)研究

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

2　聚類方法設(shè)計(jì)

2.1聚類方法分析

聚類分析中存在如下特點(diǎn)：屬于同一類的對(duì)象之間相似性高，不同類之間的相似性低，而在社會(huì)媒體網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)特點(diǎn)是同一社團(tuán)的內(nèi)部節(jié)點(diǎn)連接緊密，不同社團(tuán)之間的節(jié)點(diǎn)連接松散［14］。從聚類分析和社團(tuán)結(jié)構(gòu)的定義上發(fā)現(xiàn)，它們兩者有很多類似的地方，如聚類分析的類與社會(huì)媒體網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)類似從定義上看，社會(huì)媒體網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)概念與聚類分析中的類概念非常相似，社團(tuán)之間的聯(lián)系與聚類分析中類的相似性研究規(guī)律相似。因此，本文將聚類分析中的方法應(yīng)用到社會(huì)媒體網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)研究中，必須解決如何將社會(huì)媒體網(wǎng)絡(luò)中的節(jié)點(diǎn)用數(shù)據(jù)結(jié)構(gòu)這種方式表示，以及節(jié)點(diǎn)間的聯(lián)系如何轉(zhuǎn)換成用聚類分析中的相似度來衡量。

2.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

Hu等人提出了在復(fù)雜網(wǎng)絡(luò)中利用信號(hào)傳播將網(wǎng)絡(luò)中的節(jié)點(diǎn)轉(zhuǎn)化成代數(shù)空間上的數(shù)據(jù)對(duì)象的方法［15］。這個(gè)方法將網(wǎng)絡(luò)中的節(jié)點(diǎn)視作能發(fā)送、接受和記錄信號(hào)。步驟如下：首先選擇任意一個(gè)節(jié)點(diǎn)作為起點(diǎn)，該節(jié)點(diǎn)的信號(hào)量設(shè)為非空，其他節(jié)點(diǎn)信號(hào)量設(shè)為0。然后將源節(jié)點(diǎn)的信號(hào)發(fā)送給鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)接收到信號(hào)后再將其發(fā)送給自己的鄰居節(jié)點(diǎn)，從而實(shí)現(xiàn)在網(wǎng)絡(luò)中的傳播。根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)只影響鄰居節(jié)點(diǎn)的特點(diǎn)，認(rèn)為節(jié)點(diǎn)所處社團(tuán)的其他鄰居節(jié)點(diǎn)的信號(hào)量會(huì)增加明顯，而社團(tuán)之外的節(jié)點(diǎn)信號(hào)量影響較小。

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

2.3相似度算法設(shè)計(jì)

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

通過2.2節(jié)關(guān)于數(shù)據(jù)結(jié)構(gòu)的定義，設(shè)置數(shù)據(jù)集D（d1，d2，…，dN），數(shù)據(jù)對(duì)象di（i=1，2，…，n）和n維向量空間中的對(duì)象一一對(duì)應(yīng)，兩個(gè)數(shù)據(jù)對(duì)象di，dj，的歐氏距離設(shè)置為：，對(duì)象間平均歐氏距離表示為：，其中m表示參加聚類的對(duì)象數(shù)目［17］。

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

3　實(shí)驗(yàn)結(jié)果與分析

本文以豆瓣網(wǎng)為實(shí)證網(wǎng)絡(luò)，使用自己編寫的網(wǎng)絡(luò)數(shù)據(jù)抓取及解析程序［18］，采用多次仿真取平均值的方法來獲得演化模型的網(wǎng)絡(luò)拓?fù)渲担删哂猩鐖F(tuán)關(guān)系R1和R2的社會(huì)媒體網(wǎng)絡(luò)仿真網(wǎng)絡(luò)，分別比較歐幾里德距離、余弦夾角，以及相似性系數(shù)這3個(gè)方法在進(jìn)行社團(tuán)劃分的準(zhǔn)確率。設(shè)置仿真網(wǎng)絡(luò)包含100個(gè)節(jié)點(diǎn)，統(tǒng)計(jì)節(jié)點(diǎn)與其他社團(tuán)間有連線，值用Cout表示。通過實(shí)驗(yàn)發(fā)現(xiàn)，利用相似性系數(shù)來衡量社會(huì)媒體網(wǎng)絡(luò)節(jié)點(diǎn)間的相似性，準(zhǔn)確率較高。如圖1所示：

圖1　社團(tuán)劃分準(zhǔn)確率比較

4　總結(jié)

社會(huì)媒體網(wǎng)絡(luò)屬于典型的復(fù)雜網(wǎng)絡(luò)，應(yīng)用復(fù)雜網(wǎng)絡(luò)理論來研究用戶在網(wǎng)絡(luò)中的關(guān)系，從而分析社會(huì)媒體網(wǎng)絡(luò)的聚類方法，劃分社團(tuán)結(jié)構(gòu)，為后續(xù)社團(tuán)個(gè)性化推薦奠定了研究基礎(chǔ)。

［1］ 王莉.在線社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)及演化［J］.計(jì)算機(jī)學(xué)報(bào)，2015，38（2）：220-236

［2］ 徐恪，張賽，陳昊，李海濤.在線社會(huì)網(wǎng)絡(luò)的測(cè)量與分析［J］.計(jì)算機(jī)學(xué)報(bào)，2014， 37（1）：165-188

［8］ 王景麗等.基于復(fù)雜網(wǎng)絡(luò)的在線社交網(wǎng)絡(luò)演化模型研究［J］.智能系統(tǒng)學(xué)報(bào)，2015，10（6）：20-25

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

［10］ 算機(jī)科學(xué)，2014，41（4）：215-229

［11］ 王竹. 一種新型社交網(wǎng)絡(luò)建模方法［J］.計(jì)算機(jī)與現(xiàn)代化，2015，12：50-55

［12］ 張?chǎng)? 復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)方法的研究［J］. 計(jì)算機(jī)工程與應(yīng)用，2015，51（24）：1-7

［13］ 喬少杰等.大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)并行發(fā)現(xiàn)算法［J］.計(jì)算機(jī)學(xué)報(bào)，2015，38：1-14

［14］ 李嘉慧等.多尺度的社團(tuán)結(jié)構(gòu)穩(wěn)定性分析［J］.計(jì)算機(jī)學(xué)報(bào)，2015，38（2）：301-311

［15］ Jain A K，Marty M N，F(xiàn)lynn P J.Data clustering：a review［J］.ACM computing surveys （CSUR），1999，3l（3）：264-323.

［16］ 秦李等. 復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要性綜合評(píng)價(jià)［J］.計(jì)算機(jī)科學(xué)，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］ 黃玲.在電子商務(wù)中應(yīng)用Web 數(shù)據(jù)挖掘的研究［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］ 賓晟. 基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型的多關(guān)系在線社會(huì)網(wǎng)絡(luò)研究［D］.2014，7：40-50

［25］ 黃藍(lán)會(huì).基于在線社會(huì)網(wǎng)絡(luò)的網(wǎng)絡(luò)爬蟲的研究和設(shè)計(jì)［J］.電子設(shè)計(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）

國(guó)家自然科學(xué)基金（No.61379030）；陜西省教育廳專項(xiàng)科研項(xiàng)目（15JK1028）

黃藍(lán)會(huì)（1980-），女，岳陽人，寶雞文理學(xué)院，計(jì)算機(jī)學(xué)院，講師，碩士，研究方向：數(shù)據(jù)挖掘，寶雞，721016