基于社区发现算法和图分析Neo4j解读《权力的游戏》下篇

其中的分析和可视化是用Gephi做的，Gephi是非常流行的图分析工具。但作者觉得使用Neo4j来实现更有趣。

节点中心度

节点中心度给出网络中节点的重要性的相对度量。有许多不同的方式来度量中心度，每种方式都代表不同类型的“重要性”。

度中心性(Degree Centrality)

度中心性是最简单度量，即为某个节点在网络中的联结数。在《权力的游戏》的图中，某个角色的度中心性是指该角色接触的其他角色数。作者使用Cypher计算度中心性：

MATCH (c:Character)-[:INTERACTS]- RETURN c.name AS character, count(*) AS degree ORDER BY degree DESC

character

degree

Tyrion

36

Jon

26

Sansa

26

Robb

25

Jaime

24

Tywin

22

Cersei

20

Arya

19

Joffrey

18

Robert

18

从上面可以发现，在《权力的游戏》网络中提利昂·兰尼斯特（Tyrion）和最多的角色有接触。鉴于他的心计，我们觉得这是有道理的。

加权度中心性（Weighted Degree Centrality）

作者存储一对角色接触的次数作为 INTERACTS 关系的 weight 属性。对该角色的 INTERACTS 关系的所有 weight 相加得到加权度中心性。作者使用Cypher计算所有角色的这个度量：

MATCH (c:Character)-[r:INTERACTS]- RETURN c.name AS character, sum(r.weight) AS weightedDegree ORDER BY weightedDegree DESC

character

weightedDegree

Tyrion

551

Jon

442

Sansa

383

Jaime

372

Bran

344

Robb

342

Samwell

282

Arya

269

Joffrey

255

Daenerys

232

介数中心性（Betweenness Centrality）

介数中心性：在网络中，一个节点的介数中心性是指其它两个节点的所有最短路径都经过这个节点，则这些所有最短路径数即为此节点的介数中心性。介数中心性是一种重要的度量，因为它可以鉴别出网络中的“信息中间人”或者网络聚类后的联结点。

图6中红色节点是具有高的介数中心性，网络聚类的联结点。

为了计算介数中心性，作者使用Neo4j 3.x或者apoc库。安装apoc后能用Cypher调用其170+的程序：

MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.betweenness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreSET node.betweenness = scoreRETURN node.name AS name, score ORDER BY score DESC

name

score

Jon

1279.7533534055322

Robert

1165.6025171231624

Tyrion

1101.3849724234349

Daenerys

874.8372110508583

Robb

706.5572832464792

Sansa

705.1985623519137

Stannis

571.5247305125714

Jaime

556.1852522889822

Arya

443.01358430043337

Tywin

364.7212195528086

紧度中心性（Closeness centrality）

紧度中心性是指到网络中所有其他角色的平均距离的倒数。在图中，具有高紧度中心性的节点在聚类社区之间被高度联结，但在社区之外不一定是高度联结的。

图7 ：网络中具有高紧度中心性的节点被其它节点高度联结

MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.closeness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreRETURN node.name AS name, score ORDER BY score DESC

name

score

Tyrion

0.004830917874396135

Sansa

0.004807692307692308

Robert

0.0047169811320754715

Robb

0.004608294930875576

Arya

0.0045871559633027525

Jaime

0.004524886877828055

Stannis

0.004524886877828055

Jon

0.004524886877828055

Tywin

0.004424778761061947

Eddard

0.004347826086956522

使用python-igraph

Neo4j与其它工具（比如，R和Python数据科学工具）完美结合。我们继续使用apoc运行 PageRank和社区发现（community detection）算法。这里接着使用python-igraph计算分析。Python-igraph移植自R的igraph图形分析库。 使用 pip install python-igraph 安装它。

从Neo4j构建一个igraph实例

为了在《权力的游戏》的数据的图分析中使用igraph，首先需要从Neo4j拉取数据，用Python建立igraph实例。作者使用 Neo4j 的Python驱动库py2neo。我们能直接传入Py2neo查询结果对象到igraph的 TupleList 构造器，创建igraph实例：

from py2neo import Graphfrom igraph import Graph as IGraph graph = Graph query = ''' MATCH (c1:Character)-[r:INTERACTS]->(c2:Character) RETURN c1.name, c2.name, r.weight AS weight '''ig = IGraph.TupleList(graph.run(query), weights=True)

现在有了igraph对象，可以运行igraph实现的各种图算法来。

PageRank

作者使用igraph运行的第一个算法是PageRank。PageRank算法源自Google的网页排名。它是一种特征向量中心性(eigenvector centrality)算法。

