1. 基于社区发现算法和图分析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元素中展示可视化。
2. Nosql-neo4j-基于社区发现算法和图分析Neo4j解读《权力的游戏》
几个月前，数学家 Andrew Beveridge 和 Jie Shan 在数学杂志上发表的论文《权力的网络》，深入分析了畅销小说《冰与火之歌》第三部《冰雨的风暴》中的人物关系，并将其应用至电视剧《权力的游戏》系列。他们阐述了通过文本分析与实体提取构建人物关系网络，随后采用社交网络分析算法确定关键角色，以及通过社区发现算法识别角色聚类的过程。文中指出，Gephi作为图分析工具，尽管被广泛应用，但作者认为使用Neo4j进行实现更具有吸引力。
为了将原始数据导入Neo4j，作者构建了一个简单的数据模型，首先创建了唯一的约束条件，确保每个角色的名字独一无二，从而保证了数据模型的完整性。通过使用Neo4j的Cypher（一种声明式图查询语言）和LOAD CSV语句，数据得以高效地导入到Neo4j中。尽管可视化图形较为直观，但还需进一步分析以获得更深入的见解。
作者使用Neo4j的图查询语言Cypher对《权力的游戏》进行了详细的人物网络分析。首先，他们计算了网络中角色的数量，接着，对每个角色接触的其他角色数目进行了统计。此外，他们还分析了网络的直径，即最长的最短路径长度，并通过Cypher的shortestPath函数找到了任意两个角色之间的最短路径。进一步地，通过allShortestPaths函数，他们探索了不同路径的可能性，最终识别出关键节点，即在所有最短路径上都出现的角色。这些角色扮演着信息传递者的重要角色，验证了通过可视化展示的路径分析结果。
在讨论节点中心度时，作者强调了度中心性、加权度中心性、介数中心性和紧度中心性的重要性。度中心性反映了角色与其他角色的直接连接数，加权度中心性考虑了连接的频率，介数中心性则衡量了角色作为信息传递者的角色，而紧度中心性评估了角色与网络中其他角色的平均接近程度。通过Cypher计算这些中心性指标，作者发现提利昂·兰尼斯特在《权力的游戏》网络中具有最高的度中心性，这与他复杂的人际关系网相符。
为了进一步分析角色之间的关系，作者借助Python-igraph库，结合Neo4j的强大功能，执行了PageRank算法和社区发现算法。通过构建一个igraph实例，作者能够分析角色之间的复杂关系，并将PageRank结果与社区发现结果整合回Neo4j中。这使得角色之间的相对重要性与所属社区的信息得以可视化，提供了对《权力的游戏》网络结构更全面的理解。
为了直观展示分析结果，作者使用Neo4j的内置浏览器进行了初步的可视化，并进一步利用Vis.js构建了嵌入式可视化图，使得数据展示更加丰富且易于理解。通过整合这些工具与技术，作者成功地构建了一个详细的《权力的游戏》角色关系网络分析，不仅揭示了角色间的复杂联系，还通过视觉化手段提供了对小说情节和角色动态的深入洞察。
3. 关于在复杂网络中社区发现算法的研究及实现，推荐相关的文献，在实现过程中能用到什么软件详解
推荐文献 ”Community detection in graphs“ ，Santo Fortunato，2009
89页的论文，写得很全，涵盖了从提出复杂网络的1998年到2009年的全部重要的研究内容
至于复杂网络的实现，软件很多，推荐igraph，在C和Python中都可以直接调用。