王亮亮　李小聰

摘要摘要：隨著互聯(lián)網(wǎng)的快速發(fā)展，社交網(wǎng)絡(luò)已逐漸成為人們?nèi)粘Ｉ钪胁豢苫蛉钡囊徊糠?。介紹OAuth協(xié)議的基本原理和實(shí)現(xiàn)流程，以新浪微博為例闡述用戶和用戶關(guān)系的數(shù)據(jù)抓取方法；討論一種能夠有效地表示社交網(wǎng)絡(luò)中用戶關(guān)系的數(shù)據(jù)結(jié)構(gòu)，介紹用戶關(guān)系識(shí)別的方法；對(duì)社交網(wǎng)絡(luò)中的用戶關(guān)系進(jìn)行分析總結(jié)，并展望在后期研究工作中，如何通過(guò)對(duì)用戶關(guān)系的分析更有效地發(fā)現(xiàn)意見(jiàn)領(lǐng)袖。

關(guān)鍵詞關(guān)鍵詞：社交網(wǎng)絡(luò)；OAuth協(xié)議；用戶關(guān)系；數(shù)據(jù)抓取；LP算法

DOIDOI：10.11907/rjdk.162613

中圖分類號(hào)：TP392

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）005015203

0引言

隨著互聯(lián)網(wǎng)的不斷普及，其對(duì)人們?nèi)粘Ｉ畹臐B透不斷深入，從QQ、微信，到易信、來(lái)往，再到新浪微博，越來(lái)越多的人加入到互聯(lián)網(wǎng)社交中，因此也吸引了越來(lái)越多的研宄人員從事社交網(wǎng)絡(luò)中的數(shù)據(jù)挖掘工作[1]。但是，一方面用戶數(shù)量不斷增加，數(shù)據(jù)挖掘量急劇增大；另一方面，用戶關(guān)系日益復(fù)雜，面對(duì)海量的用戶數(shù)據(jù)，如何才能更加高效地獲取到有用信息，數(shù)據(jù)挖掘技術(shù)扮演著不可或缺的角色。

在用戶具備了高密度和高粘度屬性、真實(shí)身份信息較為完備、用戶好友之間信任度較高等條件下，用戶信息具備了較高的商業(yè)價(jià)值可挖掘性[2]。這就使得社交網(wǎng)絡(luò)變得日益復(fù)雜，單純對(duì)數(shù)據(jù)的研究已經(jīng)不能滿足社會(huì)需求，如何更好地挖掘用戶和用戶關(guān)系正是本文所要研究的核心內(nèi)容。

1基于Web的社交網(wǎng)絡(luò)數(shù)據(jù)抓取

1.1OAuth協(xié)議原理與實(shí)現(xiàn)流程

Web2.0網(wǎng)絡(luò)具有動(dòng)態(tài)性更強(qiáng)、結(jié)構(gòu)更復(fù)雜的特點(diǎn)[1]。作為一項(xiàng)起源于網(wǎng)絡(luò)身份認(rèn)證系統(tǒng)OpenID的互聯(lián)網(wǎng)標(biāo)準(zhǔn)協(xié)議，OAuth協(xié)議中包括第三方應(yīng)用、用戶本身和服務(wù)提供方3個(gè)主要角色。基本原理是在第三方應(yīng)用與眾多的服務(wù)提供方建立關(guān)系的條件下，服務(wù)提供方通過(guò)第三方應(yīng)用提供的公鑰來(lái)驗(yàn)證第三方應(yīng)用的身份，而服務(wù)提供方把用戶導(dǎo)向到第三方應(yīng)用的登錄窗口[2]，原理如圖1所示。

OAuth協(xié)議的實(shí)現(xiàn)流程主要分為3個(gè)階段。首先，用戶要通過(guò)注冊(cè)來(lái)獲得客戶端憑證；然后，服務(wù)提供方提供一致的授權(quán)服務(wù)地址和令牌服務(wù)地址進(jìn)行服務(wù)，而這一階段又包含申請(qǐng)臨時(shí)令牌、用戶授權(quán)和申請(qǐng)?jiān)L問(wèn)令牌請(qǐng)求3個(gè)過(guò)程；在最后的資源調(diào)用階段中，第三方應(yīng)用向服務(wù)提供方發(fā)送已經(jīng)明確說(shuō)明所需要的訪問(wèn)令牌和參數(shù)的資源調(diào)用申請(qǐng)[2]。其詳細(xì)實(shí)現(xiàn)流程如圖2所示。

