曹海洋　季小俊

摘要：近年來(lái)，社交網(wǎng)絡(luò)發(fā)展迅速，各種社交的網(wǎng)絡(luò)平臺(tái)每天都會(huì)產(chǎn)生海量的用戶數(shù)據(jù)。這些無(wú)序的數(shù)據(jù)中隱藏著潛在的價(jià)值，也為研究者提供了用數(shù)據(jù)挖掘中的方法來(lái)分析這些數(shù)據(jù)的機(jī)會(huì)。聚類是數(shù)據(jù)挖掘中的一個(gè)基本技術(shù)，而利用聚類方法我們能夠?qū)崿F(xiàn)LinkedIn職業(yè)網(wǎng)絡(luò)中的數(shù)據(jù)挖掘。

關(guān)鍵詞：社交網(wǎng)絡(luò)；數(shù)據(jù)挖掘；應(yīng)用；聚類；LinkedIn職業(yè)網(wǎng)絡(luò)

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）13-0001-02

Abstract：In recent years， with the rapid development of social network， the different social networking sites produce large amounts of user data every day. There is potential value in these disordered data. It also provides researchers with opportunity of using data mining methods to analyze these data. Clustering is an essential data mining techniques， and we can achieve data mining in LinkedIn professional network with the use of clustering method.

Key words： social network； data mining； application； clustering； linkedin professional network

社交網(wǎng)絡(luò)，顧名思義是用于社交的網(wǎng)絡(luò)平臺(tái)，它最初是以交友為開端的，在社會(huì)的不斷發(fā)展中逐漸演變成了今天的集社交、通訊、娛樂、商業(yè)等元素為一體的多元化平臺(tái)?；诰W(wǎng)絡(luò)的社會(huì)交往誕生于早期的基于終端的計(jì)算機(jī)，以及通過(guò)新聞組或其他早期的互聯(lián)網(wǎng)軟件來(lái)進(jìn)行。社交網(wǎng)絡(luò)的新時(shí)代開始于互聯(lián)網(wǎng)的性能的上升，以及萬(wàn)維網(wǎng)（Web）的逐漸占據(jù)主導(dǎo)地位。

近年來(lái)，國(guó)內(nèi)的新浪微博、人人網(wǎng)，國(guó)外的Facebook、Twitter和LinkedIn等社交網(wǎng)站，也已經(jīng)從時(shí)尚變?yōu)橹髁鳌６缃痪W(wǎng)絡(luò)的爆發(fā)之所以能在最近幾年爆發(fā)，很大程度上是由于社交網(wǎng)絡(luò)和媒體共享網(wǎng)站提供了大量的用戶數(shù)據(jù)。而如何對(duì)這些海量數(shù)據(jù)進(jìn)行高效的分析和處理，也決定了社交網(wǎng)絡(luò)今后的發(fā)展。

1 社交網(wǎng)絡(luò)數(shù)據(jù)分析概述

網(wǎng)絡(luò)和信息技術(shù)的飛速發(fā)展使得社交網(wǎng)絡(luò)成為人們生活中不可缺少的一部分。網(wǎng)絡(luò)設(shè)計(jì)采用電子郵件作為一個(gè)起點(diǎn)，而不是實(shí)際生活中的信件。然后開心網(wǎng)，BBS等網(wǎng)站，是由它演變，并且以虛擬為其主要特色。在社交網(wǎng)絡(luò)演進(jìn)的過(guò)程中，個(gè)人的形象由實(shí)際生活中的具體個(gè)人轉(zhuǎn)化為一個(gè)虛擬形象。所有的這一切都?xì)w功于社交網(wǎng)絡(luò)的誕生，然后又驅(qū)使人們提出網(wǎng)絡(luò)擴(kuò)展和降低成本的特征之間的聯(lián)系。良好的社交網(wǎng)絡(luò)數(shù)據(jù)分析技術(shù)可以在社交網(wǎng)絡(luò)的爆炸式發(fā)展的過(guò)程中為用戶們創(chuàng)建一個(gè)積極樂觀的網(wǎng)絡(luò)環(huán)境和氛圍。

