《單圖及群圖挖掘:原理、算法與應(yīng)用》由DanaiKoutra和全球知名的數(shù)據(jù)挖掘領(lǐng)域奠基人之一ChristosFaloutsos教授合著,介紹了圖挖掘領(lǐng)域一個(gè)嶄新的研究方向。《單圖及群圖挖掘:原理、算法與應(yīng)用》內(nèi)容主要包括兩個(gè)部分:第壹部分介紹了單圖上的概要表示以及節(jié)點(diǎn)標(biāo)簽分類算法;第二部分介紹了群圖上的概要表示以及群圖的相似性度量和節(jié)點(diǎn)對(duì)齊算法。
圖是信息表達(dá)的載體,從網(wǎng)頁(yè)之間的連接到電子郵件網(wǎng)絡(luò)中的通信關(guān)系,再到大腦神經(jīng)元之間的連接都可以用圖表示。這些圖通常具有數(shù)十億個(gè)節(jié)點(diǎn)及它們之間的交互關(guān)系。在這些相互關(guān)聯(lián)的數(shù)據(jù)中,如何找到最重要的結(jié)構(gòu)并對(duì)其進(jìn)行歸納總結(jié)?如何更有效地將它們可視化?如何檢測(cè)預(yù)示著重大事件的異常情況(例如對(duì)計(jì)算機(jī)系統(tǒng)的一次攻擊、人腦中疾病的形成或公司的衰落)?本書將呈現(xiàn)一類可擴(kuò)展、具有理論基礎(chǔ)的發(fā)現(xiàn)算法,它將全局和局部信息結(jié)合起來(lái),以幫助人們理解一個(gè)或多個(gè)圖。除給出高效的系統(tǒng)性方法論,本書還針對(duì)兩個(gè)主要方向提供圖理論的思想和模型及現(xiàn)實(shí)世界中的實(shí)際應(yīng)用: 單圖挖掘(Individual Graph Mining):本部分主要展示如何通過(guò)識(shí)別圖的重要結(jié)構(gòu),可解釋性地抽取單個(gè)圖的概要信息。除了通過(guò)概要信息對(duì)圖加以解釋,本部分還進(jìn)一步使用推理技術(shù),即利用少數(shù)實(shí)體(通過(guò)概要信息抽取技術(shù)或其他方法獲得)及其網(wǎng)絡(luò)結(jié)構(gòu)快速、有效地學(xué)習(xí)未知實(shí)體信息。 群圖挖掘(Collective Graph Mining):本部分將單圖概要信息抽取的概念推廣到時(shí)序演化圖中,并展示了如何發(fā)現(xiàn)其中的時(shí)序模式。除抽取概要信息,度量?jī)蓚(gè)圖的相似性在很多應(yīng)用中都是需要解決的前置性問(wèn)題(例如時(shí)序異常檢測(cè)、行為模式發(fā)現(xiàn)等)。此外,本部分還提出了一系列可擴(kuò)展、具有理論背景的算法,以實(shí)現(xiàn)多個(gè)圖之間的對(duì)齊和相似性度量。本書呈現(xiàn)的方法利用了來(lái)自不同領(lǐng)域的技術(shù),如矩陣代數(shù)、圖論、最優(yōu)化、信息論、機(jī)器學(xué)習(xí)、金融和社會(huì)科學(xué),來(lái)解決現(xiàn)實(shí)世界的問(wèn)題。本書把提出的探索性算法應(yīng)用到海量數(shù)據(jù)集中,其中包括具有66億條邊的互聯(lián)網(wǎng)圖、具有18億條邊的Twitter圖、多達(dá)9千萬(wàn)條邊的腦連接圖,以及合作網(wǎng)絡(luò)、點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)、瀏覽日志網(wǎng)絡(luò)等,它們都包含數(shù)百萬(wàn)用戶和他們之間的交互關(guān)系。關(guān)鍵詞數(shù)據(jù)挖掘圖挖掘及探索圖相似性圖匹配網(wǎng)絡(luò)對(duì)齊圖概要模式挖掘離群點(diǎn)檢測(cè)異常檢測(cè)可擴(kuò)展性快速算法模型可視化社交網(wǎng)絡(luò)腦連接網(wǎng)絡(luò)
譯者序
原書前言
原書致謝
作者簡(jiǎn)介
第1章緒論1
11概述1
12本書的架構(gòu)1
121第一部分:?jiǎn)螆D挖掘1
122第二部分:群圖挖掘2
123源代碼和支撐材料3
13預(yù)備知識(shí)3
131圖的基本定義4
132圖的數(shù)據(jù)結(jié)構(gòu)5
133線性代數(shù)基本概念6
134圖的主要特性7
14常用符號(hào)8
第一部分單圖挖掘
第2章靜態(tài)圖概要抽取11
21概述與動(dòng)機(jī)12
22問(wèn)題描述13
221圖概要抽取的MDL準(zhǔn)則14
222模型編碼15
223誤差編碼17
23VoG:基于詞匯表的圖概要抽取17
231子圖生成18
232子圖標(biāo)記18
233概要組裝19
234示例20
235計(jì)算復(fù)雜度20
24實(shí)證結(jié)果21
241定量分析22
242定性分析25
243可擴(kuò)展性30
25討論31
26相關(guān)工作33
目錄第3章圖的推理35
31關(guān)聯(lián)推斷技術(shù)35
311RWR36
312SSL36
313BP37
314本節(jié)小結(jié)38
32FABP39
321推導(dǎo)41
322收斂性分析45
323算法46
33擴(kuò)展到多個(gè)類47
34實(shí)證結(jié)果49
341準(zhǔn)確度49
342收斂性50
343魯棒性51
344可擴(kuò)展性51
第二部分群圖挖掘
第4章動(dòng)態(tài)圖概要抽取55
41問(wèn)題描述56
411動(dòng)態(tài)圖概要抽取的MDL準(zhǔn)則58
412編碼模型58
413誤差編碼60
42TIMECRUNCH:基于詞匯表的動(dòng)態(tài)圖概要抽取61
421生成候選靜態(tài)結(jié)構(gòu)61
422標(biāo)注候選靜態(tài)結(jié)構(gòu)61
423組裝候選時(shí)序結(jié)構(gòu)62
424概要合成63
43實(shí)證結(jié)果64
431定量分析65
432定性分析66
433可擴(kuò)展性68
44相關(guān)工作68
第5章圖的相似性70
51直覺(jué)71
511概述71
512節(jié)點(diǎn)親和度測(cè)量71
513信念傳播的應(yīng)用72
514相似性度量的預(yù)期性質(zhì)73
52DELTACON:連通性動(dòng)態(tài)檢測(cè)73
521算法描述74
522快速計(jì)算74
523預(yù)期性質(zhì)77
53DELTACON-ATTR:節(jié)點(diǎn)和邊的歸因82
531算法描述82
532可擴(kuò)展性84
54實(shí)證結(jié)果84
541DELTACON與直覺(jué)的一致性84
542DELTACON-ATTR與直覺(jué)的一致性90
543可擴(kuò)展性94
544魯棒性94
55應(yīng)用96
551Enron數(shù)據(jù)集實(shí)證分析97
552大腦連通圖聚類98
553恢復(fù)連接組的對(duì)應(yīng)關(guān)系99
56相關(guān)工作101
第6章圖的對(duì)齊104
61問(wèn)題的形式化描述105
62BIG-ALIGN:二分圖的對(duì)齊106
621數(shù)學(xué)形式化表示106
622具體問(wèn)題的優(yōu)化108
623算法描述112
63UNI-ALIGN:二分圖對(duì)齊算法在單分圖上的推廣113
64實(shí)證結(jié)果114
641BIG-ALIGN的準(zhǔn)確度和運(yùn)行時(shí)間115
642UNI-ALIGN的準(zhǔn)確度和運(yùn)行時(shí)間118
65討論119
66相關(guān)工作119
第7章結(jié)論與進(jìn)一步的研究問(wèn)題121
參考文獻(xiàn)123