陳 康，朱應堅，向 勇

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

1 引言

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

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

2.1 社交媒體的分類

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

表1 社交媒體主要分類

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

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

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

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

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

3.1 社團分析

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

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

·社團的定義可以是主觀的；

·社團評估的標準可以多樣化，往往沒有決定性正確的。

社團檢測可以分為以下4類：

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

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

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

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

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

社交網(wǎng)絡的K個社團結構特征越顯著，其M(Pk)值越大。社交媒體網(wǎng)絡是高度動態(tài)性的，因此社團會在動態(tài)的網(wǎng)絡中隨時擴大、收縮或消失，因此社團進化分析的目標包括探索一個社團隨著時間遷移在動態(tài)網(wǎng)絡中的交互活動演變模式。

3.2 影響力建模

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

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

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

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

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

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

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

3.3 情感分析與意見挖掘

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

（1）找出相關文檔；

（2）找出相關的部分；

（3）找出全部感情；

（4）量化分析每個感情；

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

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

·意見表達的對象是誰；

·對這個對象表達了什么意見；

·意見是由誰來表達的。

3.4 社交推薦

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

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

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

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

3.5 信息散布和溯源

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

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

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

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

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

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

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

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

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

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

（1）入度

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

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

（2）出度

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

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

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

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

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

4.2 節(jié)點度數(shù)的相關性

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

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

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

圖3 Facebook不同社交度的用戶與knn值的關系

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

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

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

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

4.3 路徑長度、直徑與半徑

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 社交關系圖的可視分析

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

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

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

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

表5 邊信息示例

5.2 結果的可視化

（1）社交圖的可視化

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

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

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

·在 流 程 面 板 對 圖 分 別 使 用 “Force Atlas”、“FruchtermanReingold”和“Label Adjust”3個 算 法，并在排序面板設計節(jié)點、邊和標簽的顏色與大小。

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

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

（2）社團檢測

社團的識別和輸出就是將用戶間的關系進行可視化顯示，了解社團的成員情況。在圖5的基礎上，以用戶“ddjournlism”為中心，進一步分析了其社團結構，如圖6所示。

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

圖6 以用戶“ddjournlism”為中心的社團結構

（3）主題分析

對特定的話題進行分析，以了解哪些用戶討論了某個話題。圖7展示了以“opendata”主題為中心的主題結構。

圖7 以主題“opendata”為中心的主題結構

（4）社團與主題分析的關系

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

6 結束語

社交媒體作為大數(shù)據(jù)的主要類型，正展現(xiàn)出它的革新性應用，例如政治選舉、工作申請、商務推廣和網(wǎng)絡化客戶服務；而挖掘社交網(wǎng)絡的商業(yè)應用模式能加速傳染式營銷，使各類基層團體快速增長，用于趨勢分析和銷售預測。社交數(shù)據(jù)挖掘研究的初步成功驗證了社交媒體數(shù)據(jù)挖掘社團的光明前景，有助于擴大和發(fā)展對在線和離線的人類活動和交互模式的研究。社交媒體數(shù)據(jù)會繼續(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 李紹華，高文宇.搜索引擎頁面排序算法研究綜述.計算機應用研究，2007，24(6):4～7