面向社交網(wǎng)絡(luò)的用戶數(shù)據(jù)挖掘技術(shù)研究

陳 康，朱應(yīng)堅(jiān)，向 勇

（1.中國電信股份有限公司廣州研究院 廣州510630；2.中國電信股份有限公司廣東分公司 廣州510081）

1 引言

近年來社交媒體風(fēng)靡全球，與此同時(shí)產(chǎn)生了大量的用戶數(shù)據(jù)，如何充分有效地挖掘和利用這些社交數(shù)據(jù)成為最熱門的課題。利用社交媒體數(shù)據(jù)，可提高理解新現(xiàn)象的能力，實(shí)現(xiàn)商業(yè)智能化，為用戶提供更好的服務(wù)，并自動(dòng)發(fā)現(xiàn)創(chuàng)新性商機(jī)。例如，社交數(shù)據(jù)挖掘?qū)⒆R(shí)別出在互聯(lián)網(wǎng)社交環(huán)境中具有重要影響力的人；發(fā)現(xiàn)和歸類隱藏在社交網(wǎng)站中擁有不同興趣的群組；識(shí)別特定用戶并根據(jù)用戶某一時(shí)刻的主觀情感進(jìn)行主動(dòng)規(guī)劃；開發(fā)商品購買推薦系統(tǒng)和朋友推薦的應(yīng)用；掌握IP網(wǎng)絡(luò)的演化和實(shí)體關(guān)系的改變過程；保護(hù)社交網(wǎng)絡(luò)的用戶隱私和安全；建立和加強(qiáng)用戶與用戶之間、用戶與實(shí)體之間的信任度等。社交媒體的數(shù)據(jù)挖掘是一個(gè)生機(jī)勃勃的交叉學(xué)科領(lǐng)域，不同學(xué)科背景的學(xué)者為社交媒體發(fā)展做出了巨大貢獻(xiàn)。

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

2.1 社交媒體的分類

社交媒體主要分類如表1所示。

表1 社交媒體主要分類

2.2 社交數(shù)據(jù)的特點(diǎn)

社交媒體數(shù)據(jù)與傳統(tǒng)數(shù)據(jù)有很大的差異性，呈現(xiàn)出數(shù)量大、噪聲大、非結(jié)構(gòu)化、分散、動(dòng)態(tài)的趨勢，這給數(shù)據(jù)挖掘任務(wù)帶來挑戰(zhàn)，同時(shí)對(duì)于新型、高效的數(shù)據(jù)算法的需求也越來越強(qiáng)烈。

2.3 社交數(shù)據(jù)的價(jià)值

很多關(guān)于人類行為學(xué)的問題都可以通過社交網(wǎng)絡(luò)媒體的數(shù)據(jù)挖掘這個(gè)課題來解決。例如，社交媒體可以幫助廣告商發(fā)現(xiàn)對(duì)其產(chǎn)品感興趣的客戶，最大化廣告投放效益；也可以幫助社會(huì)科學(xué)學(xué)家分析人類活動(dòng)行為特征，如群組內(nèi)活動(dòng)和群組外活動(dòng)。

3 社交數(shù)據(jù)主要研究方向

3.1 社團(tuán)分析

社團(tuán)是由個(gè)體組成的，并且社團(tuán)內(nèi)個(gè)體之間的交互活動(dòng)比個(gè)體與外面的活動(dòng)更為頻繁。基于此定義，社團(tuán)也常常被稱為群組、集群、凝聚子群或者模塊。在社交網(wǎng)絡(luò)中，社團(tuán)大致可以分為顯性和隱性的群體。顯性群體是由用戶間明顯的關(guān)注關(guān)系產(chǎn)生的，而隱性群體則是由自然的網(wǎng)絡(luò)交流活動(dòng)產(chǎn)生。社團(tuán)分析普遍面臨的問題有社團(tuán)的發(fā)現(xiàn)、形成和演變。

社團(tuán)檢測往往是指在社交網(wǎng)絡(luò)中的隱性群體的抽取。社團(tuán)檢測的主要挑戰(zhàn)有：

·社團(tuán)的定義可以是主觀的；

·社團(tuán)評(píng)估的標(biāo)準(zhǔn)可以多樣化，往往沒有決定性正確的。

