社會(huì)網(wǎng)絡(luò)挖掘的應(yīng)用

錢萬良 高 燕

（南京河海大學(xué)公共管理學(xué)院，江蘇南京 210098）

0 引言

數(shù)據(jù)挖掘（Data Mining），就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的非平凡過程。通俗的說，數(shù)據(jù)挖掘就是對(duì)一大堆數(shù)據(jù)進(jìn)行分析，獲取其中的某種規(guī)律，進(jìn)而能做出某種估計(jì)或預(yù)測，從而給人們的社會(huì)生產(chǎn)或生活帶來一定程度的幫助或指導(dǎo)。世界零售業(yè)巨頭沃爾瑪公司通過對(duì)其顧客購物行為進(jìn)行購物車分析，得出了“跟尿布一起購買最多的商品是啤酒”的結(jié)論，按常規(guī)思維，尿布和啤酒風(fēng)馬牛不相及，若不是借助數(shù)據(jù)挖掘技術(shù)對(duì)大量數(shù)據(jù)進(jìn)行分析與挖掘，沃爾瑪是不可能發(fā)現(xiàn)這一奇妙的規(guī)律的。這是數(shù)據(jù)挖掘的一則經(jīng)典案例，通過這則故事，人們對(duì)數(shù)據(jù)挖掘的興趣也大大加深了。

社會(huì)網(wǎng)絡(luò)（Social Network）作為數(shù)據(jù)挖掘的子領(lǐng)域，在近年有著飛速的發(fā)展，它也是目前數(shù)據(jù)挖掘中與社會(huì)生活聯(lián)系的最緊密的熱點(diǎn)研究方向之一。社會(huì)網(wǎng)絡(luò)發(fā)現(xiàn)領(lǐng)域的研究廣泛應(yīng)用在疾病的傳播、科學(xué)家的合作、文獻(xiàn)引用和恐怖分子網(wǎng)絡(luò)等方面。社會(huì)網(wǎng)絡(luò)是由圖表示的異構(gòu)多關(guān)系的數(shù)據(jù)集。這種圖一般都很大，節(jié)點(diǎn)對(duì)應(yīng)對(duì)象，邊對(duì)應(yīng)表示對(duì)象間聯(lián)系或相互作用的鏈接。節(jié)點(diǎn)和鏈接都有屬性，對(duì)象可以具有類標(biāo)號(hào)，鏈接可以是單向的并且不必是二元的。在實(shí)際應(yīng)用中，有許多科技、商業(yè)、經(jīng)濟(jì)等方面的社會(huì)網(wǎng)絡(luò)實(shí)力，比如消費(fèi)網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、計(jì)算機(jī)病毒傳播、聊天室、朋友聯(lián)系等，總之社會(huì)網(wǎng)絡(luò)問題在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用。

我之所以選擇社會(huì)網(wǎng)絡(luò)發(fā)現(xiàn)問題作為我研究的數(shù)據(jù)挖掘子領(lǐng)域，就是因?yàn)槲矣X得這個(gè)子領(lǐng)域與社會(huì)的密切聯(lián)系，任何一個(gè)學(xué)術(shù)界的研究成果，如果最終沒有投入到社會(huì)生產(chǎn)中，使之轉(zhuǎn)換為價(jià)值，那這個(gè)研究成果的成色將被打上一定的折扣。

社會(huì)網(wǎng)絡(luò)的分支有很多種，科研人員在不同領(lǐng)域進(jìn)行研究，研究了博客圈中作者與博文內(nèi)容的聯(lián)系，使用數(shù)據(jù)挖掘模型去解決物聯(lián)網(wǎng)的問題，還有通過數(shù)據(jù)挖掘手段從事犯罪調(diào)查的。

1 社會(huì)網(wǎng)絡(luò)發(fā)現(xiàn)的研究狀況

1.1 研究發(fā)展簡史