流行的社交網(wǎng)絡(luò)如今被認(rèn)為是社交加網(wǎng)絡(luò)，即通過(guò)將網(wǎng)絡(luò)作為載體，將很多的用戶連接以形成具有一定特性的虛擬社區(qū)。和基礎(chǔ)科學(xué)不同，對(duì)社交網(wǎng)絡(luò)的數(shù)據(jù)分析重點(diǎn)是人與人之間的相互聯(lián)系[1]，而不僅僅是獨(dú)立個(gè)體的屬性。社交網(wǎng)絡(luò)分析就是研究這種社會(huì)結(jié)構(gòu)的，它主要檢查關(guān)系之間的結(jié)構(gòu)和組成，并分析其結(jié)構(gòu)特點(diǎn)[2]。通常包括：

1）個(gè)體的鄰接點(diǎn)之間是如何連接的；

2）彼此之間經(jīng)常進(jìn)行通信的個(gè)體[3]（社區(qū)）；

3）通過(guò)網(wǎng)絡(luò)傳遞信息所涉及的個(gè)體數(shù)[4]（路徑長(zhǎng)度）；

4）實(shí)際網(wǎng)絡(luò)中可能存在的關(guān)系的比重[5]（密度）。

2 數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)中的具體應(yīng)用——LinkedIn中的職業(yè)網(wǎng)絡(luò)聚類

2.1 LinkedIn中數(shù)據(jù)挖掘的意義

LinkedIn是全球最大的職業(yè)社交網(wǎng)站，它主要關(guān)注用戶的職業(yè)和相互之間的商業(yè)關(guān)系，即“人脈”。LinkedIn的理想定位為年輕職業(yè)人員，被廣泛地用于構(gòu)建和維護(hù)外部職業(yè)網(wǎng)絡(luò)。因?yàn)長(zhǎng)inkedIn的管理團(tuán)隊(duì)認(rèn)為用戶的職業(yè)數(shù)據(jù)本質(zhì)上是私有的，并且這些數(shù)據(jù)非常寶貴，不能像Facebook或Twitte上的好友那樣任意查看。由于這類數(shù)據(jù)的敏感性，LinkedIn中API提供的數(shù)據(jù)和一般社交網(wǎng)站是有本質(zhì)區(qū)別的[6]。LinkedIn限制用戶訪問(wèn)自己“一度人脈”的某些信息，因此它不適用于作為圖挖掘。本章下面的內(nèi)容將介紹如何用基本的聚類分析來(lái)幫助用戶找到以下幾個(gè)問(wèn)題的答案：

1）你的哪些“人脈”和你的職位最相似？

2）你的哪些“人脈”曾在想去的公司工作過(guò)？

3）你的大多數(shù)“人脈”住在什么地方？

2.2 使用聚類分析的動(dòng)機(jī)

聚類分析可以作為一個(gè)單獨(dú)的工具被用以發(fā)現(xiàn)數(shù)據(jù)庫(kù)中分布的一些深層的信息，然后歸納出每一類的特點(diǎn)，或者把注意力放在某一個(gè)特定的類上以作進(jìn)一步的分析[7]。對(duì)于LinkedIn的大量數(shù)據(jù)，在實(shí)現(xiàn)上一節(jié)中提到的數(shù)據(jù)挖掘時(shí)，我們會(huì)遇到兩個(gè)問(wèn)題：

對(duì)于職位、公司名稱、專業(yè)領(lǐng)域等字段，如何合理度量?jī)蓚€(gè)字符串之間的相似性。

如何用時(shí)間復(fù)雜度較小的算法將所有的項(xiàng)用一個(gè)相似性度量聚合成一個(gè)集合。

上述兩個(gè)問(wèn)題也是聚類分析中通常會(huì)涉及的問(wèn)題，因此可以按職位將聯(lián)系人聚類來(lái)實(shí)現(xiàn)LinkedIn中的數(shù)據(jù)挖掘。

2.3 聚類分析的具體過(guò)程

2.3.1 規(guī)范職位名稱和統(tǒng)計(jì)職位數(shù)量