在igraph实例中运行PageRank算法，然后把结果写回Neo4j，在角色节点创建一个pagerank属性存储igraph计算的值：

pg = ig.pagerank pgvs = for p in zip(ig.vs, pg): print(p) pgvs.append({"name": p[0]["name"], "pg": p[1]}) pgvs write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.pagerank = n.pg '''graph.run(write_clusters_query, nodes=pgvs)

现在可以在Neo4j的图中查询最高PageRank值的节点：

MATCH (n:Character) RETURN n.name AS name, n.pagerank AS pagerank ORDER BY pagerank DESC LIMIT 10

name

pagerank

Tyrion

0.042884981999963316

Jon

0.03582869669163558

Robb

0.03017114665594764

Sansa

0.030009716660108578

Daenerys

0.02881425425830273

Jaime

0.028727587587471206

Tywin

0.02570016262642541

Robert

0.022292016521362864

Cersei

0.022287327589773507

Arya

0.022050209663844467

社区发现（Community detection）

图8

社区发现算法用来找出图中的社区聚类。作者使用igraph实现的随机游走算法（ walktrap）来找到在社区中频繁有接触的角色社区，在社区之外角色不怎么接触。

在igraph中运行随机游走的社区发现算法，然后把社区发现的结果导入Neo4j，其中每个角色所属的社区用一个整数来表示：

clusters = IGraph.community_walktrap(ig, weights="weight").as_clustering nodes = [{"name": node["name"]} for node in ig.vs]for node in nodes: idx = ig.vs.find(name=node["name"]).index node["community"] = clusters.membership[idx] write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.community = toInt(n.community) '''graph.run(write_clusters_query, nodes=nodes)

我们能在Neo4j中查询有多少个社区以及每个社区的成员数：

MATCH (c:Character) WITH c.community AS cluster, collect(c.name) AS members RETURN cluster, members ORDER BY cluster ASC

cluster

members

0

[Aemon, Alliser, Craster, Eddison, Gilly, Janos, Jon, Mance, Rattleshirt, Samwell, Val, Ygritte, Grenn, Karl, Bowen, Dalla, Orell, Qhorin, Styr]

1

[Aerys, Amory, Balon, Brienne, Bronn, Cersei, Gregor, Jaime, Joffrey, Jon Arryn, Kevan, Loras, Lysa, Meryn, Myrcella, Oberyn, Podrick, Renly, Robert, Robert Arryn, Sansa, Shae, Tommen, Tyrion, Tywin, Varys, Walton, Petyr, Elia, Ilyn, Pycelle, Qyburn, Margaery, Olenna, Marillion, Ellaria, Mace, Chataya, Doran]

2

[Arya, Beric, Eddard, Gendry, Sandor, Anguy, Thoros]

3

[Brynden, Catelyn, Edmure, Hoster, Lothar, Rickard, Robb, Roose, Walder, Jeyne, Roslin, Ramsay]

4

[Bran, Hodor, Jojen, Luwin, Meera, Rickon, Nan, Theon]

5

[Belwas, Daario, Daenerys, Irri, Jorah, Missandei, Rhaegar, Viserys, Barristan, Illyrio, Drogo, Aegon, Kraznys, Rakharo, Worm]

6

[Davos, Melisandre, Shireen, Stannis, Cressen, Salladhor]

7

[Lancel]

角色“大合影”

《权力的游戏》的权力图。节点的大小正比于介数中心性，颜色表示社区（由随机游走算法获得），边的厚度正比于两节点接触的次数。现在已经计算好这些图的分析数据，让我们对其进行可视化，让数据看起来更有意义。

Neo4j自带浏览器可以对Cypher查询的结果进行很好的可视化，但如果我们想把可视化好的图嵌入到其它应用中，可以使用Javascript可视化库Vis.js。从Neo4j拉取数据，用Vis.js的neovis.js构建可视化图。Neovis.js提供简单的API配置，例如：

var config = { container_id: "viz", server_url: "localhost", labels: { "Character": "name" }, label_size: { "Character": "betweenness" }, relationships: { "INTERACTS": }, relationship_thickness: { "INTERACTS": "weight" }, cluster_labels: { "Character": "community" } }var viz = new NeoVis(config)viz.render

其中：

节点带有标签Character，属性name；

节点的大小正比于betweenness属性；

可视化中包括INTERACTS关系；

关系的厚度正比于weight属性；

节点的颜色是根据网络中社区community属性决定；

从本地服务器localhost拉取Neo4j的数据；

在一个id为viz的DOM元素中展示可视化。

