图算法 Apache Spark和Neo4j中实用案例

Mark Needham & Amy E. Hodler (数据科学家)-[:热爱]->(Neo4j) 强大 实用 智能

Neo4j是处理数据网络（connected data）排名第一的平台，它同时具备图分析、存储和处理能力。Neo4j中的图算法展示了数据中隐藏的模式，并能增强机器学习的预测能力。

序(Preface) 世界是由连接(connections)驱动的，从金融、通信系统、社会过程到生物过程。揭示这些连接背后的含义，会推动各行业上的突破，比如识别欺诈团伙、对团队能力评估建议进行优化、和预测级联故障等。

因为图算法是基于数学而发展起来，它通过数据间的关系来获得知识见解，随着数据间连接越来越快，大家对图的兴趣也是与日俱增。图分析能够在大的规模上揭示复杂系统和网络的工作原理，这适用于任何组织。

我们对图分析的效用和重要性充满了热情，也体验到揭示复杂场景的内部工作原理所带来的乐趣。直到最近，应用图分析仍然需要大量的专业知识和决心，因为工具和集成并不容易，很少有人知道如何应用图算法到他们的困境中去。我们的目标是帮助改变这种状况。我们写这本书是为了帮助各组织更好地利用图分析做出新的发现，并更快地开发智能解决方案。

本书的内容

本书是给那些使用Apache Spark和Neo4j的开发人员和数据科学家用的图算法实用指南。虽然我们的算法示例是利用 Spark和Neo4j平台，但无论您选择什么图形技术，本书也将有助于理解更通用的图概念。

本书前两章介绍了图分析、算法和理论。第三章简要介绍了本书中使用的平台。之后的三章，专注于经典图形算法：路径查找、中心性、和社区检测。最后的两章说明如何在工作流程中应用图形算法，一章是一般性的分析，另一章是机器学习。

在每个算法类别的开头,都有一个参考表,可帮助您快速索引到相关算法。对于每种算法，都会有: • 关于算法作用的说明 • 算法的用例，并告诉你何时使用该算法 • 在Apache Spark或Neo4j上的示例代码

本书中使用的约定

本书使用了以下排版约定: Italic 指示新术语、URL、电子邮件地址、文件名和文件扩展名。 Constant width 用于程序列表，以及段落中引用程序元素。例如变量或函数名称、数据库、数据类型、环境变量、语句和关键字。 Constant Width Bold 显示应由用户逐字键入的命令或其他文本。 Constant Width Italic 显示应替换为用户提供的值或由上下文确定的值。

意味着，这里是提示或建议。 意味着，这里是常规注释。 意味着，这里是警告，需要特别注意。

使用示例代码

补充材料(代码示例、练习等)可在以下网址下载:https://bit.ly/2FPgGVV。

这本书是帮助你来完成工作的。通常，如果提供了书中的示例代码，您可以在程序和文档中使用它。您不需要联系我们获得许可，除非您正在复制代码中很重要的部分。例如，编写一个程序，该程序使用此书中的代码块，不需要许可。销售或分发O’Reilly书中的示例光盘是需要得到许可的。引用此书籍和示例代码来回答问题，不需要许可。将本书中的重要部分的代码纳入到你的产品文档中，需要许可。

如果你在使用示例代码时指明了引用，我们会很欢迎，但是我们不做强制性的规定。

引用通常包括标题、作者、出版商和 ISBN。

例如:"Graph Algorithms by Amy E. Hodler and Mark Needham (O’Reilly). Copyright 2019 Amy E. Hodler and Mark Needham, 978-1-492-05781-9.”

如果您觉得使用代码示例超出了以上合理使用或授予的权限，请随时联系我们permissions@oreilly.com。

O’Reilly在线学习

O’Reilly在40年来提供技术和业务的培训、知识和智慧，帮助许多公司取得成功。

我们独一无二的专家和创新者的网络，通过书籍、文章、会议和在线学习平台来分享他们的知识和专业技能。O’Reilly的在线学习平台提供随需所取的在线培训课程、深度学习路径和交互式代码环境，以及O’Reilly和其他200多出版商提供的大量的文字和音视频内容。请访问http://oreilly.com，获得更多的信息。

如何与我们联系

请将关于这本书的评论和疑问发给出版商：

O’Reilly Media, Inc.
1005 Gravenstein Highway North
Sebastopol, CA 95472
800-998-9938 (in the United States or Canada)
707-829-0515 (international or local)
707-829-0104 (fax)

我们有一个关于本书的网页，你可以访问http://bit.ly/graph-algorithms 来获得勘误、示例和任何额外的信息。 关于技术问题的评论和询问，请给bookquestions@oreilly.com这个地址发送邮件。 希望获得更多的关于我们的书籍、课程、会议和新闻，请访问我们的网站http://www.oreilly.com. 我们在facebook上的位置 http://facebook.com/oreilly 我们在tweeter上的账号 http://twitter.com/oreillymedia 在Youtube上的内容 http://www.youtube.com/oreillymedia

致谢 我们非常喜欢把这本书的内容整理在一起，并感谢所有那些协助的人。我们特别要感谢Michael Hunger的指导，Jim Webber的宝贵编辑，Tomaz Bratanic的热心研究。最后，我们非常感谢Yelp允许我们将其丰富的数据集用于功能强大的示例。

