王亮亮　李小聰

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

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

DOIDOI：10.11907/rjdk.162613

中圖分類號：TP392

文獻標識碼：A文章編號文章編號：16727800（2017）005015203

0引言

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

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

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

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

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

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

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

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

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

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

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

2社交網(wǎng)絡(luò)用戶關(guān)系拓撲特性

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

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

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

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

3.1用戶信息有效劃分

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

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

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

Meank；

步驟3：計算數(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ù)測用戶之間的其它關(guān)系[13]。拓撲鏈接結(jié)構(gòu)分析方法是利用圖論的研究方法，首先要分離出具有關(guān)系或潛在關(guān)系節(jié)點的集合。微博的影響力和用戶的粉絲數(shù)目以及用戶在微博上發(fā)布消息被轉(zhuǎn)發(fā)和被提到的次數(shù)成正相關(guān)關(guān)系[14]。

對于微博中用戶關(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é)點的集合，E表示用戶之間的社會關(guān)系，W表示權(quán)重，路徑表示由社會關(guān)系構(gòu)成的鏈接關(guān)系[15]。

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

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

步驟2：隨機選擇n個對象作為聚類中心；

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

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

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

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

4結(jié)語

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

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

參考文獻參考文獻：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

責任編輯（責任編輯：孫娟）