◆張 宇張 誠

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

基于無標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)的SNS識別方案

◆張 宇1張 誠2

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

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

SNS識別；無標(biāo)度網(wǎng)絡(luò)；中心節(jié)點(diǎn)

0 引言

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

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

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

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

2 無標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)SNS識別方案闡述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 鏈點(diǎn)的聚合

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

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

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

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

重復(fù)步驟（3），直至更新隊(duì)列為空。

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

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

2.5 系統(tǒng)輸出

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