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