◆張 宇張 誠

（1.北京師范大學珠海分校 廣東 519087；2.中國移動國際有限公司 香港 999077）

基于無標度網(wǎng)絡結構的SNS識別方案

◆張 宇1張 誠2

（1.北京師范大學珠海分校 廣東 519087；2.中國移動國際有限公司 香港 999077）

本文根據(jù)社交網(wǎng)絡中存在大量無標度網(wǎng)絡結構的特性，在分析聚合算法和剖分算法的基礎上，提出基于無標度網(wǎng)絡結構的社區(qū)識別算法，并利用微博數(shù)據(jù)作為方案分析和闡述的實證數(shù)據(jù)。首先根據(jù)中心節(jié)點劃分網(wǎng)絡，把剩余點連接到歸屬中心節(jié)點上，最終將社交網(wǎng)絡劃分成若干聯(lián)系緊密的好友圈子。分析結果對移動互聯(lián)網(wǎng)新產(chǎn)品的開發(fā)、潛在客戶的挖掘和服務有參考意義。

SNS識別；無標度網(wǎng)絡；中心節(jié)點

0 引言

隨著4G網(wǎng)絡的全面覆蓋和智能手機全面普及，移動互聯(lián)網(wǎng)得到飛速的發(fā)展，社交形式的網(wǎng)站和手機應用不斷涌現(xiàn)，如國外的社交平臺Facebook、Wikipedia、Twitter等，國內(nèi)的微信、微博、QQ、陌陌等社交應用和社交網(wǎng)站用戶破億，其他照片分享、音樂分享、視頻分享、交友等社交應用更是層出不窮，網(wǎng)絡愈發(fā)呈現(xiàn)出社會性特征，即社交網(wǎng)絡（Social Networking Services，簡稱SNS）。社交網(wǎng)絡是一個虛擬社區(qū)，如何對這個社區(qū)進行有效識別并加以利用，對移動互聯(lián)網(wǎng)產(chǎn)品的開發(fā)、營銷與推廣以及潛在客戶的挖掘和服務有參考意義。

1 現(xiàn)有SNS識別方案分析

在社交網(wǎng)絡領域的社區(qū)識別中，最具代表性的算法是聚集算法和剖分算法。聚集算法是從某個點開始向外擴展，將耦合性大的點逐步加入到當前集合，直至不再有滿足條件的點，將這一部分的點劃分為同一個社區(qū)，然后再重新選取尚未劃分的點重復之前的步驟；剖分算法從整個網(wǎng)絡開始，尋找連接性最小的邊進行刪除，重復此步驟可將該網(wǎng)絡逐步細分，直至達到滿意的剖分效果，算法的關鍵在于如何對整個網(wǎng)絡中邊的關聯(lián)度進行適當?shù)暮饬浚浞椒ㄓ凶疃搪窂剿惴?、隨機漫步模型、電路模型等。

本文根據(jù)社交網(wǎng)絡中存在大量無標度網(wǎng)絡結構的特性，在聚合算法和剖分算法的基礎上提出基于無標度網(wǎng)絡結構的社區(qū)識別算法，該算法認為這些網(wǎng)絡結構的中心也是網(wǎng)絡中各個社區(qū)的中心，通過對這些具有“代表性”的中心節(jié)點的確定，可以簡單的將網(wǎng)絡分割成以這些節(jié)點為中心的社區(qū)，然后將其余的“鏈點”逐次聚合到各個社區(qū)中。

2 無標度網(wǎng)絡結構SNS識別方案闡述

根據(jù)中心節(jié)點來劃分網(wǎng)絡，再把剩余的點連接到其歸屬的中心節(jié)點上，最終將社交網(wǎng)絡劃分成若干聯(lián)系緊密的好友圈子。本文將利用微博數(shù)據(jù)作為方案分析的實證數(shù)據(jù)。

2.1 社交網(wǎng)絡數(shù)據(jù)

本文的研究對象是社交網(wǎng)絡中社區(qū)圈子劃分及用戶在圈中的地位和影響力，所以需要獲得用戶的好友連接數(shù)據(jù)，以此來建立連接的人際網(wǎng)絡圖。利用移動網(wǎng)絡信令分析中的微博好友連接作為測試數(shù)據(jù)。

2.2 中心節(jié)點的識別

