单图及群图挖掘：原理、算法与应用 pdf下载

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

Danai Koutra是密歇根大学安娜堡分校计算机科学与工程系的助理教授。她的研究兴趣包括大规模图挖掘、图相似性计算和匹配、图概要抽取和异常检测。Danai 的研究主要应用于社交网络、合作网络、Web 网络以及大脑连接网络。她现持有1项:“rate-1”专利，并拥有6项(待定)二分图对齐专利。Danai 曾荣获2016年ACM SIGKDD博士论文奖，并荣获SCS博士论文奖( CMU)。她在数据挖掘会议上发表了多篇论文，其中包括两篇获奖论文。她现在共开展3门课程，曾在IBM Watson、Microsoft Research 和Technicolor工作。她于2010年在雅典国立技术大学电子与计算机工程学院获得学士学位，于2015年在卡耐基·梅隆大学计算机科学学院获取博士学位和理学硕士学位。

Christos Faloutsos 是卡耐基.梅隆大学的教授。他曾于1989年获得美国国家科学基金会颁发的总统青年研究员奖，于2006年荣获ICDM研究贡献奖，并于2010年荣获SIGKDD创新奖，曾获得24项论文奖( 包括5项时间考验奖)和4项教学奖。他指导的6位学生荣获了KDD或SCS论文奖。同时他也是ACM Fellow, 并曾担任SIGKDD执行委员会成员。他共发表同行评议文章350多篇，参与撰写17本书中的部分章节，出版专著2本。他共拥有7项专利(及2项待定专利)。他已经开展40门课程和20多个特邀讲座。他的研究兴趣包括针对图和时间序列的大规模数据挖掘、异常检测、张量分解和分形。

译者序
原书前言
原书致谢
作者简介

第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

前言

图是信息表达的载体，从网页之间的连接到电子邮件网络中的通信关系，再到大脑神经元之间的连接都可以用图表示。这些图通常具有数十亿个节点及它们之间的交互关系。在这些相互关联的数据中，如何找到最重要的结构并对其进行归纳总结？如何更有效地将它们可视化？如何检测预示着重大事件的异常情况（例如对计算机系统的一次攻击、人脑中疾病的形成或公司的衰落）？本书将呈现一类可扩展、具有理论基础的发现算法，它将全局和局部信息结合起来，以帮助人们理解一个或多个图。除给出高效的系统性方法论，本书还针对两个主要方向提供图理论的思想和模型及现实世界中的实际应用：

单图挖掘（Individual Graph Mining）：本部分主要展示如何通过识别图的重要结构，可解释性地抽取单个图的概要信息。除了通过概要信息对图加以解释，本部分还进一步使用推理技术，即利用少数实体（通过概要信息抽取技术或其他方法获得）及其网络结构快速、有效地学习未知实体信息。

群图挖掘（Collective Graph Mining）：本部分将单图概要信息抽取的概念推广到时序演化图中，并展示了如何发现其中的时序模式。除抽取概要信息，度量两个图的相似性在很多应用中都是需要解决的前置性问题（例如时序异常检测、行为模式发现等）。

此外，本部分还提出了一系列可扩展、具有理论背景的算法，以实现多个图之间的对齐和相似性度量。本书呈现的方法利用了来自不同领域的技术，如矩阵代数、图论、最优化、信息论、机器学习、金融和社会科学，来解决现实世界的问题。本书把提出的探索性算法应用到海量数据集中，其中包括具有66亿条边的互联网图、具有18亿条边的Twitter图、多达9千万条边的脑连接图，以及合作网络、点对点网络、浏览日志网络等，它们都包含数百万用户和他们之间的交互关系。

译者序

现实中很多系统都可以描述为一个复杂的网络结构图，无向的或有向的，无权的或含权 的，甚至是时变的。图挖掘已有很多相关的研究，包括社团结构检测、高影响力节点挖掘、 链路预测、图上的信息传播动力学等。对于一个超大规模的图，如何快速、准确地获取其蕴 含的重要结构，以及反映图中主体框架的图概要信息是图挖掘领域中的一个重要研究方向。两位教授在这方面做了大量开创性工作。

本书共包含两个部分：第一部分介绍了单图上的概要表示以及节点标签分类算法；第二 部分介绍了群图上的概要表示以及群图的相似性度量和节点对齐算法。此外，在绪论中，还 介绍了图挖掘相关的基本概念，这也是理解本书后续内容的预备知识。 本书研究问题的角度比较新颖，首次系统、清晰地整理了单图和群图上的研究问题及解 决思路，包括如何抽取大规模图和时序图的基本概要来加以可视化，如何基于先验知识对单 图中的节点进行类别推理，以及如何对不同图的节点进行对齐并计算图之间的相似性。这些 研究问题都对应于非常热门的应用场景，部分场景可以直接从本书找到答案，例如大规模图 的可视化以及节点标签的分类等，也有一部分应用场景可以从本书的算法思路中得到启发并 迁移到适用的研究场景中，如不同语言之间的互译等。此外，书中对相关算法的设计技巧、 理论基础和推导过程介绍得比较详细，适合读者理解和重现。除介绍具体的研究问题和算 法，本书更大的意义在于给读者带来了图挖掘领域新的研究方向和思考视角。

本书最初受机械工业出版社顾谦编辑邀请，周涛教授负责本书的中文翻译。在探讨翻译 事项时，周涛教授带领的图挖掘研究小组成员对本书的内容表示了极大兴趣，并希望通过参 与翻译过程对本书介绍的相关内容加深理解。译稿主要由图挖掘研究小组中的陈端兵副教 授、李艳丽博士和谢文波博士完成，其中陈端兵副教授负责翻译第 １章、第 ２章和第 ７章， 谢文波博士负责翻译第 ３章、第 ４章，李艳丽博士负责翻译第 ５章、第 ６章及其他部分， 周涛教授对全书进行了非常细致的指导和修改，并参与部分内容的翻译，罗咏稢博士对全书 的审校付出了巨大的努力。此外，全部译者也针对每一章进行了交叉检验和校对。 整体上，译文尽可能和原书保持结构和表达风格的一致性，但为了符合中文表达习惯， 在保持原文语义的情况下，在理解原文并查阅相关文献的基础上，对部分原文内容进行了意 译。在本书的翻译过程中，对部分内容进行了说明和解释，并对某些知识点进行了延伸和扩 展，同时对原书中的一些小的错误进行了注释。由于译者中大部分是图挖掘领域的新人，知 识体系尚不完整，在有限的时间内完成本书的翻译，很担心不能够完全准确无误地传达原书 的意思，疏漏和不准确之处在所难免，特别恳请感兴趣的读者有时间能够阅读原书，并对译 文中出现的纰漏予以指正。 介绍翻译过程中的一个插曲：最初，几位译者力争的目标是忠实于原书。初稿提交后， 周涛教授并不满意，他对我们的要求是要用批判的眼光审视原书逻辑，从而对读者负责。于 是我们重新返稿，花费大量时间推导公式，反复研读原书，这个过程是痛苦的，但也是对科 研建立敬畏心的过程。非常感谢周涛教授的严谨，也很感谢翻译团队的伙伴们在承担其他科研重任的同时，花费精力提升译稿质量。同时也要感谢顾谦编辑和为译稿提出详细修改意见 的各位编辑们，没有你们的帮助，本译稿难以完成。最后，希望各位图挖掘爱好者能从本书 中获取有用的信息，希望本书能够为大家现有的研究方向提供帮助，同时也能为从业者解决 实际应用问题提供解决思路。

译者