1.2微博數(shù)據(jù)抓取

社交網(wǎng)絡(luò)具有開(kāi)放、自由、高容納性、互動(dòng)性等特點(diǎn)，人們可以自由發(fā)言、評(píng)論、或者表達(dá)自己的感受[3]。針對(duì)不同的用戶數(shù)據(jù)信息采用不同的網(wǎng)絡(luò)爬蟲(chóng)對(duì)數(shù)據(jù)進(jìn)行抓取，通過(guò)新浪微博API，需要爬取的數(shù)據(jù)信息包括用戶信息、用戶關(guān)系信息、用戶標(biāo)簽信息、微博評(píng)價(jià)等[4]。

只有獲取了用戶的相關(guān)信息，了解了用戶的愛(ài)好之后，才能夠更好地“推薦”以滿足用戶所需。這也是本研究的重點(diǎn)，在此著重探討用戶標(biāo)簽的獲取，用戶標(biāo)簽獲取流程如圖3所示[5]。

獲取用戶標(biāo)簽的方法中所定義的數(shù)據(jù)結(jié)構(gòu)如下（其中用戶標(biāo)簽的信息都存放在Label數(shù)組中）：

所需定義的用戶信息如表1所示，在這個(gè)表中存儲(chǔ)的是需要查詢的用戶id，以及該用戶的粉絲和好友的id。

2社交網(wǎng)絡(luò)用戶關(guān)系拓?fù)涮匦?/p>

通過(guò)微博、微信、QQ，人們總是把身邊發(fā)生的好玩的、有意義的故事分享到空間供他人分享、評(píng)論。人與人之間的關(guān)系變得日益復(fù)雜，有好友或親情關(guān)系、關(guān)注與被關(guān)注關(guān)系、共同評(píng)論關(guān)系、共同愛(ài)好關(guān)系等[6]。以新浪微博為例，其關(guān)系網(wǎng)絡(luò)是由用戶間的關(guān)注與被關(guān)注關(guān)系而形成（見(jiàn)圖4），而且這是一種屬于復(fù)雜網(wǎng)絡(luò)的有向無(wú)權(quán)關(guān)系網(wǎng)絡(luò)[7]。這種關(guān)系網(wǎng)絡(luò)具有拓?fù)涮匦?，因此需要用網(wǎng)絡(luò)度及度分布、聚類系數(shù)以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等幾種要素反映這一特性[8]。

結(jié)合節(jié)點(diǎn)度的定義與微博用戶間的特殊關(guān)系，將關(guān)系網(wǎng)絡(luò)中節(jié)點(diǎn)的入度設(shè)為該用戶的粉絲數(shù)，出度設(shè)為該用戶關(guān)注的用戶量。入度的計(jì)算方法如圖5所示，出度的計(jì)算方法如圖6所示。

通過(guò)對(duì)用戶粉絲數(shù)和用戶關(guān)注數(shù)進(jìn)行計(jì)算就可以得到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的入度kin與Pin（k）、出度kout與Pout（k）。為了更加形象、具體地表示這些特征屬性的分布情況，通常選用kin（或kout）作為x軸，Pin（k）（或Pout（k））作為y軸，構(gòu)造擬合曲線[9]。

3社交網(wǎng)絡(luò)中用戶關(guān)系識(shí)別

3.1用戶信息有效劃分

LP （Linear Programming）算法是單類分類器研究的主要方法，它具有稀疏性、大間隔、核誘導(dǎo)和全局最優(yōu)等特點(diǎn)[10]。LP問(wèn)題的求解方法有3種類型：主元法、非線性函數(shù)極值法和收縮區(qū)域法，它通過(guò)計(jì)算最小化樣本的輸出結(jié)果之和來(lái)尋找超平面，從而將目標(biāo)數(shù)據(jù)和非目標(biāo)數(shù)據(jù)分開(kāi)。在此利用LP算法的改進(jìn)算法DLP將社交網(wǎng)絡(luò)中用戶的數(shù)據(jù)信息進(jìn)行有效劃分，從而為后期微博用戶信息的抓取做好前期準(zhǔn)備[11]。其操作步驟如下[12]：