中心節(jié)點是指處于整個網(wǎng)絡或社區(qū)中心位置的節(jié)點，本文定義中心節(jié)點為網(wǎng)絡中好友數(shù)量較多的節(jié)點。由于無標度網(wǎng)絡結構的中心的節(jié)點度數(shù)都比較大，根據(jù)我們對基礎數(shù)據(jù)統(tǒng)計，大約有5%的節(jié)點其度數(shù)明顯比其余節(jié)點多，因此實際計算時，選取度數(shù)最大前5%的節(jié)點作為中心節(jié)點。

2.3 中心節(jié)點的合并

NAM模型模擬的安陽站日徑流過程的精度比較結果詳見表1。NAM模型模擬的日徑流過程，在率定期內(nèi)，確定性系數(shù)大于0.9，等級屬于甲等的有2年;確定性系數(shù)大于等于0.7小于等于0.9，等級屬于乙等的有5年。在驗證期內(nèi)，確定性系數(shù)都在大于等于0.7小于等于0.9的范圍內(nèi)，等級都屬于乙等。徑流深相對誤差，在率定期內(nèi)，5年都合格，合格率為100%；驗證期內(nèi)，3年都合格，合格率為100%。

由于選取的多個中心節(jié)點可能屬于同一個社區(qū)，必須對中心節(jié)點間的關系進行判定，將屬于同一個社區(qū)的節(jié)點進行合并。

首先，定義兩個中心節(jié)點之間的相關度為：

其中N(u)、N(v)分別表示節(jié)點u、v的好友數(shù)量，num(t)指節(jié)點u和v共同好友節(jié)點的數(shù)量，即ruv衡量的是共同節(jié)點占總節(jié)點的比重。

將ruv大于某一給定閾值α的兩個中心節(jié)點認為是屬于同一個社區(qū)，即如果兩個中心節(jié)點的相關度大于α，則將其合并成同一個社區(qū)，具體合并算法如下：

（1）假設u1、u2……uk為選定的k個中心節(jié)點，依次計算每兩個中心節(jié)點之間的相關度ruv，選取其中的最大值。

（2）若相關度ruv<α，則合并過程完成，否則將這兩個節(jié)點視為同一個社區(qū)，并進行合并組成新節(jié)點。

（3）重復上邊步驟，直至沒有節(jié)點合并為止。

需要注意的問題是當兩個節(jié)點合并時，應該同時將他們的邊也合并在一起。根據(jù)α的大小還控制社區(qū)圈子規(guī)模，α值越高，則要求社區(qū)的藕合程度越高，社區(qū)數(shù)量較多，規(guī)模相對較小。

2.4 鏈點的聚合

中心成員完成合并后，形成若干以中心節(jié)點為成員的社區(qū)，下一步將非中心節(jié)點，即鏈點逐次聚合到現(xiàn)有的社區(qū)。聚合思路是計算該節(jié)點與各個社區(qū)的最短距離，將其歸并到距離最近的社區(qū)。在聚合過程中，由于存在多個社區(qū)，必須進行多源的最短路徑計算，每次聚合之后都重新計算的代價較大，所以我們的算法是聚合之后即時更新。具體計算過程如下：

（1）完成中心節(jié)點合并后，計算各社區(qū)到所有其他節(jié)點的路徑，選取最短路徑的社區(qū)。其中，屬于同一社區(qū)的節(jié)點視為單獨的點，即他們之間的距離為0。

（2）將節(jié)點u聚合到最近的社區(qū)T后，將所有非社區(qū)節(jié)點標記為“未訪問”狀態(tài)，更新節(jié)點u到社區(qū)T的距離為0，然后將節(jié)點u放到更新隊列中，狀態(tài)標記為“己訪問”。

（3）從更新隊列中選取最前面的節(jié)點v，標記狀態(tài)為“已訪問”，逐次訪問節(jié)點v的所有狀態(tài)為“未訪問”的鄰接節(jié)點，對最短距離進行更新，將更新過的節(jié)點放入更新隊列中。

重復步驟（3），直至更新隊列為空。

為提高算法中鏈點聚合的準確性，我們優(yōu)先考慮連接數(shù)多的節(jié)點。

經(jīng)過以上幾步計算后，社交網(wǎng)絡就被劃分成聯(lián)系緊密的好友圈子。

2.5 系統(tǒng)輸出

根據(jù)計算結果，為方便其他系統(tǒng)調(diào)用，系統(tǒng)輸出數(shù)據(jù)結構為：