在使用LinkedIn數(shù)據(jù)集時(shí)，先要導(dǎo)出一定數(shù)量的聯(lián)系人。由于職位之間的細(xì)微差別也可能對(duì)數(shù)據(jù)挖掘結(jié)果產(chǎn)生巨大的影響，因此在處理這些數(shù)據(jù)之前，先通過(guò)用已知縮寫來(lái)替換同義的職位（如“總裁”和“CEO”）來(lái)標(biāo)準(zhǔn)化常見的職位，再通過(guò)編碼計(jì)算這些職位出現(xiàn)的頻率。這里得到的頻率分布的結(jié)果只是針對(duì)職位中的全職稱和個(gè)別標(biāo)記，但仍可以作為后面數(shù)據(jù)分析的起始模板。

2.3.2 對(duì)職位的相似性度量

在獲取一組表示職位的字符串并以一種有效的方法將他們聚類時(shí)，面臨最大的問(wèn)題是使用哪種基本的相似性度量[8]。對(duì)字符串的相似性度量在很大程度上取決于目標(biāo)的性質(zhì)。而在比較職位時(shí)，可能會(huì)使用如下的幾種常見的相似性度量：

l 編輯距離

編輯距離是一種簡(jiǎn)單的度量，它用于記錄將一個(gè)字符串轉(zhuǎn)換成另一個(gè)字符串時(shí)，需要插入、刪除或替換的次數(shù)[9]。例如，將“bed”轉(zhuǎn)換成“bad”需要一次替換操作，編輯距離為1。對(duì)于長(zhǎng)度為K和P的字符串來(lái)說(shuō)，計(jì)算編輯距離的時(shí)間復(fù)雜度為O（K*P）。

l N元語(yǔ)法相似度

N元語(yǔ)法可以簡(jiǎn)單的表示文本中n個(gè)標(biāo)記的所有可能的連續(xù)序列，它提供了計(jì)算不同排列的基本數(shù)據(jù)結(jié)構(gòu)[10]。N元語(yǔ)法相似度有很多變化，考慮最簡(jiǎn)單的情況：計(jì)算兩個(gè)字符串標(biāo)記中所有可能的二元語(yǔ)法，通過(guò)統(tǒng)計(jì)兩個(gè)字符串之間共同的二元語(yǔ)法來(lái)計(jì)算它們之間的相似度。

l MASI距離

MASI距離度量是雅克比相似度的加權(quán)版本[11-12]，當(dāng)集合之間存在部分重疊時(shí)，它通過(guò)調(diào)整得分來(lái)生產(chǎn)小于雅克比相似度的距離。MASI距離的測(cè)量方式如1所示：

1 -float（len（X.intersection（Y）））/float（max（len（X），len（Y））） （1）

其中，X和Y表示項(xiàng)集。需要注意的是，當(dāng)兩個(gè)集合完全不相交或相等時(shí)，MASI距離和雅克比距離相同；當(dāng)兩個(gè)集合部分重合時(shí)，MASI距離大于雅克比距離。針對(duì)表示職位的字符串，顯然符合后一種情況，因此這里使用MASI距離會(huì)更高效。

3 使用貪心啟發(fā)來(lái)聚類職位

本節(jié)介紹如何將職位聚類，并用MASI距離與其他職位相對(duì)比。這里，用編碼從常見的連詞列表分離出綜合職位，并標(biāo)準(zhǔn)化常見職位。然后嵌套循環(huán)遍歷所有的職位，并根據(jù)一個(gè)閾值MASI相似性度量將它們聚類。如果相似性啟發(fā)確定的任意兩個(gè)職位的距離足夠近，就可以“貪婪”地將它們聚合起來(lái)。在此基礎(chǔ)上，“貪婪”意味著第一次就能確定一個(gè)可能適合某一聚類的項(xiàng)，繼續(xù)前進(jìn)并對(duì)其分配，而不需要考慮是否有更合適的選擇[9]。

然后，用編碼根據(jù)特定的職位查詢聯(lián)系人，并將結(jié)果分組顯示。結(jié)果的可視化效果如圖1所示：

3.1從地理上聚類網(wǎng)絡(luò)

本節(jié)將介紹如何使用Google Earth標(biāo)識(shí)LinkedIn職業(yè)網(wǎng)絡(luò)。為了實(shí)現(xiàn)聚類在Google Earth上的可視化，第一步先要從每個(gè)聯(lián)系人的公開資料中解析出地理位置，然后根據(jù)地理編碼器將位置編碼到坐標(biāo)中。接著把地理坐標(biāo)提供給聚類模塊來(lái)計(jì)算聚類，這里會(huì)按地址將聯(lián)系人分組，將他們聚類，然后用聚類的結(jié)果計(jì)算質(zhì)心。由此，我們可以得出“人脈”住在哪里的答案。

