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

◆張 宇張 誠(chéng)

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

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

◆張 宇1張 誠(chéng)2

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

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

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

0 引言

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

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

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

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

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

根據(jù)中心節(jié)點(diǎn)來(lái)劃分網(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ù)

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

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

中心節(jié)點(diǎn)是指處于整個(gè)網(wǎng)絡(luò)或社區(qū)中心位置的節(jié)點(diǎn)，本文定義中心節(jié)點(diǎn)為網(wǎng)絡(luò)中好友數(shù)量較多的節(jié)點(diǎn)。由于無(wú)標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)的中心的節(jié)點(diǎn)度數(shù)都比較大，根據(jù)我們對(duì)基礎(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模型模擬的安陽(yáng)站日徑流過(guò)程的精度比較結(jié)果詳見(jiàn)表1。NAM模型模擬的日徑流過(guò)程，在率定期內(nèi)，確定性系數(shù)大于0.9，等級(jí)屬于甲等的有2年;確定性系數(shù)大于等于0.7小于等于0.9，等級(jí)屬于乙等的有5年。在驗(yàn)證期內(nèi)，確定性系數(shù)都在大于等于0.7小于等于0.9的范圍內(nèi)，等級(jí)都屬于乙等。徑流深相對(duì)誤差，在率定期內(nèi)，5年都合格，合格率為100%；驗(yàn)證期內(nèi)，3年都合格，合格率為100%。

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

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

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

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

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

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

2.4 鏈點(diǎn)的聚合

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

（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)記為“未訪問(wèn)”狀態(tài)，更新節(jié)點(diǎn)u到社區(qū)T的距離為0，然后將節(jié)點(diǎn)u放到更新隊(duì)列中，狀態(tài)標(biāo)記為“己訪問(wèn)”。

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

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

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

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

2.5 系統(tǒng)輸出

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