社會(huì)網(wǎng)絡(luò)發(fā)現(xiàn)可以說是一個(gè)比較經(jīng)典的研究方向，而且不同專業(yè)的人士在這個(gè)領(lǐng)域都從事著不同的研究工作。社會(huì)網(wǎng)絡(luò)發(fā)現(xiàn)并不是在一個(gè)學(xué)科中發(fā)展出來的，而是在眾多學(xué)者的不斷努力下，在多個(gè)學(xué)科中相對(duì)獨(dú)立的發(fā)展壯大的。最初對(duì)社會(huì)網(wǎng)絡(luò)感興趣的是英國人類學(xué)家布朗，他以相對(duì)非技術(shù)的形式提出了“社會(huì)網(wǎng)絡(luò)”思想。從二十世紀(jì)30年代到70年代，越來越多的社會(huì)人類學(xué)家和社會(huì)學(xué)家涉足這個(gè)領(lǐng)域，然而社會(huì)網(wǎng)絡(luò)發(fā)現(xiàn)的另一次突破歸功于美國哈佛大學(xué)的學(xué)者，他們從數(shù)學(xué)的角度定量刻畫網(wǎng)絡(luò)結(jié)構(gòu)。自此之后，隨著數(shù)學(xué)與計(jì)算機(jī)技術(shù)的發(fā)展，社會(huì)網(wǎng)絡(luò)發(fā)現(xiàn)取得更加重大的突破。

從社會(huì)關(guān)系存在的形態(tài)劃分，社會(huì)關(guān)系可以分為靜態(tài)關(guān)系和動(dòng)態(tài)關(guān)系。前者指社會(huì)關(guān)系的構(gòu)成模式，又稱社會(huì)結(jié)構(gòu)，后者指社會(huì)關(guān)系的相互作用模式，又稱社會(huì)互動(dòng)。

1.2 相關(guān)概念

社會(huì)網(wǎng)絡(luò)指的是社會(huì)行動(dòng)者及其間的關(guān)系的集合。一個(gè)社會(huì)網(wǎng)絡(luò)是有多個(gè)點(diǎn)（社會(huì)行動(dòng)者）和各點(diǎn)之間的連線（行動(dòng)者之間的關(guān)系）組成的集合。用點(diǎn)和線來表達(dá)網(wǎng)絡(luò)，這是社會(huì)網(wǎng)絡(luò)的可視化界定。社會(huì)網(wǎng)絡(luò)強(qiáng)調(diào)每個(gè)行動(dòng)者都與其它行動(dòng)者有或多或少的關(guān)系。社會(huì)網(wǎng)絡(luò)分析方法關(guān)注如何建立這些關(guān)系的模型，力圖描述群體關(guān)系的結(jié)構(gòu)，研究這種結(jié)構(gòu)對(duì)群體功能或者群體內(nèi)部個(gè)體的影響。社會(huì)網(wǎng)絡(luò)分析被用來建立社會(huì)關(guān)系的模型，發(fā)現(xiàn)群體內(nèi)行動(dòng)者之間的社會(huì)關(guān)系，描述社會(huì)關(guān)系的結(jié)構(gòu)，研究這種結(jié)構(gòu)對(duì)群體功能或者群體內(nèi)部個(gè)體的影響。

社會(huì)網(wǎng)絡(luò)在圖論中可以表示為，其中節(jié)點(diǎn)集V和邊集E固定不變的社會(huì)網(wǎng)絡(luò)稱為靜態(tài)社會(huì)網(wǎng)絡(luò)，節(jié)點(diǎn)集V和邊集E會(huì)隨著時(shí)間的變化而變化的社會(huì)網(wǎng)絡(luò)稱為動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)。

圖1 社會(huì)網(wǎng)絡(luò)示例圖

1.3 相關(guān)工作及算法