步驟1：獲得數(shù)據(jù)樣本X= {x1，x2，…，xn}；

步驟2：計(jì)算xi到其k鄰域xki的距離d（xi，xki）；計(jì)算全部樣本點(diǎn)到k鄰域的平均值

Meank；

步驟3：計(jì)算數(shù)據(jù)密度公式如式（1）（Z為權(quán)重系數(shù)，調(diào)節(jié)pi的大?。?/p>

pi=zM eank[]d（xi-xki），pi>0（1）

步驟4：得到數(shù)據(jù)的判定函數(shù)如式（2）（K為核矩陣，描述數(shù)據(jù)之間的相似性）：

f（z）=∑k[]i=1TiK（z，xi）+b（2）

步驟5：重復(fù)步驟2～4，直到把異常信息全部刪除掉。

3.2微博用戶數(shù)據(jù)信息抓取

社交網(wǎng)絡(luò)用戶關(guān)系分析就是根據(jù)已有的部分社交網(wǎng)絡(luò)結(jié)構(gòu)、用戶屬性和行為等，分析和預(yù)測(cè)用戶之間的其它關(guān)系[13]。拓?fù)滏溄咏Y(jié)構(gòu)分析方法是利用圖論的研究方法，首先要分離出具有關(guān)系或潛在關(guān)系節(jié)點(diǎn)的集合。微博的影響力和用戶的粉絲數(shù)目以及用戶在微博上發(fā)布消息被轉(zhuǎn)發(fā)和被提到的次數(shù)成正相關(guān)關(guān)系[14]。

對(duì)于微博中用戶關(guān)系的研究，通常采用有向加權(quán)圖的結(jié)構(gòu)形式表示，用有向加權(quán)圖G=（V，E，W）表示社交網(wǎng)絡(luò)的結(jié)構(gòu)形式，其中 G 表示社交網(wǎng)絡(luò)，V表示節(jié)點(diǎn)的集合，E表示用戶之間的社會(huì)關(guān)系，W表示權(quán)重，路徑表示由社會(huì)關(guān)系構(gòu)成的鏈接關(guān)系[15]。

識(shí)別社交網(wǎng)絡(luò)中用戶關(guān)系的方法多種多樣，在此采用k均值算法實(shí)現(xiàn)對(duì)用戶的分類，其實(shí)現(xiàn)步驟如下[16]：

步驟1：輸入對(duì)象矩陣X和聚類數(shù)N；

步驟2：隨機(jī)選擇n個(gè)對(duì)象作為聚類中心；

步驟3：利用k均值算法計(jì)算相似度。本文以微博用戶“奮斗去北京”關(guān)注的其它用戶信息，生成關(guān)系圖如圖7所示。其中計(jì)算對(duì)象相似度的公式如式（3）：

dxkN=minm[]k=1Xk-Nk1[]2（3）

步驟4：用各個(gè)類的平均向量更新聚類中心，再將每一個(gè)對(duì)象分別與這n個(gè)聚集中心的距離作比較，把相近的分為一類；

步驟5：不斷重復(fù)步驟3～4，直到滿足終止條件為止。

4結(jié)語(yǔ)

作為一種開(kāi)放、自由、容納性高、互動(dòng)性強(qiáng)的社會(huì)化網(wǎng)絡(luò)，面對(duì)大量的互聯(lián)網(wǎng)用戶，如何高效地識(shí)別用戶關(guān)系、抓取有效的數(shù)據(jù)尤為重要。本文以新浪微博為例，介紹了新浪微博用戶關(guān)系的形成方式以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)要素的概念，并以流程圖的形式反映了節(jié)點(diǎn)度的定義與微博用戶間的特殊關(guān)系。

