图分析在《权力的游戏》中的应用


在这篇文章中,我们回顾了组织是如何集成图事务和分析处理的,然后深入研究图算法。我们将提供在《权力的游戏》数据上使用图算法的示例,以说明如何入门。请注意,这部分内容摘自O'Reilly的书,Graph Algorithms: Practical Examples in Apache Spark and Neo4j,您可以免费下载。

Neo4j在一个统一的平台中提供本机图形存储,计算和分析。我们的目标是帮助组织使用连接优先的方法揭示人员,过程,位置和系统是如何相互关联的。Neo4j Graph平台支持处理人工智能,欺诈检测,实时推荐和主数据的应用程序。

您可能还喜欢:6 Project Management Lessons From Game of Thrones

合并事务和分析处理

事务处理和分析处理之间的界限已经模糊了一段时间。在线事务处理(或OLTP)操作通常是短期活动,如订票或记入帐户。它意味着大量的低延迟查询处理和高数据完整性。这种方法与联机分析处理(OLAP)非常不同,联机分析处理(OLAP)便于对具有多种数据源,格式和类型的历史数据进行更复杂的查询和分析。

现代数据密集型应用程序现在将实时事务操作与分析相结合。这种处理的合并是由软件和低成本,大内存硬件的进步所推动的。将分析和事务结合在一起可以使连续分析成为常规操作的自然组成部分。

我们现在可以通过对两种类型的处理使用单一的统一平台来简化我们的架构。这意味着我们的分析查询可以利用实时数据,并且我们可以在被描述为混合事务和分析处理(HTAP)的情况下简化迭代分析过程。


混合平台支持事务所需的低延迟查询处理和高数据完整性,同时集成大量数据的复杂分析。

图分析与算法

随着数据变得越来越相互连接,系统变得越来越复杂,利用我们数据中丰富和不断发展的关系是至关重要的。如果您已经在使用图形数据库,那么现在正是将图形分析添加到您的实践中以揭示数据中的结构模式和预测模式的绝佳时机。

在这个最高层次上,图形分析被应用于理解或预测动态群体中的行为。这需要了解一个组的连接和拓扑。图算法通过使用专门为使用连接而开发的数学,通过它们的连接来检查网络的整体性质,从而完成这一任务。通过这种方法,我们可以理解连接系统的结构并对其过程进行建模。

使用图表我们可以对从金融市场到IT服务的动态环境进行建模,为机器学习找到更多预测性元素以打击金融犯罪,或者为个性化体验和推荐发现社区。图形分析帮助我们推断关系和预测行为。

图算法分类

图算法提供了分析连接数据的最有效的方法之一,因为它们的数学计算是专门为操作关系而构建的。图算法的类型和类别很多。三个经典类别考虑图的整体性质:寻路,中心性和社区检测。而其他图算法如相似度和链接预测算法则考虑和比较特定的节点。

  • 寻路(和搜索)算法对于图形分析和算法以及探索节点之间的路径是基本的。这些算法被用来识别最优路径,用于诸如物流规划,最小成本路径选择和游戏模拟等用途。
  • 中心性算法帮助我们理解图中各个节点的角色和影响。它们之所以有用,是因为它们确定了最重要的节点,并帮助我们理解群体动态,例如可信度,可访问性,传播速度以及群体之间的桥梁。
  • 社区算法评估相关的笔记集,找到成员在组内有更多关系的社区。识别这些相关集揭示了节点的群集,孤立的组和网络结构。这有助于推断同侪群体的类似行为或偏好,估计弹性,查找嵌套关系,并为其他分析准备数据。
  • 相似性算法研究单个节点的相似性。通过比较节点的属性和属性,可以识别出最相似的实体,并对差异进行评分。这有助于构建更个性化的推荐以及开发本体和层次结构。
  • 链路预测算法考虑节点的邻近性以及结构元素,如节点之间的潜在三角形,来估计新关系形成的可能性或未记录的连接存在的可能性。这类算法有许多应用,从毒品再利用到刑事调查。

图分析在《权力的游戏》中的应用

现在,让我们深入研究在每个人最喜欢的奇幻剧《《权力的游戏》》的数据集上应用图算法。

NEuler-图算法的操场

我们将使用NEuler Graph Algorithms Playground Graph应用程序来实现这一点。NEuler提供了一个直观的UI,让用户执行各种图形算法而无需键入任何代码。这是Neo4j实验室的一个项目,旨在帮助人们快速熟悉图算法并探索有趣的数据。有关该应用程序的更多信息,包括安装说明,将在发布版中提供blog post

安装了NEuler之后,我们需要加载《权力的游戏》示例图,如下面的屏幕截图所示:
Load GoT sample graph

此数据集基于Andrew Beveridge's Network of Thrones并包含了不同季节的角色和角色之间的相互作用。

分析《权力的游戏》

加载了数据集之后,我们就可以开始分析它了。我们的关注点将放在电视剧的第二季上,但我们会偶尔展示其他几季的结果,以作比较。