社團(tuán)檢測可以分為以下4類：

·以節(jié)點(diǎn)為中心的社團(tuán)檢測，其中每個(gè)節(jié)點(diǎn)滿足某些特性，如相互完整性、可達(dá)性、節(jié)點(diǎn)度、內(nèi)外聯(lián)系的頻繁性等，典型例子包括cliques、k-cliques和kclubs；

·以群組為中心的社團(tuán)檢測，其中每個(gè)群組需要滿足一些特性，如最小群密度（minimum group density）；

·以網(wǎng)絡(luò)為中心的社團(tuán)檢測，其中群組的形成是依靠把網(wǎng)絡(luò)分區(qū)成不相交的子集來實(shí)現(xiàn)的，典型的例子有 譜 聚 類 （spectral clustering）和 模 塊 最 大 化（modularity maximization）；

·以層次為中心的社團(tuán)檢測，其目標(biāo)是建立一個(gè)社團(tuán)層級(jí)結(jié)構(gòu)，分析者可以采用不同的策略實(shí)現(xiàn)，典型的方法分為分裂式聚類（divisive clustering）和合并式聚類（agglomerative clustering）。

本文所使用的，也是最為通用的基于模塊化（modularity）值最大化算法。如一個(gè)社交網(wǎng)絡(luò)被劃分為K個(gè)社團(tuán)Pk，模塊化值M(Pk)用于評(píng)價(jià)社交網(wǎng)絡(luò)社團(tuán)劃分質(zhì)量的度量，計(jì)算式為：

社交網(wǎng)絡(luò)的K個(gè)社團(tuán)結(jié)構(gòu)特征越顯著，其M(Pk)值越大。社交媒體網(wǎng)絡(luò)是高度動(dòng)態(tài)性的，因此社團(tuán)會(huì)在動(dòng)態(tài)的網(wǎng)絡(luò)中隨時(shí)擴(kuò)大、收縮或消失，因此社團(tuán)進(jìn)化分析的目標(biāo)包括探索一個(gè)社團(tuán)隨著時(shí)間遷移在動(dòng)態(tài)網(wǎng)絡(luò)中的交互活動(dòng)演變模式。

3.2 影響力建模

分析潛在社交網(wǎng)絡(luò)是由影響力驅(qū)動(dòng)還是同質(zhì)性驅(qū)動(dòng)的，這點(diǎn)非常重要。例如在廣告行業(yè)，如果該社交網(wǎng)絡(luò)是影響力推動(dòng)，那么有影響力的用戶被分辨出來后就可以有償性地讓他們向社交網(wǎng)絡(luò)的用戶推薦產(chǎn)品或服務(wù)；如果這個(gè)網(wǎng)絡(luò)是同質(zhì)性（相似性）驅(qū)動(dòng)的，那么就應(yīng)該將某些用戶作為目標(biāo)直接向其推銷商品。目前大多數(shù)社交網(wǎng)絡(luò)兼有同質(zhì)性和影響力驅(qū)動(dòng)，因而如何分辨哪一個(gè)為主導(dǎo)力是一個(gè)巨大挑戰(zhàn)。檢測出社交網(wǎng)絡(luò)中具有影響力的核心節(jié)點(diǎn)極為重要，下面介紹幾種對(duì)影響力建模的實(shí)現(xiàn)方式。

（1）一個(gè)用戶在社交網(wǎng)絡(luò)中的度數(shù)越大，其影響力也越大：

其中，v為某一用戶節(jié)點(diǎn)，N為整個(gè)社交網(wǎng)絡(luò)。

（2）考慮社交網(wǎng)絡(luò)的信息（如微博）的交互活動(dòng)，根據(jù)用戶的消息記錄計(jì)算每條社交消息的平均轉(zhuǎn)發(fā)率，以每條消息引起的轉(zhuǎn)發(fā)行為作為用戶影響力的衡量指標(biāo)：

其中，s為用戶v所產(chǎn)生的社交消息，R（s）為s的評(píng)價(jià)轉(zhuǎn)發(fā)數(shù)量，S為用戶v所有消息的集合。