面對(duì)大量數(shù)據(jù)，采用不同的網(wǎng)絡(luò)爬蟲(chóng)對(duì)數(shù)據(jù)進(jìn)行抓取，本文總結(jié)了用有向加權(quán)圖G=（V，E，W）來(lái)表示社交網(wǎng)絡(luò)的結(jié)構(gòu)形式，先使用PL算法去掉用戶的異常數(shù)據(jù)信息，做好數(shù)據(jù)抓取的前期準(zhǔn)備工作，再介紹k均值算法的具體操作流程，以一個(gè)微博用戶實(shí)例對(duì)象來(lái)進(jìn)行數(shù)據(jù)抓取，有效地提取了用戶信息。下一步工作將是通過(guò)對(duì)用戶及用戶關(guān)系的進(jìn)一步研究，探索出一種能夠十分有效地發(fā)現(xiàn)意見(jiàn)領(lǐng)袖的方法，從而通過(guò)引導(dǎo)意見(jiàn)領(lǐng)袖的觀點(diǎn)，有效控制網(wǎng)絡(luò)輿情并幫助廠商進(jìn)行商品推廣[17]。

參考文獻(xiàn)參考文獻(xiàn)：

[1]陳曉美.網(wǎng)絡(luò)評(píng)論觀點(diǎn)知識(shí)發(fā)現(xiàn)研究[D].長(zhǎng)春：吉林大學(xué)，2014.

[2]盧慧鋒.社會(huì)化網(wǎng)絡(luò)服務(wù)中OAuth2_0的應(yīng)用研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2014，34（S1）：5054.

[3]王連喜，蔣盛益，龐觀松，等.微博用戶關(guān)系挖掘研究綜述[J].情報(bào)雜志，2012，31（12）：9294.

[4]馮典.面向微博的數(shù)據(jù)采集和分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京：北京郵電大學(xué)，2013.

[5]徐志明，李棟，劉挺，等.微博用戶的相似性度量及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（1）：208210.

[6]王川.社交網(wǎng)絡(luò)數(shù)據(jù)抓取和社團(tuán)發(fā)現(xiàn)硏究[D].上海：復(fù)旦大學(xué)，2013.

[7]覃夢(mèng)河，邱遠(yuǎn)棋，晉佑順.基于內(nèi)容分析的微博用戶關(guān)系推薦機(jī)制研究[J].圖書(shū)館論壇，2013，33（4）：104106.

[8]劉曉曼.社交網(wǎng)絡(luò)數(shù)據(jù)獲取與結(jié)構(gòu)分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].合肥：安徽大學(xué)，2014.

[9]吳信東，李毅，李磊.在線社交網(wǎng)絡(luò)影響力分析[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（4）：736738.

[10]劉道建.SLI的條件冗余性及LP問(wèn)題的算法研究[D].成都：西南交通大學(xué)，2013.

[11]劉慧玲.頻繁模式挖掘算法LPSMiner及其并行模式研究[D].蘭州：蘭州大學(xué)，2009.

[12]馮愛(ài)民，陳斌.基于局部密度的單類分類器LP改進(jìn)算法[J].南京航空航天大學(xué)學(xué)報(bào)，2006，38（6）：728730.

[13]廉捷.基于用戶特征的社交網(wǎng)絡(luò)數(shù)據(jù)挖掘研究[D].北京：北京交通大學(xué)，2013.

[14]王玙，高琳.基于社交圈的在線社交網(wǎng)絡(luò)朋友推薦算法[J].計(jì)算機(jī)學(xué)報(bào)，37（4）：804805，2014.

[15]李德民.社會(huì)網(wǎng)絡(luò)用戶關(guān)系分析與預(yù)測(cè)[D].濟(jì)南：山東大學(xué)，2015.

[16]張國(guó)安，鐘紹輝.基于k均值聚類的微博用戶分類的研究[J].電腦知識(shí)與技術(shù)，2012，8（26）：62736275.

[17]尹衍騰，李學(xué)明，蔡孟松.基于用戶關(guān)系與屬性的微博意見(jiàn)領(lǐng)袖挖掘方法[J].計(jì)算機(jī)方法，2013，39（4）：185187.

責(zé)任編輯（責(zé)任編輯：孫娟）