以LinkedIn為代表的社交網(wǎng)絡(luò)軟件在我們研究的問(wèn)題中被大量使用。本章介紹了基本的聚類技術(shù)，并通過(guò)各種方式將它們應(yīng)用到LinkedIn職業(yè)網(wǎng)絡(luò)的數(shù)據(jù)中，以此來(lái)找到關(guān)于“人脈”的幾個(gè)問(wèn)題的答案，并且整個(gè)數(shù)據(jù)挖掘的過(guò)場(chǎng)快速高效，交互方式友好，為用戶的職業(yè)網(wǎng)絡(luò)管理提供了一種全新的體驗(yàn)。通過(guò)這幾個(gè)LinkedIn職業(yè)網(wǎng)絡(luò)中的實(shí)例，我們可以了解到數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)中的具體應(yīng)用。

4 結(jié)束語(yǔ)

本文簡(jiǎn)要地介紹了社交網(wǎng)絡(luò)中的數(shù)據(jù)挖掘應(yīng)用的意義。并通過(guò)一個(gè)具體的實(shí)例——用聚類方法實(shí)現(xiàn)的LinkedIn職業(yè)網(wǎng)絡(luò)的數(shù)據(jù)挖掘來(lái)介紹社交網(wǎng)絡(luò)中數(shù)據(jù)挖掘的大致方法和過(guò)程。除此之外，我們還能用其他的數(shù)據(jù)挖掘方法，對(duì)各種社交網(wǎng)絡(luò)的數(shù)據(jù)進(jìn)行高效的分析和處理，以滿足用戶在使用社交網(wǎng)絡(luò)過(guò)程中的各種需求。

參考文獻(xiàn)：

[1] Calvani A， Fini A， Molino M， et al. Visualizing and monitoring effective interactions in online collaborative groups[J]. British Journal of Educational Technology， 2010， 41（2）：213-226.

[2] Limited B P. British Journal of Educational Technology[J]. British Journal of Educational Technology， 2009， 35（3）：275-288. （下轉(zhuǎn)第5頁(yè)）

（上接第2頁(yè)）

[3] Chen J， Fagnan J， Goebel R， et al. Meerkat： Community mining with dynamic social networks[C]. In Data Mining Workshops （ICDMW）， 2010 IEEE International Conference on， 2010： 1377-1380.

[4] Artz D， Gil Y. A survey of trust in computer science and the Semantic Web[J]. Web Semantics Science Services & Agents on the World Wide Web， 2007， 5（2）：58-71.

[5] Rodgers R J， Halford J C G， Souza R L N D， et al. SB-334867， a selective orexin-1 receptor antagonist， enhances behavioural satiety and blocks the hyperphagic effect of orexin-A in rats[J]. Annals of Oncology Official Journal of the European Society for Medical Oncology， 2001， 13（7）：1444–1452.

[6] Backstrom L， Leskovec J. Supervised random walks： predicting and recommending links in social networks[C]// ACM International Conference on Web Search & Data Mining. ACM， 2010：635-644.

[7] Marco A D， Navigli R. Clustering Web Search Results with Maximum Spanning Trees[J]. Lecture Notes in Computer Science， 2010， 6934：201-212.

[8] Cho H， Gay G， Davidson B， et al. Social networks， communication styles， and learning performance in a CSCL community[J]. Computers & Education， 2007， 49（2）：309-329.

[9] Clauset A， Newman M E J， Moore C. Finding community structure in very large networks. Phys Rev E 70（6）：066111[J]. Physical Review E， 2005， 70（6 Pt 2）.

[10] Tang J， Hu X， Liu H. Social recommendation： a review[J]. Social Network Analysis & Mining， 2013， 3（4）：1113-1133.

[11] Agarwal N， Liu H， Tang L， et al. Modeling blogger influence in a community[J]. Social Network Analysis & Mining， 2011， 2（2）：139-162.

[12] Aral S， Muchnik L， Sundararajan A. Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. Proc Natl Acad Sci[J]. Proceedings of the National Academy of Sciences， 2009， 106（51）：21544-9.