（3）基于谷歌的PageRank算法思想，如果社交網(wǎng)絡(luò)某一用戶被越多的優(yōu)質(zhì)用戶所關(guān)注，其影響力就越大，以此為根據(jù)得到社交關(guān)注排名的影響力算法如下：

其中，I（i）為用戶i的影響力，F(xiàn)（i）為關(guān)注用戶i的所有用戶集合，N（j）為用戶j的關(guān)注用戶數(shù)量。

3.3 情感分析與意見挖掘

情感分析和意見挖掘的目標(biāo)是從用戶發(fā)布的內(nèi)容中自動(dòng)抽取出觀點(diǎn)。由于自然語言存在歧義性，情感分析相當(dāng)有難度。情感分析的主要步驟為：

（1）找出相關(guān)文檔；

（2）找出相關(guān)的部分；

（3）找出全部感情；

（4）量化分析每個(gè)感情；

（5）聚集所有感情形成一個(gè)概述判斷。

意見挖掘的主要組成部分是：

·意見表達(dá)的對(duì)象是誰；

·對(duì)這個(gè)對(duì)象表達(dá)了什么意見；

·意見是由誰來表達(dá)的。

3.4 社交推薦

傳統(tǒng)推薦系統(tǒng)是根據(jù)用戶對(duì)物品的關(guān)注程度或歷史購買記錄來推薦相關(guān)物品。社交推薦在原有方法的基礎(chǔ)上，充分利用了用戶的社交網(wǎng)絡(luò)數(shù)據(jù)及其關(guān)聯(lián)信息。社交推薦建立在3個(gè)假設(shè)的基礎(chǔ)上：

·人們傾向于與自己有社交好友關(guān)系的用戶分享相同或相近的興趣（同質(zhì)性）；

·用戶更容易被他們信任的朋友影響；

·與隨機(jī)推薦相比，用戶更愿意相信朋友的推薦。

3.5 信息散布和溯源

信息散布和溯源主要研究信息是如何散布的，并探索出了信息散布的不同模型，包括獨(dú)立級(jí)聯(lián)模型（independent cascade model）、閾值模型（threshold model）、易受感染模型（susceptible-infected model） 和 易 受 感 染 恢 復(fù) 模 型（susceptible-infected-recovered model）。例如分析流言、病毒和疾病暴發(fā)期間的傳播速度。

從社交媒體視角思考信息數(shù)據(jù)的兩個(gè)重要問題：

·信息如何通過社交媒體網(wǎng)絡(luò)傳播及其影響因素；

·那些合理的信息實(shí)質(zhì)上來源于哪里。

4 社交數(shù)據(jù)的挖掘分析

本文對(duì)豆瓣、Flickr、Facebook、Twitter等主流社交媒體網(wǎng)站進(jìn)行了用戶數(shù)據(jù)的獲取、計(jì)算和統(tǒng)計(jì)分析，并重點(diǎn)分析節(jié)點(diǎn)度數(shù)（即某節(jié)點(diǎn)與其他節(jié)點(diǎn)聯(lián)系的數(shù)量）分布、節(jié)點(diǎn)度數(shù)相關(guān)性等。

4.1 節(jié)點(diǎn)度數(shù)分布

本文假設(shè)社交網(wǎng)絡(luò)的數(shù)據(jù)與結(jié)構(gòu)是通過圖（graph）來表示的，其定義為：

節(jié)點(diǎn)（node）為用戶；邊（edge）為用戶之間產(chǎn)生的所有聯(lián)系，既可以是有向的，即每個(gè)聯(lián)系都來源于一個(gè)節(jié)點(diǎn)并終止于另外一個(gè)節(jié)點(diǎn)；也可以是無向的，即兩個(gè)節(jié)點(diǎn)之間的聯(lián)系是不區(qū)分來源和目標(biāo)的。

定義一個(gè)節(jié)點(diǎn)i的度數(shù)為di，即該節(jié)點(diǎn)與其他節(jié)點(diǎn)聯(lián)系的數(shù)量。

（1）入度

入度（in degree）表示到該節(jié)點(diǎn)發(fā)生聯(lián)系的數(shù)量，如圖1所示是社交網(wǎng)站入度值的互補(bǔ)累積分布函數(shù)（complementary cumulative distribution function，CCDF）分布。