我们将使用社区检测算法来发现维斯特洛系统中的用户集群,并使用中心性算法来发现最重要和最有影响力的人物。

Louvain模块化算法基于一种启发式最大化模块化得分来检测网络中的社区。(模块性得分范围从-1到1,作为社区内部关系密度的度量,到社区外部关系密度。)如果我们针对《权力的游戏》数据集第2季运行它,并可视化输出格式,我们将看到以下图表:

GoT visualization

在左上角的紫色星团中,我们可以看到丹妮莉丝星团是独立的,与其他星团没有联系。那群人没有和其他人互动。我们最初认为数据或算法一定有问题,并运行了另一个社区检测算法--连接组件来证实我们的发现。

连接组件算法是一种社区检测算法,它根据用户群之间是否存在路径来检测用户群。如果我们运行该算法,我们将看到以下可视化:

Game of Thrones visualization

在这里,我们只有两个社区:左边是丹妮莉丝,右边是绝大多数其他角色。这证实了我们从卢万模块化算法中得出的结论,如果我们把记忆拉回到第二季,我们就会记得丹妮莉丝在一个远离其他主要角色的岛上。

分析社区结构的另一种方法是计算用户所在的三角形的数量。这个图中的三角形表示字符A与字符B相互作用,字符B与字符C相互作用,字符C与字符A相互作用,我们可以在下图中看到一个三角形的例子:

Number of triangles

如果我们运行三角形计数算法并选择表输出格式,我们将看到以下输出:

Number of triangles

我们还会注意到,这个算法返回一个系数分数。这个聚类系数衡量的是,我们的邻居之间的连接程度与它们之间的最大连接程度相比有多好。1分表示我们所有的邻居都是互相影响的。因此,虽然Joffrey在整体三角形上得分很高(邻居交互的原始数量),但我们注意到小指头和珊莎的邻居有更高的连接概率(聚类系数)。

接下来,我们将使用中心性算法来查找重要字符。

中心性算法

中心性算法中最简单的是度中心性,它测量连接到节点的关系的数量。我们可以用这个算法找到交互最多的人物。

当我们运行算法时,我们将看到以下输出:

Centrality algorithm

乔佛里和提利昂互动的人最多,这告诉我们剧集第二季主要是以这些角色为原型的。这并不一定意味着这些人是最有影响力的人物,但他们肯定是那些谈论很多的人!

介数中心性算法检测节点对图中信息流的影响量。它通常用于查找作为图的一部分到另一部分的桥梁的节点。

我们可以用这个算法来找到与维斯特洛内部的子社区有很好联系的人。如果我们运行算法并选择图表输出类型,我们将看到以下输出:

Betweenness Centrality algorithm

图表选项将在适用时显示,这是查看许多中心性算法的好方法,其中排名比实际分数更重要。我们在这里看到乔佛里从学位中心性的排名1下降到这里的排名6,而艾莉亚从学位中心性的排名5上升到这里的排名1。在第二季中,艾莉亚在旅途中,她将充当与她交往的人和王国其他地方的人之间的桥梁节点。

我们也可以看一看第七季的变化:

Betweenness Centrality algorithm

基于中间性中心性,乔恩现在是压倒性地排名第一的角色。他的分数是下一个人的两倍。他很可能是一群人之间的黏合剂,除了乔恩,这些人不与核心群体以外的人交往。

另一个衡量重要性的指标是PageRank,它衡量的是包括间接影响在内的整体影响力。它不仅会发现那些本身就很重要的人,还会发现那些与更有影响力的人交往的人。

Page Rank

在上面的PageRank结果中,我们看到了一些熟悉的面孔--乔佛里和提利昂在度中心度上排名也很高,艾莉亚在中间中心度上排名第一。请注意,对于其他数据集,特别是那些关系复杂的数据集,我们可能会看到中心性排名的更多变化。

现在让我们回到过去,对比一下在第1季运行PageRank,它给出了以下输出:

Page Rank Season 1

奈德显然是这个阶段最有影响力的角色,但可悲的是,这并没有持续下去!通过对分段数据(可能是时间,地理或人口统计)的结果进行比较,我们可以揭示更深层次的故事。

最后,让我们通过展示如何在可视化输出格式中组合社区检测和中心性算法的结果来结束这篇文章。

下图根据Louvain模块化群集为节点着色,并根据PageRank得分为节点大小:

Louvain Modularity cluster and sized based on their PageRank

现在我们不仅可以看到集群,还可以看到特定集群中最重要的字符。不出所料,我们得知丹妮莉丝是孤立星团中最重要的角色。我们还会看到其他一些熟悉的面孔,包括蓝色星团中的艾莉亚和泰温,黄色星团中的提利昂,瑟曦和乔佛里,以及绿色星团中的乔恩。

结论

我们希望你在阅读这篇分析时和我们在写作时一样开心。你只需看一下元数据就能了解到《权力的游戏》的许多信息,这真是令人着迷。

如果您想了解更多关于图分析及其应用的知识,可以在中找到Spark和Neo4j的实际示例和工作代码free digital copy of the O’Reilly Graph Algorithms book

进一步阅读