常见的非关系型数据库有：1、mongodb；2、cassandra；3、redis；4、hbase；5、neo4j。其中mongodb是非常著名的NoSQL数据库，它是一个面向文档的开源数据库。

常见的几种非关系型数据库：

1、MongoDB

MongoDB是最著名的NoSQL数据库。它是一个面向文档的开源数据库。MongoDB是一个可伸缩和可访问的数据库。它在c++中。MongoDB同样可以用作文件系统。在MongoDB中，JavaScript可以作为查询语言使用。通过使用sharding MongoDB水平伸缩。它在流行的JavaScript框架中非常有用。

人们真的很享受分片、高级文本搜索、gridFS和map-reduce功能。惊人的性能和新特性使这个NoSQL数据库在我们的列表中名列第一。

特点：提供高性能；自动分片；运行在多个服务器上；支持主从复制；数据以JSON样式文档的形式存储；索引文档中的任何字段；由于数据被放置在碎片中，所以它具有自动负载平衡配置；支持正则表达式搜索；在失败的情况下易于管理。

优点：易于安装MongoDB；MongoDB Inc.为客户提供专业支持；支持临时查询；高速数据库；无模式数据库；横向扩展数据库；性能非常高。

缺点：不支持连接；数据量大；嵌套文档是有限的；增加不必要的内存使用。

2、Cassandra

Cassandra是Facebook为收件箱搜索开发的。Cassandra是一个用于处理大量结构化数据的分布式数据存储系统。通常，这些数据分布在许多普通服务器上。您还可以添加数据存储容量，使您的服务保持在线，您可以轻松地完成这项任务。由于集群中的所有节点都是相同的，因此不需要处理复杂的配置。

Cassandra是用Java编写的。Cassandra查询语言(CQL)是查询Cassandra数据库的一种类似sql的语言。因此，Cassandra在最佳开源数据库中排名第二。Facebook、Twitter、思科(Cisco)、Rackspace、eBay、Twitter、Netflix等一些最大的公司都在使用Cassandra。

特点：线性可伸缩；；保持快速响应时间；支持原子性、一致性、隔离性和耐久性(ACID)等属性；使用Apache Hadoop支持MapReduce；分配数据的最大灵活性；高度可伸缩；点对点架构。

优点：高度可伸缩；无单点故障；Multi-DC复制；与其他基于JVM的应用程序紧密集成；更适合多数据中心部署、冗余、故障转移和灾难恢复。

缺点：对聚合的有限支持；不可预知的性能；不支持特别查询。

3、Redis

Redis是一个键值存储。此外，它是最著名的键值存储。Redis支持一些c++、PHP、Ruby、Python、Perl、Scala等等。Redis是用C语言编写的。此外，它是根据BSD授权的。

特点：自动故障转移；将其数据库完全保存在内存中；事务；Lua脚本；将数据复制到任意数量的从属服务器；钥匙的寿命有限；LRU驱逐钥匙；支持发布/订阅。

优点：支持多种数据类型；很容易安装；非常快（每秒执行约11万组，每秒执行约81000次）；操作都是原子的；多用途工具（在许多用例中使用）。

缺点：不支持连接；存储过程所需的Lua知识；数据集必须很好地适应内存。

4、HBase

HBase是一个分布式的、面向列的开源数据库，该技术来源于 Fay Chang 所撰写的Google论文“Bigtable：一个结构化数据的分布式存储系统”。就像Bigtable利用了Google文件系统（File System）所提供的分布式数据存储一样，HBase在Hadoop之上提供了类似于Bigtable的能力。

HBase是Apache的Hadoop项目的子项目。HBase不同于一般的关系数据库，它是一个适合于非结构化数据存储的数据库。另一个不同的是HBase基于列的而不是基于行的模式。

5、neo4j

Neo4j被称为原生图数据库，因为它有效地实现了属性图模型，一直到存储层。这意味着数据完全按照白板的方式存储，数据库使用指针导航和遍历图。Neo4j有数据库的社区版和企业版。企业版包括Community Edition必须提供的所有功能，以及额外的企业需求，如备份、集群和故障转移功能。

特点：它支持唯一的约束；Neo4j支持完整的ACID(原子性、一致性、隔离性和持久性)规则；Java API: Cypher API和本机Java API；使用Apache Lucence索引；简单查询语言Neo4j CQL；包含用于执行CQL命令的UI: Neo4j Data Browser。

优点：容易检索其相邻节点或关系细节，无需连接或索引；易于学习Neo4j CQL查询语言命令；不需要复杂的连接来检索数据；非常容易地表示半结构化数据；大型企业实时应用程序的高可用性；简化的调优。

缺点：不支持分片

---