圖1 社交網(wǎng)站入度值的CCDF分布示例

（2）出度

出度（out degree）表示從該節(jié)點(diǎn)出去發(fā)生聯(lián)系的數(shù)量，如圖2所示是社交網(wǎng)站出度值的互補(bǔ)累積分布函數(shù)分布。

節(jié)點(diǎn)度數(shù)的分布情況是對(duì)社交網(wǎng)絡(luò)結(jié)構(gòu)最好的刻畫。從以上的入度和出度的CCDF圖和社交網(wǎng)站的計(jì)算結(jié)果來看，其分布都是遵循指數(shù)定律（Power-Law）的。

普通網(wǎng)站與社交網(wǎng)站的節(jié)點(diǎn)聯(lián)系分布有明顯區(qū)別，結(jié)果表明：5%的普通網(wǎng)站節(jié)點(diǎn)占據(jù)了75%的進(jìn)站鏈接（入度），但只占了25%的出站鏈接（出度）。普通網(wǎng)站中的進(jìn)站鏈接比起出站鏈接更容易集中在一些少數(shù)的高度數(shù)節(jié)點(diǎn)中，而Flickr等大多數(shù)社交網(wǎng)站，節(jié)點(diǎn)的進(jìn)站和出站鏈接占比非常相近。

在社交網(wǎng)絡(luò)中擁有高出度的節(jié)點(diǎn)往往也擁有非常高的入度。本文分析的社交網(wǎng)絡(luò)在入度值和出度值排名前1%的節(jié)點(diǎn)中有65%是重疊的，而在普通網(wǎng)站中只有20%是重疊的。這說明社交網(wǎng)絡(luò)中活躍的用戶創(chuàng)建了大量連接，同時(shí)也是很多連接的目標(biāo)，起到了網(wǎng)絡(luò)核心點(diǎn)作用。

圖2 社交網(wǎng)站出度值的CCDF分布示例

4.2 節(jié)點(diǎn)度數(shù)的相關(guān)性

（1）聯(lián)合社交度分布

聯(lián)合社交度分布（joint degree distribution）意為某一度數(shù)節(jié)點(diǎn)連接到其他度數(shù)節(jié)點(diǎn)的可能性，度量值為knn，計(jì)算方式為：給定一個(gè)社交度（social degree，即di）的值N，knn為鏈接到度數(shù)為N的所有節(jié)點(diǎn)的社交度平均值。

圖3表明了Facebook為上升knn分布；但并不是每個(gè)社交網(wǎng)絡(luò)都是這樣，如YouTube為下降趨勢，這是由于“名人效應(yīng)”產(chǎn)生的合理結(jié)果：一群不受歡迎的用戶關(guān)注了少量的炙手可熱的明星。

圖3 Facebook不同社交度的用戶與knn值的關(guān)系

（2）同配性系數(shù)

同配性系數(shù)（assortativity coefficient），縮寫r，為節(jié)點(diǎn)連接到其他類似度數(shù)節(jié)點(diǎn)的可能性，取值范圍為[-1,1]。當(dāng)r>0，節(jié)點(diǎn)連接到其他類似度數(shù)節(jié)點(diǎn)的概率則大，大部分社交網(wǎng)站的r都為正值；當(dāng)r<0，節(jié)點(diǎn)傾向于連接到不相同度數(shù)的其他節(jié)點(diǎn)，如YouTube和普通網(wǎng)站。表2所示為各社交網(wǎng)絡(luò)的同配性系數(shù)值。

表2 各社交網(wǎng)絡(luò)的同配性系數(shù)值

正數(shù)的同配性系數(shù)值也說明了該社交網(wǎng)站的高度數(shù)節(jié)點(diǎn)緊密聯(lián)結(jié)在一起形成核心，而低度數(shù)節(jié)點(diǎn)則分布在網(wǎng)絡(luò)的邊緣地帶。

4.3 路徑長度、直徑與半徑

通常使用平均路徑長度、半徑和直徑用來衡量一個(gè)社交網(wǎng)絡(luò)（區(qū)域或全局性）中用戶之間的距離。

·離心率（eccentricity）：一個(gè)節(jié)點(diǎn)與社交圖中所有其他節(jié)點(diǎn)的最大距離。

