单图及群图挖掘 原理、算法与应用

本书由DanaiKoutra和全球知名的数据挖掘领域奠基人之一ChristosFaloutsos教授合著，介绍了图挖掘领域一个崭新的研究方向。全书内容主要包括两个部分：第壹部分介绍了单图上的概要表示以及节点标签分类算法；第二部分介绍了群图上的概要表示以及群图的相似性度量和节点对齐算法。

 

译者序
原书前言
原书致谢
作者简介
第1章绪论1
1.1概述1
1.2本书的架构1
1.2.1第一部分：单图挖掘1
1.2.2第二部分：群图挖掘2
1.2.3源代码和支撑材料3
1.3预备知识3
1.3.1图的基本定义4
1.3.2图的数据结构5
1.3.3线性代数基本概念6
1.3.4图的主要特性7
1.4常用符号8
第一部分单图挖掘
第2章静态图概要抽取11
2.1概述与动机12
2.2问题描述13
2.2.1图概要抽取的MDL准则14
2.2.2模型编码15
2.2.3误差编码17
2.3VoG：基于词汇表的图概要抽取17
2.3.1子图生成18
2.3.2子图标记18
2.3.3概要组装19
2.3.4示例20
2.3.5计算复杂度20
2.4实证结果21
2.4.1定量分析22
2.4.2定性分析25
2.4.3可扩展性30
2.5讨论31
2.6相关工作33
第3章图的推理35
3.1关联推断技术35
3.1.1RWR36
3.1.2SSL36
3.1.3BP37
3.1.4本节小结38
3.2FABP39
3.2.1推导41
3.2.2收敛性分析45
3.2.3算法46
3.3扩展到多个类47
3.4实证结果49
3.4.1准确度49
3.4.2收敛性50
3.4.3鲁棒性51
3.4.4可扩展性51
第二部分群图挖掘
第4章动态图概要抽取55
4.1问题描述56
4.1.1动态图概要抽取的MDL准则58
4.1.2编码模型58
4.1.3误差编码60
4.2TIMECRUNCH：基于词汇表的动态图概要抽取61
4.2.1生成候选静态结构61
4.2.2标注候选静态结构61
4.2.3组装候选时序结构62
4.2.4概要合成63
4.3实证结果64
4.3.1定量分析65
4.3.2定性分析66
4.3.3可扩展性68
4.4相关工作68
第5章图的相似性70
5.1直觉71
5.1.1概述71
5.1.2节点亲和度测量71
5.1.3信念传播的应用72
5.1.4相似性度量的预期性质73
5.2DELTACON：“δ”连通性动态检测73
5.2.1算法描述74
5.2.2快速计算74
5.2.3预期性质77
5.3DELTACON-ATTR：节点和边的归因82
5.3.1算法描述82
5.3.2可扩展性84
5.4实证结果84
5.4.1DELTACON与直觉的一致性84
5.4.2DELTACON-ATTR与直觉的一致性90
5.4.3可扩展性94
5.4.4鲁棒性94
5.5应用96
5.5.1Enron数据集实证分析97
5.5.2大脑连通图聚类98
5.5.3恢复连接组的对应关系99
5.6相关工作101
第6章图的对齐104
6.1问题的形式化描述105
6.2BIG-ALIGN：二分图的对齐106
6.2.1数学形式化表示106
6.2.2具体问题的优化108
6.2.3算法描述112
6.3UNI-ALIGN：二分图对齐算法在单分图上的推广113
6.4实证结果114
6.4.1BIG-ALIGN的准确度和运行时间115
6.4.2UNI-ALIGN的准确度和运行时间118
6.5讨论119
6.6相关工作119
第7章结论与进一步的研究问题121
参考文献123