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

1、社會網(wǎng)絡(luò)發(fā)現(xiàn)綜述肖韜1(南京大學(xué)計算機(jī)科學(xué)與技術(shù)系,南京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)絡(luò)發(fā)現(xiàn)是數(shù)據(jù)挖掘?qū)W科的一個子領(lǐng)域,致力于從數(shù)據(jù)中找出對象與對象之間的關(guān)系。與傳統(tǒng)的數(shù)據(jù)挖掘任務(wù)不同,社會網(wǎng)絡(luò)發(fā)現(xiàn)任務(wù)中的數(shù)據(jù)不滿足獨立同分布的假設(shè)。本文介紹了社會網(wǎng)絡(luò)發(fā)現(xiàn)的概念、數(shù)據(jù)特征、基本方法與實際應(yīng)用,并對鏈接挖掘的概念、理論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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