·半徑（radius）：該社交圖中所有社交離心率的最小值。

·直徑（diameter）：該社交圖中所有社交離心率的最大值。

·平均路徑長度（average path length）：該社交圖中所有節(jié)點(diǎn)對(duì)之間最短路徑距離值的平均值。

表3說明社交網(wǎng)站的3個(gè)距離度量值都遠(yuǎn)小于普通網(wǎng)站，而平均路徑長度都小于6，這也驗(yàn)證了社交服務(wù)網(wǎng)站符合“六度分隔理論”或稱為“小世界理論”，即“最多通過6個(gè)人就能夠認(rèn)識(shí)任何一個(gè)陌生人”。

表3 普通網(wǎng)站與社交網(wǎng)絡(luò)的平均路徑長度、半徑和直徑

4.4 社區(qū)聚類與網(wǎng)絡(luò)核心

（1）用戶之間的群組聚類

聚類系數(shù)（clustering coefficient）用來刻畫用戶節(jié)點(diǎn)之間聯(lián)系的緊密程度，其計(jì)算式為：

其中，n為節(jié)點(diǎn)i的所有鄰居間的聯(lián)系數(shù)量。

而一個(gè)社交圖G的平均聚類系數(shù)（average clustering coefficient）的計(jì)算式為：

平均聚類系數(shù)的值越高，說明該群組中節(jié)點(diǎn)間的聯(lián)系越緊密。圖4所示表明小群組的成員往往比大群組成員的聚類系數(shù)高，也結(jié)合得更為緊密；低度數(shù)節(jié)點(diǎn)往往只參與少量的群組，而高度數(shù)節(jié)點(diǎn)傾向于成為多個(gè)群組的成員。

圖4 關(guān)系圖中節(jié)點(diǎn)度數(shù)與平均群組聚類系數(shù)大小的關(guān)系

（2）社交網(wǎng)絡(luò)的核心節(jié)點(diǎn)

社交網(wǎng)絡(luò)結(jié)構(gòu)的核心必須滿足兩個(gè)條件。首先，是不可替代的連接作用，除去網(wǎng)絡(luò)核心使得其他的節(jié)點(diǎn)被分割成許多細(xì)小群組；其次，核心必須是通過很小的直徑值相連的。因此核心就是能使網(wǎng)絡(luò)的其他部分保持緊密連接的小群組。本文研究數(shù)據(jù)表明，大部分社交網(wǎng)絡(luò)都擁有緊密聯(lián)系在一起的核心點(diǎn)，占高度數(shù)節(jié)點(diǎn)的1%～10%，刪除這些核心將會(huì)完全破壞社交網(wǎng)絡(luò)圖的結(jié)構(gòu)。

5 社交關(guān)系圖的可視分析

在Twitter中，以“@name”方式向其他用戶發(fā)送一個(gè)或多個(gè)以“#theme”方式標(biāo)記的主題信息，以達(dá)到傳遞信息。本文以此為例，介紹社交關(guān)系圖的可視分析過程。

5.1 數(shù)據(jù)的預(yù)處理

通過Twitter API，用戶可發(fā)表信息、主題、用戶信息、模板和背景等內(nèi)容。預(yù)處理后的數(shù)據(jù)含有560個(gè)節(jié)點(diǎn)和1 257條邊（其格式分別如表4、表5所示）。

表4 節(jié)點(diǎn)信息示例

表5 邊信息示例

5.2 結(jié)果的可視化

（1）社交圖的可視化

使用Gephi可視化軟件對(duì)數(shù)據(jù)進(jìn)行處理和可視化：

·在數(shù)據(jù)資料面板對(duì)數(shù)據(jù)進(jìn)行添加、刪除以及合并等處理；

·在統(tǒng)計(jì)面板分別進(jìn)行“網(wǎng)絡(luò)直徑”和“模塊化”分析；

·在 流 程 面 板 對(duì) 圖 分 別 使 用 “Force Atlas”、“FruchtermanReingold”和“Label Adjust”3個(gè) 算 法，并在排序面板設(shè)計(jì)節(jié)點(diǎn)、邊和標(biāo)簽的顏色與大小。