關(guān)于社會(huì)網(wǎng)絡(luò)的分析工作有著長遠(yuǎn)而全面的歷史，從統(tǒng)計(jì)領(lǐng)域到可視角度，在生物科學(xué)、社會(huì)學(xué)和信息學(xué)方面有著廣泛的應(yīng)用。研究人員曾提出大量用于測量社會(huì)網(wǎng)絡(luò)的統(tǒng)計(jì)特性，包括聚類、程度分布和凝聚性。凝聚性決定了網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的相關(guān)重要性，通常用度數(shù)和相關(guān)性等來度量。在因特網(wǎng)中還廣泛使用了一種更加精確的方法，即特征向量凝聚性，這個(gè)方法在網(wǎng)頁排名和HITS算法的相關(guān)論文中有著詳細(xì)的描述。White和Smyth提出了一種名叫馬爾科夫凝聚法的可選擇性算法，這種算法將一個(gè)社會(huì)網(wǎng)絡(luò)看成一個(gè)馬爾科夫鏈。

在靜態(tài)社會(huì)網(wǎng)絡(luò)中多采用經(jīng)典的層次聚類方法：層次的聚類方法將數(shù)據(jù)對(duì)象組成聚類的樹。根據(jù)層次分解是自底向上，還是自頂向下形成，層次的聚類方法可以進(jìn)一步分為凝聚和分裂層次聚類。凝聚的層次聚類：這種自底向上的策略首先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來越大的簇，直到所有的對(duì)象都在一個(gè)簇中，或者某個(gè)終結(jié)條件被滿足。絕大多數(shù)層次聚類方法屬于這一類，它們只是在簇間相似度的定義上有所不同。分裂的層次聚類：這是一種自頂向下的策略，它首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來越小的簇，直到每個(gè)對(duì)象自成一簇，或者達(dá)到了某個(gè)終結(jié)條件。

2 數(shù)據(jù)挖掘技術(shù)在社會(huì)網(wǎng)絡(luò)發(fā)現(xiàn)中的應(yīng)用

2.1 博客圈中的社會(huì)網(wǎng)絡(luò)挖掘

博客圈中含有大量來自不同領(lǐng)域的信息，根據(jù)權(quán)威搜索工具顯示，每天至少有900，000篇博客發(fā)布，于是要想知道哪些產(chǎn)品、品牌、人物、技術(shù)或事件是最被人們關(guān)注的，查查人們寫的博客即可。中實(shí)現(xiàn)了掌控某些特定領(lǐng)域博客圈的三個(gè)目標(biāo)，其中第一個(gè)目標(biāo)是收集某領(lǐng)域中盡可能多的博文，然后獲得一個(gè)比較有意義的方法以找出權(quán)威的說法，第三個(gè)目標(biāo)是用很長的一段時(shí)間來檢驗(yàn)我們的方法。

2.1.1 博客網(wǎng)絡(luò)挖掘中的算法

首先，我們定義個(gè)圖 G=（V，E），其中 V 為點(diǎn)集，E=（V×V）為有向邊集。對(duì)于一個(gè)給定的節(jié)點(diǎn)，indeg（v）函數(shù)返回了該點(diǎn)的入度，也就是進(jìn)入該點(diǎn)的邊數(shù)，succ（v）函數(shù)返回了該節(jié)點(diǎn)的后繼節(jié)點(diǎn)的集合，pre（v）返回該節(jié)點(diǎn)所有先驅(qū)節(jié)點(diǎn)的集合。然后我們假設(shè)一個(gè)抽象權(quán)威性函數(shù) auth以返回給定節(jié)點(diǎn)的正交化后的權(quán)威值。

這個(gè)函數(shù)中的一個(gè)重要性質(zhì)直接依賴于該節(jié)點(diǎn)的入度，如下定義：

所有比較熱門的博客查詢工具（如PageRank，HITS等）都遵循了這個(gè)假設(shè)，所以它們的搜索結(jié)果都可以使用我們的方法。使用的示例數(shù)據(jù)中集合了兩個(gè)不同的社會(huì)網(wǎng)絡(luò)，帶有引用鏈接的文章網(wǎng)絡(luò)和帶有博客鏈接的博客網(wǎng)絡(luò)定義如下：

使用網(wǎng)絡(luò)，我們能計(jì)算出來自這個(gè)網(wǎng)絡(luò)的權(quán)威值。我們定義為文章原始權(quán)威值，其派生于，然而觀察值表明文章和特定的領(lǐng)域很少有關(guān)聯(lián)，因此使用了一種更加精確的方法用于計(jì)算社會(huì)權(quán)威性。

