社會網(wǎng)絡發(fā)現(xiàn)綜述 (肖韜,南京大學計算機系,數(shù)據(jù)挖掘大作業(yè))_圖文

1、社會網(wǎng)絡發(fā)現(xiàn)綜述肖韜1(南京大學計算機科學與技術系,南京210093Comprehensive Introduction to Social Network DiscoveryXiaoTao1(Department of Computer Science and Technology, Nanjing University, Nanjing 210093, ChinaAbstract: As a subdomain of data mining discipline, social network discovery concentrates on finding relationship a

2、mong objects. In contrast to traditional data mining tasks, data in social network discovery tasks do not satisfy the assumption that they are independent, identically distributed. This paper introduces the concept of social network discovery, the feature of concerned data, basic methods and applica

3、tions as well as the concept of link mining and its theoretical background and classical tasks.Keywords: data mining; social network discovery; graph; relationship; link mining摘 要: 社會網(wǎng)絡發(fā)現(xiàn)是數(shù)據(jù)挖掘學科的一個子領域,致力于從數(shù)據(jù)中找出對象與對象之間的關系。與傳統(tǒng)的數(shù)據(jù)挖掘任務不同,社會網(wǎng)絡發(fā)現(xiàn)任務中的數(shù)據(jù)不滿足獨立同分布的假設。本文介紹了社會網(wǎng)絡發(fā)現(xiàn)的概念、數(shù)據(jù)特征、基本方法與實際應用,并對鏈接挖掘的概念、理論

4、背景及幾種常見的任務做了簡要闡述。關鍵詞: 數(shù)據(jù)挖掘;社會網(wǎng)絡發(fā)現(xiàn);圖;關系;鏈接挖掘1 數(shù)據(jù)挖掘學科概述在計算機被發(fā)明之前的時代,人類存儲信息的主要載體是紙張。雖然全世界的圖書(以及報紙等各種類型的紙張很多,但是以今天的眼光來看,當時的信息量并不算多。自從計算機被發(fā)明以來,記錄信息的方式發(fā)生了根本性的變化:計算機所獨有的數(shù)據(jù)存儲、輸入、生成、交換功能,使得人類可以以前所未有的低成本和高速度來存儲、生成、使用和傳遞大量的信息,幾乎可以說人類進入了信息時代。但是真正帶來信息爆炸效應的是Internet的普及。隨著目前Internet的無孔不入,在互聯(lián)網(wǎng)上每天都有海量的信息在生成和傳遞,并且這些海

5、量數(shù)據(jù)每天還在以越來越快的速度增長,這些數(shù)據(jù)在目前的技術條件下已經(jīng)不可能全部地進行實時處理(當然對于我們所需的部分數(shù)據(jù)是可以進行有效分析的,并且將來處理的難度和強度將越來越大,以至于人們處理數(shù)據(jù)的速度將跟不上數(shù)據(jù)產(chǎn)生的速度,這就是人們驚呼的“信息爆炸”時代的到來。面對如此海量的數(shù)據(jù),人們發(fā)現(xiàn)已有的數(shù)據(jù)處理和提煉的工具是多么地匱乏,我們迫切需要新的、更加有效的工具來從這海量的數(shù)據(jù)中“挖掘”出對我們有價值的信息,這就是數(shù)據(jù)挖掘這門學科最根本的目的所在。按照J. W. Han和Micheline Kamber的定義,數(shù)據(jù)挖掘是從巨量數(shù)據(jù)中發(fā)現(xiàn)有效的、新穎的、潛在有用的并且最終可理解的模式的非平凡過程

6、3。經(jīng)過幾十年的研究和發(fā)展,數(shù)據(jù)挖掘學科已經(jīng)在社會經(jīng)濟的各個方面得到了普遍的應用,其從海量數(shù)據(jù)中挖掘出極具價值的信息的例子也是數(shù)不勝數(shù),例如沃爾瑪超市中“啤酒和尿布”的例子就是一個典型:經(jīng)過對貨物的銷售記錄數(shù)據(jù)進行分析,沃爾瑪發(fā)現(xiàn)很多購買尿布的人同時也購買了啤酒,故而沃爾瑪有意將尿布與啤酒的貨架放在一起,大大提高了這二者的銷量。*作者簡介:肖韜(生于1985年,男,江蘇省南京市人,碩士研究生在讀,主要研究領域為計算機體系結構與并行計算。經(jīng)過數(shù)十年的研究與發(fā)展,數(shù)據(jù)挖掘技術已經(jīng)在很多的方面取得了成功,同時,數(shù)據(jù)挖掘技術也呈現(xiàn)出更加細化和專業(yè)化的發(fā)展趨勢:向著各個子領域深入地發(fā)展。例如,在多媒體領

7、域的數(shù)據(jù)挖掘、在醫(yī)療領域的數(shù)據(jù)挖掘以及在消費市場領域的數(shù)據(jù)挖掘等等。本文將對數(shù)據(jù)挖掘技術在社會網(wǎng)絡發(fā)現(xiàn)這一子領域展開介紹與論述。2 社會網(wǎng)絡發(fā)現(xiàn)的概念與研究意義2.1 社會網(wǎng)絡與社會網(wǎng)絡分析人類是群居動物,從遠古時代起,人類就在一起共同耕種、狩獵、勞作,從而形成了社會。社會發(fā)展到現(xiàn)在,每一個人都不可避免地與其他一些人發(fā)生著聯(lián)系,如工作、學習、交友等。這樣,社會中各個成員中就形成了某種穩(wěn)定的關系,進而構成了社會網(wǎng)絡,就如Mickenberg和Dugan在1995年所說的那樣,“We all connect, like a net we cannot see”6。維基百科對社會網(wǎng)絡給出了如下的定義

8、:社會網(wǎng)絡是一個社會結構,該結構由被稱為節(jié)點的個體(或者組織構成,各個節(jié)點之間由一種或者多種特定類型的相互依賴性(如友誼、親屬關系、共同愛好、金融交易、兩性關系、信仰、知識或者威望連接起來1。在20世紀30年代,Jacob L. Moreno和哈佛大學的一組研究人員分別提出社會網(wǎng)絡模型這個概念,想借此來研究和分析社會學中的一些現(xiàn)象和問題。而社會網(wǎng)絡分析,則是指對那些連接社會網(wǎng)絡中的個體的結構模型進行研究。在大部分情況下,社會網(wǎng)絡分析致力于找出兩種模型:(1能夠揭示屬于同一個特定群體的個體的模型;(2能夠揭示那些處在同一社會地位或者扮演相同社會角色的個體的模型5。2.2 對社會網(wǎng)絡發(fā)現(xiàn)這一領域進

9、行研究和分析的意義現(xiàn)代社會中的人不可能是獨居的人,而必定是時刻都在與他人發(fā)生著各種各樣的聯(lián)系,他們幾乎所有的活動也都是建立在這種種聯(lián)系的基礎之上的。通過研究社會網(wǎng)絡中人們之間的聯(lián)系,我們可以從中發(fā)掘出大量的極具價值的信息。例如,可以尋找出具有某些相同特征的人,如共同的愛好、相似的工作等等;通過對已知患者群的社會網(wǎng)絡關系進行發(fā)掘,可以預測出這些患者群所患疾病的傳播趨勢;在已知對某項業(yè)務有需求的初始人群時,通過社會網(wǎng)絡發(fā)現(xiàn)與分析找出與該初始人群有密切聯(lián)系或者共同活動特征的其他關鍵人群,可以有效地對該關鍵人群展開業(yè)務推廣,從而產(chǎn)生口碑效應,提高業(yè)務推廣的成功率與效率?？梢?對社會網(wǎng)絡發(fā)現(xiàn)進行研究和分

10、析在當今的信息化社會中具有重大的現(xiàn)實應用意義。3 社會網(wǎng)絡發(fā)現(xiàn)的研究歷史及進展美籍奧地利人Jacob L. Moreno是最早提出社會網(wǎng)絡分析這一學科概念并對其開展研究工作的學者之一4。他認為,這一學科是通過對連接各個對象的網(wǎng)絡的分析,對個體在某個群體或者社區(qū)中的角色進行定量的評價。而社會網(wǎng)絡發(fā)現(xiàn),則是指利用已有的數(shù)據(jù)來發(fā)現(xiàn)對象與對象之間的關系,這樣這些對象以及發(fā)現(xiàn)的關系則構成了社會網(wǎng)絡?？梢?社會網(wǎng)絡分析與社會網(wǎng)絡發(fā)現(xiàn)是數(shù)據(jù)挖掘中兩個相互有關聯(lián)的子領域:社會網(wǎng)絡分析技術可以用于發(fā)現(xiàn)潛在的社會網(wǎng)絡,而社會網(wǎng)絡發(fā)現(xiàn)則是社會網(wǎng)絡分析預備步驟,亦可以看作是社會網(wǎng)絡分析的目標之一。目前,社會網(wǎng)絡發(fā)現(xiàn)在

11、現(xiàn)實生活中已經(jīng)取得了一定的應用。很多在線購物網(wǎng)站通過對消費者的瀏覽及消費記錄進行分析,確定該消費者與其他哪些消費者具有相似的購物傾向,并給出該消費者可能感興趣的其它商品的推薦。例如,在當當網(wǎng)上的搜索框內輸入關鍵字“數(shù)據(jù)挖掘”,該網(wǎng)站不僅會列出書名叫數(shù)據(jù)挖掘的書籍(圖1,還會根據(jù)其他瀏覽過該書的用戶的購買及瀏覽記錄,列出購買過和瀏覽過該書的其他讀著所購買和瀏覽的其他書籍(圖2和圖3。更有意義的是,通過對讀者的購買和瀏覽記錄這些數(shù)據(jù)進行分析,該網(wǎng)站能夠確定出一個社會網(wǎng)絡,該網(wǎng)絡由與該購書者具備相似購書需求或者興趣的個體組成。由此,網(wǎng)站進一步地預測了瀏覽過該書的其他個體還可能會購買哪些其他書籍(圖4

12、,以及與該購書者具有相似興趣的顧客關注的其他商品(圖5。 圖1 圖2 圖3 圖4 圖54 社會網(wǎng)絡中的數(shù)據(jù)、特征及表示方式4.1 社會網(wǎng)絡中的數(shù)據(jù)的特點在傳統(tǒng)的數(shù)據(jù)挖掘任務中,數(shù)據(jù)是孤立的記錄,每一條記錄可以由一個屬性向量表示,向量的每一維對應著一種條件屬性的取值,而這些屬性向量之間都是相互獨立的2。顯然,社會網(wǎng)絡中的數(shù)據(jù)不滿足以上這些假設:之所以把各個節(jié)點組成社會網(wǎng)絡,就是為了發(fā)現(xiàn)與研究這些個體之間的關系,如果一開始就認為這些個體(及其數(shù)據(jù)是相互獨立的,那么這項數(shù)據(jù)挖掘任務本身失去了意義。而在現(xiàn)實生活中,這也是顯然的。舉例來說,在研究甲型H1N1流感病毒傳染趨勢的模型中,如果僅僅考慮個體的自

13、身免疫系統(tǒng)狀況,只能得到一些簡單的分類依據(jù)。如果兩個人的免疫狀況差不多,則很難進一步地預測哪一個會感染甲型H1N1流感病毒。而如果將兩個人的生活圈子也考慮進來進行分析,則可以進行更加精確的預測。因為如果一個人的交際圈子中有人已經(jīng)感染了甲型H1N1流感病毒,那么這個人也感染甲型H1N1流感病毒的概率顯然要更高。可見,在社會網(wǎng)絡中數(shù)據(jù)中最有價值的部分就是其中蘊藏著的個體之間的聯(lián)系信息,在社會網(wǎng)絡中進行數(shù)據(jù)挖掘,個體之間已經(jīng)不再是獨立的了。所以如果想利用依賴性(dependencies來改善預測結果的話,就必須充分地考慮個體之間的關系,以建立更加準確的模型。4.2 社會網(wǎng)絡中數(shù)據(jù)的表示方式任何數(shù)據(jù)都

14、有其表示方式,而社會網(wǎng)絡分析需要強有力的數(shù)學工具作支撐,如概率論、數(shù)理統(tǒng)計和圖論等,這樣,數(shù)據(jù)以怎樣的形式來表示就顯得尤為重要。合理的數(shù)據(jù)表示方式,可以使得對社會網(wǎng)絡的分析更加地方便和高效,也有利于分析結果的可視化。Freeman在文6中提出,現(xiàn)代的社會網(wǎng)絡分析必須具備以下四個特征:1社會網(wǎng)絡分析是以基于社會活動者(social actor之間關系的結構直覺(structure intuition為動機的;2基于系統(tǒng)的實驗數(shù)據(jù)(systematic empirical data;3充分利用圖的表示形式(graphic imagery;4依賴于數(shù)學及/或計算模型的使用。這四點對現(xiàn)代的社會網(wǎng)絡分析

15、任務作了特征描述,其中的第三點指出了圖是社會網(wǎng)絡中的數(shù)據(jù)的最基本表示方式。而在大量的研究項目里,也的確是把圖論作為最基本的分析工具,這一點非常易于理解:既然社會網(wǎng)絡由被稱為節(jié)點的個體(或者組織構成,且各個節(jié)點之間由一種或者多種特定類型的相互依賴關系連接起來,那么很自然地想到使用圖論中的圖這一概念來進行數(shù)據(jù)的表示,即將各個個體看做圖中的頂點,而在兩個個體之間存在的聯(lián)系則看做是兩頂點之間的邊。在文6中,Freeman還提出了在社會網(wǎng)絡發(fā)現(xiàn)及分析中的幾個處于中心地位的概念,并對其做了定義:1活動者(Actor:社會網(wǎng)絡中的實體,可以是單個個體或者是團體、社會單元,如群體中的人、公司中的部門、城市中的

16、公共服務機構或者世界范圍內的國家。2聯(lián)系(Relational Tie:社會網(wǎng)絡中的各個活動者之間通過聯(lián)系連接在一起,其范圍和種類十分地寬泛,但是最顯著的特征是其能夠在一對活動者之間建立鏈接。3二元組(Dyad:由一對活動者及他們之間可能的聯(lián)系構成。二元組分析注重一對活動者之間聯(lián)系的屬性,如聯(lián)系是否是雙向作用的(reciprocated及某幾種特定類型的聯(lián)系是否會同時存在。二元組常常是對社會網(wǎng)絡進行統(tǒng)計分析的基本單元。4三元組(Triad:由三個活動者及他們之間可能的聯(lián)系構成,為許多重要的社會網(wǎng)絡方法及模型所關注。平衡理論(Balance Theory提出和激發(fā)了許多三元組分析相關的問題,其中

17、特別有意義的是三元組是否是可傳遞的(transitive及平衡的(balanced。5子群(Subgroup:由所有活動者的任意大小的子集(subset及他們之間的聯(lián)系構成。使用特定的標準來定位和研究子圖已經(jīng)成為社會網(wǎng)絡分析中重要的關注點。6群體(Group:從社會學家的角度出發(fā)有很寬泛的定義,在社會網(wǎng)絡領域中定義為一群活動者及其中的聯(lián)系。5 社會網(wǎng)絡發(fā)現(xiàn)任務及其理論基礎在J. W. Han的書中,數(shù)據(jù)挖掘任務通?？梢员粍澐譃閮纱箢?描述型(descriptive任務和預測型(predictive任務。描述型數(shù)據(jù)挖掘任務側重于對已有的樣本數(shù)據(jù)的整體特征進行刻畫和歸納,而預測型數(shù)據(jù)挖掘任務則側重

18、于根據(jù)從已有數(shù)據(jù)樣本中得到的已知規(guī)律,預測在未來或者新的情況下將會產(chǎn)生哪些變化。作為數(shù)據(jù)挖掘的子領域,社會網(wǎng)絡發(fā)現(xiàn)兼具描述型和預測型數(shù)據(jù)挖掘任務的特征,即側重于從已有的樣本數(shù)據(jù)中發(fā)現(xiàn)潛在的關系網(wǎng)絡。經(jīng)過這幾十年的研究,已經(jīng)有了若干理論與方法來進行關于社會網(wǎng)絡的數(shù)據(jù)挖掘任務,如常見的有基于相似度度量的方法、基于統(tǒng)計的方法、基于ILP的方法、基于頻繁模式挖掘的方法、基于圖性質的方法等9。本節(jié)將介紹由L. Getoor和C. P. Diehl在其一篇論文中提出的鏈接挖掘的概念及其相關理論基礎8。5.1 鏈接挖掘理論在社會網(wǎng)絡中,個體之間的關系被看作勢一種特定的鏈接(link,這些鏈接通常展現(xiàn)出若干種

19、能夠代表數(shù)據(jù)實例屬性(如重要性、排名和范疇等的模型。當然,在很多情況下,并不是所有的鏈接都是顯而易見的,所以我們也許對預測兩個個體之間是否存在鏈接感興趣。在一些其他領域,個體之間的鏈接可能會隨著時間而發(fā)生變化,這時我們的目標可能就是預測某個已經(jīng)觀察到的鏈接在將來是否依然會存在。將鏈接考慮進來,會產(chǎn)生一些更加復雜的模型,這在我們聚焦于發(fā)現(xiàn)子結構(substructure時會產(chǎn)生一些更大的挑戰(zhàn),如群組和共同子圖(common subgraphs等。相比較于主要關注數(shù)據(jù)實例的傳統(tǒng)數(shù)據(jù)挖掘任務,鏈接挖掘更加注重對鏈接(關系的挖掘與分析,且在很多時候是整個挖掘任務的最重要目標。5.2 鏈接挖掘的研究和發(fā)

20、展歷史鏈接挖掘(link mining是一個新興的研究領域,處于鏈接分析(link analysis、超文本和頁面挖掘(hypertext and web mining、關系學習(relational learning、歸納邏輯編程(inductive logic programming和圖挖掘(graph mining等研究工作的交叉地帶。近年來,已經(jīng)有一系列的研討會對鏈接挖掘相關的課題展開了討論,其中最早的是國際人工智能協(xié)會(AAAI在1998年召開的人工智能及鏈接分析秋季研討會,其他的還包括在關于統(tǒng)計關系學習(Statistical Relational Learning、多關系數(shù)據(jù)挖掘(Multi-Relational Data Mining、LinkKDD、鏈接分析(Link Analysis、反恐及安全(Counter-Terrorism and Security以及圖、樹、序列挖掘(Mining Graphs, Trees and Sequences等方面展開的研討會8。5.3 幾種常見的鏈接挖掘任務鏈接挖掘所涉及到的數(shù)據(jù)挖掘技術在建立關于被鏈接的個體的描述型或者預測型模型時會重點考慮那些鏈接,文8提出了五種典型的鏈接挖掘任