·對(duì)子網(wǎng)絡(luò)（社團(tuán)）進(jìn)行詳細(xì)分析，在濾波面板選擇庫中的“屬性”文件夾，并添加其中的模塊化分析，對(duì)圖形結(jié)果進(jìn)行過濾和分析。

Twitter數(shù)據(jù)的可視化結(jié)果如圖5所示，含有@字符的節(jié)點(diǎn)是用戶節(jié)點(diǎn)，含有#字符的節(jié)點(diǎn)是主題節(jié)點(diǎn)，而箭頭表示用戶發(fā)表的主題或是一個(gè)用戶@向另外一個(gè)用戶。由整圖可以看出，用戶ddjournalism、mirkolorenz、jplusplus、jeanabbiateci為digiphile最活躍、影響力最大的用戶，而opendata、dataviz、data以及projectk是討論得最多的主題。

（2）社團(tuán)檢測

社團(tuán)的識(shí)別和輸出就是將用戶間的關(guān)系進(jìn)行可視化顯示，了解社團(tuán)的成員情況。在圖5的基礎(chǔ)上，以用戶“ddjournlism”為中心，進(jìn)一步分析了其社團(tuán)結(jié)構(gòu)，如圖6所示。

圖5 Twitter用戶關(guān)系網(wǎng)絡(luò)的可視化效果

圖6 以用戶“ddjournlism”為中心的社團(tuán)結(jié)構(gòu)

（3）主題分析

對(duì)特定的話題進(jìn)行分析，以了解哪些用戶討論了某個(gè)話題。圖7展示了以“opendata”主題為中心的主題結(jié)構(gòu)。

圖7 以主題“opendata”為中心的主題結(jié)構(gòu)

（4）社團(tuán)與主題分析的關(guān)系

在一個(gè)同時(shí)包含用戶和主題的數(shù)據(jù)集中進(jìn)行社團(tuán)與主題分析，這兩個(gè)分析之間必然有區(qū)別與聯(lián)系。區(qū)別在于一個(gè)社團(tuán)之間交流信息可以不帶主題，而主題則必須要用戶創(chuàng)造和傳播，因此社團(tuán)中用戶可以形成鏈、樹或圖，而一個(gè)主題則必須直接連接到用戶；聯(lián)系則是當(dāng)一個(gè)社團(tuán)在交流時(shí)，總會(huì)有一個(gè)特定的話題，如用戶ddjournalism創(chuàng)造了話題dataviz，而討論和傳播這個(gè)話題的用戶大多都在以創(chuàng)造者為中心的社團(tuán)內(nèi)。

6 結(jié)束語

社交媒體作為大數(shù)據(jù)的主要類型，正展現(xiàn)出它的革新性應(yīng)用，例如政治選舉、工作申請(qǐng)、商務(wù)推廣和網(wǎng)絡(luò)化客戶服務(wù)；而挖掘社交網(wǎng)絡(luò)的商業(yè)應(yīng)用模式能加速傳染式營銷，使各類基層團(tuán)體快速增長，用于趨勢分析和銷售預(yù)測。社交數(shù)據(jù)挖掘研究的初步成功驗(yàn)證了社交媒體數(shù)據(jù)挖掘社團(tuán)的光明前景，有助于擴(kuò)大和發(fā)展對(duì)在線和離線的人類活動(dòng)和交互模式的研究。社交媒體數(shù)據(jù)會(huì)繼續(xù)著它的高速增長步伐，而新算法和新工具亟需我們繼續(xù)探索研究。

1 Newman M E J,Girvan M．Finding and evaluating community structure in networks．Phys Rev E,2004,69(2)

2 White S,Smyth P．A spectral clustering approach to finding communities in graphs．Proceedings of 5th SIAM Int’l Conference on Data Mining,Philadelphia,USA,2005

3 Girvan M,Newman M E J．Community structure in social and biological networks．Proceedings of National Academy of Sciences of the United States of America，2002，99(12)：7821～7826

4 Alon A,Tennenholtz M.Ranking systems:the PageRank axioms.Proceedings of the 6th ACM conference on Electronic commerce(EC-05),Vancouver,Canada,2005

5 李紹華，高文宇.搜索引擎頁面排序算法研究綜述.計(jì)算機(jī)應(yīng)用研究，2007，24(6):4～7