對(duì)于博客的權(quán)威性，我們手動(dòng)做一個(gè)從文章鏈接到博客網(wǎng)絡(luò)的映射，或許這個(gè)函數(shù)就能對(duì)給定的文章找到其所在的博客。

2.2 犯罪調(diào)查中的社會(huì)網(wǎng)絡(luò)挖掘

隱藏在社會(huì)網(wǎng)絡(luò)數(shù)據(jù)背后的信息可以做為調(diào)查犯罪案件的重要資源，它可以幫助辦案人員找出整個(gè)犯罪團(tuán)伙，然而這么一個(gè)過程至今還沒有實(shí)現(xiàn)自動(dòng)化，提出了一個(gè)用于自動(dòng)分析網(wǎng)絡(luò)數(shù)據(jù)的框架，其中用到了大量的數(shù)據(jù)挖掘和統(tǒng)計(jì)學(xué)的方法，這個(gè)方法讓警署建立和部署P2P系統(tǒng)以找到犯罪者之間的關(guān)系并鑒別出可疑對(duì)象。

2.2.1 犯罪網(wǎng)絡(luò)挖掘中的算法

由于犯罪調(diào)查的問題具有分布較廣的特性（即在多重網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)挖掘），請(qǐng)需要通過并行計(jì)算以加快計(jì)算速度，中使用了多代理架構(gòu)，這個(gè)架構(gòu)中包含四個(gè)不同種代理：

（1）聯(lián)系規(guī)則挖掘機(jī)代理（ARMA）：ARMAs用于發(fā)現(xiàn)有用的規(guī)則并將它們轉(zhuǎn)換為第一個(gè)邏輯順序（FOL），以存入本地IA知識(shí)庫中，本地IA就是該架構(gòu)的本地ARM代理；

（2）中間代理（BA）：它將從用戶中派生查詢給推理代理，查詢以事實(shí)的形式存在IA知識(shí)庫中；

（3）推理代理（IA）：它使用基于ARMAs、BA搜集來的規(guī)則FOL，進(jìn)行推理，并將結(jié)果傳給響應(yīng)代理；

（4）響應(yīng)代理（RA）：它用于顯示通過收集IAs得出的結(jié)果，將它們和Dempster-Shafer方法結(jié)合，并將它們在屏幕上打印出來，且以相關(guān)性權(quán)重降序排列。

3 總結(jié)

社會(huì)網(wǎng)絡(luò)是近年數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)，本文對(duì)社會(huì)網(wǎng)絡(luò)的概念及特征進(jìn)行了描述，結(jié)合外文文獻(xiàn)，對(duì)博客圈挖掘、犯罪調(diào)查挖掘進(jìn)行了重點(diǎn)的研究。

數(shù)據(jù)挖掘作為一種幫助人們從大量數(shù)據(jù)中發(fā)現(xiàn)有用知識(shí)的工具，在處理社會(huì)網(wǎng)絡(luò)問題方面已經(jīng)有了較為廣泛的應(yīng)用。用計(jì)算機(jī)計(jì)算代替?zhèn)鹘y(tǒng)人工勞動(dòng)，是計(jì)算機(jī)專業(yè)人員的一大夢想，作為有很大實(shí)際應(yīng)用價(jià)值的社會(huì)網(wǎng)絡(luò)挖掘?qū)⒃谖磥砩鐣?huì)生活中扮演十分重要的角色。

[1]Darko Obradovicm，Stephan Baumann，Andreas Dengel.A Social Network Analysis and Mining Methodology for the Monitoring of Specific Domains in the Blogosphere.2010 International Conference on Advances in Social Networks Analysis and Mining.2010.

[2]Shen Bin，Liu Yuan，Wang Xiaoyi.Research on Data Mining Models for the Internet of Things.2010 International Conference on Page Help Image Analysis and Signal Processing（IASP），2010 ：127-132.

[3]Amin Milani Fard，Martin Ester.Collaborative Mining in Multiple Social Networks Data for Criminal Group Discovery.2009 International Conference on Computational Science and Engineering.2009：582-587.