社會網絡挖掘的應用

錢萬良 高 燕

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

0 引言

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

社會網絡（Social Network）作為數據挖掘的子領域，在近年有著飛速的發展，它也是目前數據挖掘中與社會生活聯系的最緊密的熱點研究方向之一。社會網絡發現領域的研究廣泛應用在疾病的傳播、科學家的合作、文獻引用和恐怖分子網絡等方面。社會網絡是由圖表示的異構多關系的數據集。這種圖一般都很大，節點對應對象，邊對應表示對象間聯系或相互作用的鏈接。節點和鏈接都有屬性，對象可以具有類標號，鏈接可以是單向的并且不必是二元的。在實際應用中，有許多科技、商業、經濟等方面的社會網絡實力，比如消費網絡、電力網絡、計算機病毒傳播、聊天室、朋友聯系等，總之社會網絡問題在現實生活中有著廣泛的應用。

我之所以選擇社會網絡發現問題作為我研究的數據挖掘子領域，就是因為我覺得這個子領域與社會的密切聯系，任何一個學術界的研究成果，如果最終沒有投入到社會生產中，使之轉換為價值，那這個研究成果的成色將被打上一定的折扣。

社會網絡的分支有很多種，科研人員在不同領域進行研究，研究了博客圈中作者與博文內容的聯系，使用數據挖掘模型去解決物聯網的問題，還有通過數據挖掘手段從事犯罪調查的。

1 社會網絡發現的研究狀況

1.1 研究發展簡史

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

從社會關系存在的形態劃分，社會關系可以分為靜態關系和動態關系。前者指社會關系的構成模式，又稱社會結構，后者指社會關系的相互作用模式，又稱社會互動。

1.2 相關概念

社會網絡指的是社會行動者及其間的關系的集合。一個社會網絡是有多個點（社會行動者）和各點之間的連線（行動者之間的關系）組成的集合。用點和線來表達網絡，這是社會網絡的可視化界定。社會網絡強調每個行動者都與其它行動者有或多或少的關系。社會網絡分析方法關注如何建立這些關系的模型，力圖描述群體關系的結構，研究這種結構對群體功能或者群體內部個體的影響。社會網絡分析被用來建立社會關系的模型，發現群體內行動者之間的社會關系，描述社會關系的結構，研究這種結構對群體功能或者群體內部個體的影響。

社會網絡在圖論中可以表示為，其中節點集V和邊集E固定不變的社會網絡稱為靜態社會網絡，節點集V和邊集E會隨著時間的變化而變化的社會網絡稱為動態社會網絡。

圖1 社會網絡示例圖

1.3 相關工作及算法

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

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

2 數據挖掘技術在社會網絡發現中的應用

2.1 博客圈中的社會網絡挖掘

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

2.1.1 博客網絡挖掘中的算法

首先，我們定義個圖 G=（V，E），其中 V 為點集，E=（V×V）為有向邊集。對于一個給定的節點，indeg（v）函數返回了該點的入度，也就是進入該點的邊數，succ（v）函數返回了該節點的后繼節點的集合，pre（v）返回該節點所有先驅節點的集合。然后我們假設一個抽象權威性函數 auth以返回給定節點的正交化后的權威值。

這個函數中的一個重要性質直接依賴于該節點的入度，如下定義：

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

使用網絡，我們能計算出來自這個網絡的權威值。我們定義為文章原始權威值，其派生于，然而觀察值表明文章和特定的領域很少有關聯，因此使用了一種更加精確的方法用于計算社會權威性。

對于博客的權威性，我們手動做一個從文章鏈接到博客網絡的映射，或許這個函數就能對給定的文章找到其所在的博客。

2.2 犯罪調查中的社會網絡挖掘

隱藏在社會網絡數據背后的信息可以做為調查犯罪案件的重要資源，它可以幫助辦案人員找出整個犯罪團伙，然而這么一個過程至今還沒有實現自動化，提出了一個用于自動分析網絡數據的框架，其中用到了大量的數據挖掘和統計學的方法，這個方法讓警署建立和部署P2P系統以找到犯罪者之間的關系并鑒別出可疑對象。

2.2.1 犯罪網絡挖掘中的算法

由于犯罪調查的問題具有分布較廣的特性（即在多重網絡中進行數據挖掘），請需要通過并行計算以加快計算速度，中使用了多代理架構，這個架構中包含四個不同種代理：

（1）聯系規則挖掘機代理（ARMA）：ARMAs用于發現有用的規則并將它們轉換為第一個邏輯順序（FOL），以存入本地IA知識庫中，本地IA就是該架構的本地ARM代理；

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

（3）推理代理（IA）：它使用基于ARMAs、BA搜集來的規則FOL，進行推理，并將結果傳給響應代理；

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

3 總結

社會網絡是近年數據挖掘領域的研究熱點，本文對社會網絡的概念及特征進行了描述，結合外文文獻，對博客圈挖掘、犯罪調查挖掘進行了重點的研究。

數據挖掘作為一種幫助人們從大量數據中發現有用知識的工具，在處理社會網絡問題方面已經有了較為廣泛的應用。用計算機計算代替傳統人工勞動，是計算機專業人員的一大夢想，作為有很大實際應用價值的社會網絡挖掘將在未來社會生活中扮演十分重要的角色。

[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.