前言(Foreword)

营销因素分析、反洗钱分析(AML)、客户旅程建模、安全事件因果因素分析、文献发现、欺诈网络检测、互联网搜索节点分析、地图应用创建、疾病聚类分析、威廉莎士比亚戏剧表演分析，所有的这些都共同点。你可能已经猜到，这些事物的共同点是使用了图。这证明莎士比亚是正确的，他曾经宣布，“整个世界都是一个图(graph)!”

好吧，开个玩笑，这个爱芬河的游吟诗人（指的是莎士比亚）其实并没有在这句话上写上图（graph），他用的词是舞台（stage）。但是，请注意，上面列出的示例都涉及到实体和它们之间的关系，包括直接的和间接的关系。实体是图中的节点，可以是人员、事件、对象、概念或者地方。节点之间的关系是图中的边。因此，莎士比亚的戏剧的精髓，难道不是实体（the Nodes, 节点）和它们之间的关系（the edges, 边）的写照吗？因此，也许莎士比亚可以在他的注明宣言中写下“图”（graph）这个字。

使得图算法(graph algorithm)和图数据库(graph database)变得有趣而且强大的，不是两个实体之间的简单关系：A 与 B 相关。毕竟，标准的关系型数据库（RDBMS）在几十年前，在实体关系图 (Entity-Relationship Diagram, ERD) 中已经能够实例化这些类型的关系。所以，使得图（graph）如此重要的是有方向的关系和可传递的关系。在定向关系中，A 可能导致 B，但反过来就不行。在可传递关系中，A 可以直接(directly)与 B 相关，而 B 可与 C 直接相关，A和C并不直接相关，因此A与C间接（transitively）相关。

通过这些可传递的关系，图模型揭示了实体之间的关系，尤其是当它们数量众多、多种多样，且具有许多可能的关系/网络模式/实体间的离散程度的时候。而在关系型数据库中，这种情况就会被看成断开、不相关，或者干脆就无法被发现的。因此，图模型可以有效地应用于许多网络分析用例。

考虑这个营销归因用例：一个人A看到了某个市场营销活动，A在社交媒体中谈论它；B这个人和A之间有关系，并且B看到了这个评论。之后，B购买了市场营销活动所推荐的产品。从市场营销活动经理的角度来看，标准关系模型无法识别归因，因为B看不到市场营销活动，而A未对市场活动做出直接响应。市场活动看起来像是失败的，但实际上它是成功的，因为ROI（投入产出比）是正的！它是通过市场营销活动和最终客户购买之间的非直接（transitive）关系,也就是通过一种中介(中间的实体)来完成的。

接下来,考虑反洗钱分析案件：两个人A和C都涉嫌非法贩运。有关部门将标记两者之间的任何互动(例如，金融数据库中的金融交易)，并严格审查（scrutinize）。

但是,如果A和C从未一起交易业务,而是通过安全、受尊重和未被标记的财务机构B进行金融交易,那么该交易又能获得什么结果呢？这要看图分析算法！图引擎通过中间人B发现A和C之间的可传递关系。

在互联网搜索中，主流搜索引擎使用基于图的超链接网络的算法来查找任何给定搜索词集在整个互联网上的中央权威节点。在这种情况下，关系（边）的方向性至关重要，因为网络中的权威节点是许多其他节点指向的节点。

文献发现 (Literature-based discovery, LBD)：基于图的知识网络应用程序支持在数千(甚至数百万)研究期刊文章的知识库中进行重大发现，”隐性知识（hidden knowledge）"只能通过已发表的研究成果之间的连接来发现，其间可能有许多的非直接关系。LBD正被应用于癌症研究，其中大量的语义医学知识库的症状、诊断、治疗、药物相互作用、遗传标记、短期结果和长期后果，可能是”隐藏的”而且在之前未知的治愈手段，或对疑难杂症病例的有益治疗。知识可能已经在网络中，但我们需要连接各个“点”来找到它。

以上通过图算法进行网络分析，对于其他上面列举到的用例，可以给出类似的图功能描述。每个案例都深深涉及实体(人、对象、事件、行动、概念和地点)及其关系(接触点、因果关联和简单关联)。

在考虑图的强大功能时,我们应该记住,对于实际用例,图形模型中最强大的节点可能是"上下文"。上下文可能包括时间、位置、相关事件、邻近实体等。因此,将上下文合并到图形中，作为节点或作为边，就会产生令人印象深刻的预测性分析和规范分析的能力。

Mark Needham 和 Amy Hodler的《Graph Algorithm - Practical Examples in Apache Spark & Neo4j》(本书)旨在围绕这些重要的图分析类型，包括算法、概念、算法在机器学习上的实际应用，来扩展我们的知识和能力。从基本概念到基本算法，从处理平台和实际用例，作者为图的精彩世界编制了一份具有启发性和说明性的指南。 — Kirk Borne博士 首席数据科学家，常务顾问 Booz Allen Hamilton公司 2019年3月

微信公众号： 《Medical与AI的故事》 文章地址：https://mp.weixin.qq.com/s/2knabidMBfZJY8np1reujw