2019-05-12
原文链接: https://tbgraph.wordpress.com/2017/11/23/neo4j-marvel-social-graph-algorithms-centralities/
关于漫威英雄的社交网络系列已写了好几篇文章，是时候结束它了。作为本系列的最后一篇文章，我们将来研究一下如何在cypher语句映射的虚拟图上进行中心性计算，我们将使用Neo4j和图形算法库来找出漫威英雄网络中最有影响力的英雄或其他重要的英雄。
关于漫威社交网络的研究已完成的文章有以下几篇：
Neo4j中使用Louvain和标签传播算法对漫威英雄进行客户群分析
使用Cypher进行虚拟图映射
正如我在前面文章中说过的，使用Cypher映射虚拟图是真的好用，他可以使我们简单快速的映射一个我们想要的虚拟图，我们简称为“Cypher加载”。为了更好的理解这个神奇的功能，我们需要深入了解它是如何工作。
与直接使用结点标签和关系类型加载子图不同，Cypher加载允许我们定义关系的方向，通常是以下三种值“incoming”,"outgoing"或者"both"(双向/无向)，但是Cypher加载不支持单条无向关系。
这看起来可不太友好，但事实上，Cypher加载允许我们使用Cypher查询语句映射各种虚拟图去尝试执行图像算法。我在之前的文章中也使用过，只是没有详细的介绍它而已。
假设我们现在有两个英雄结点以及在他们之间有一个单向的关系。将此图加载为无向图或者有向图的唯一区别就是：在使用Cypher查询语句映射时是否指定关系的方向。当我们在查询时不指定方向，Cypher引擎会为每个关系返回两个方向的结果，这样我们映射图也就是双向的，你也可以称他为无向的。
映射有向图:
MATCH (u1:Hero)-[rel:KNOWS]->(u2:Hero)
RETURN id(u1) as source, id(u2) as target映射无向图:
MATCH (u1:Hero)-[rel:KNOWS]-(u2:Hero)
RETURN id(u1) as source, id(u2) as target中心性
在图论与网络分析中，中心性是用来表示网络中结点重要性的指标之一。在社交网络中，其用来表明最有影响力的人。在互联网、城市网络甚至传染病学中，用来表明关键结点。中心性概念最初应用在社交网络中，并且它的很多术语都可以反应出其社会学起源，随后中心性被推广到其它类型网络的分析中。[1]
Pagerank
Pagerank是因Google专有的搜索算法。它通过计算链接到页面的链接数量和质量来决定当前页面的重要性。其基本的假设是，重要的结点肯定会有许多的页面链向它。关于Pagerank更多内容可以看此文(https://neo4j.com/docs/graph-algorithms/3.5/algorithms/page-rank/)
我们使用Cypher加载来漫威网络中最大社群的结点，并且设置关系的weight阈值为100.
call algo.pageRank.stream(
// 仅加载最大的社群。
'MATCH (u:Hero) WHERE u.component = 136 RETURN id(u) as id
','
MATCH (u1:Hero)-[k:KNOWS]-(u2:Hero)
// 近似性阈值
WHERE k.weight >= 100
RETURN id(u1) as source, id(u2) as target
',{graph:'cypher'}
) yield node,score
WITH node,score ORDER BY score DESC limit 10
return node.name as name, score;美国队长是Pagerank分数最高的，他位于网络的中心，有24个关系，并且与其他重要英雄如雷神托尔、蜘蛛侠、钢铁侠都有联系。如果我们仔细看一下与美国队长有联系的英雄，会发现一个有趣现象，他们因为与美国队长有联系，而使得他们的pagerank分也比较高。
结点颜色由浅到深代表着Pagerank值由小到大。
译者言：上面的查询语句中
u.component = 136代表着社群的ID，(如果你执行上的语句没有结果可以试试改成321，这是我计算是使用的社群ID)。这个值可以在上一篇文章Neo4j中使用Louvain和标签传播算法对漫威英雄进行客户群分析中看到。但我们的数据中Hero结点是没有这个属性的，为了将Hero结点上增加component属性，需要先运行下面的语句:CALL algo.unionFind('Hero', 'KNOWS',
{weightProperty:'weight', defaultValue:0.0, threshold:100.0,concurrency:1, write: true, writeProperty:'component'})
YIELD nodes, setCount, loadMillis, computeMillis, writeMillis此语句运行之后就会在每个Hero结点上增加一个component属性。
接近中心性
接近中心性定义了一个点到所有其他点最短距离的和，换句话说，要计算接近中心性，首先需要计算每对结点之间的最短路径长度。然后再对每个结点计算其到所有其他结点的最短路径和。[2]
接近中心性可以理解为信息流到达网络中任一点的所消耗的时间指标。这个接近中心性分数越高，代表信息流从一个结点到另一个结点所花的时间就越长。因此，我们可以认为接近中心性代表着一个结点到达其他结点的潜在能力。关于更多信息可见文档(https://neo4j.com/docs/graph-algorithms/3.5/algorithms/closeness-centrality/)
译者言：这个接近中心性的介绍好生硬，其实简单说，接近中心性，计算的是一个点到其他所有点的距离的总和，这个总和越小就说明这个点到其他所有点的路径越短，也就说明这个点距离其他所有点越近，从而证明这个点的重要性。
我们仍将使用Cypher加载漫威网络中最大社群中的结点并将关系的weight阈值设置为100。对于接近中心性而言，最重要的是需要加载一个独立社群。
不幸的是，当图是非连通图时，接近中心性是无法使用的，因为在非连通图中，两个点可能属于不同的社群，则这两个点是无法连接的，这样他们之间的距离就是无穷大。对于这样的图中的每一个点，都有属于另一个社群的点与之无法连接。因此图中所有顶点的都是没有用的，而接近中心性的计算也被限制在最大的社群中，其他社群中结点的作用是被忽略的。
CALL algo.closeness.stream(
// Match only the biggest component
'MATCH (u:Hero) WHERE u.component = 136 RETURN id(u) as id',
'MATCH (u1:Hero)-[k:KNOWS]-(u2:Hero)
// Similarity threshold
WHERE k.weight >= 100
RETURN id(u1) as source,id(u2) as target',
{graph:'cypher'}) YIELD nodeId, centrality
WITH nodeId,centrality
ORDER BY centrality DESC LIMIT 10
MATCH (h:Hero) where id(h)=nodeId
RETURN h.name as hero, centrality上图中可以看出，美国队长的位置非常特殊，事实上，在所有类型的中心性上，美国队长都是排第一。我们可以看到，在较紧密的社群里，其结点的接近中心性的值相对较大，而在边缘或较少连接的结点上，其接近中心性的值也较小。另外，我们还注意到图中结点的分布也很重要，一般中间社群结点的接近中心性值要比周边社群的高。例如，钢铁侠和幻视要比蜘蛛侠的接近中心性高。但有意思的是蜘蛛侠的Pagerank值要比较他们大。
结点颜色由浅到深代表着接近中心性值由小到大。
和谐中心性（值中心性）
从毕达哥拉斯和柏拉图时代起，人们就知道，和谐就是“谐调和优美的比率”的表述，后来，音乐家用来表达规范音阶，建筑学家描述建筑的完美比例。[4]
社交网络分析是一门快速发展的且跨学科领域，它由社会学、物理学、历史学、数学、政治等多种学科共同发展而来。可能是由于缺少综合性研究，造成其中有些方法存在着不足，但已被普遍所接受(Freeman, 1978; Faust & Wasserman, 1992)，而接近中心性在非连通网络的不适用性就是其一。和谐中心性也正是用来在非连通网络中代替接近中心性的。实际情况显示，在真实环境下，我们解读的结果发现其与接近中心性指标一致，计算复杂度相同，但最重要的是它可用于非连通网络！[3]
CALL algo.closeness.harmonic.stream(
'MATCH (u:Hero) WHERE u.component = 136 RETURN id(u) as id ',
'MATCH (u1:Hero)-[k:KNOWS]-(u2:Hero) WHERE k.weight >= 100 RETURN id(u1) as source,id(u2) as target',
{graph:'cypher'}) YIELD nodeId, centrality
WITH nodeId,centrality
ORDER BY centrality DESC LIMIT 10
MATCH (h:Hero) where id(h)=nodeId
RETURN h.name as hero, centrality因为和谐中心性是为了帮助接近中心性解决其在非连通图上的问题，所以，得到的结果也是相似的。
译者言：这个和谐中心性（Harmonic Centrality），完全没有找到相应的中文资料可参考。仅从官方文章中找到其计算公式为：
结点原始和谐中心性 = sum(1 / 结点到其他点的距离)
归一化后的结点和谐中心性 = sum(1 / 结点到其他点的距离)/(总结点数-1)
而接近中心性的计算公式为:
结点原始接近中心性 = 1/sum(结点到其他点的距离）
归一化后的结点接近中心性 = (总结点数-1)/sum(结点到其他点的距离）
中介中心性
在图论中，中介中心性是一种基于最短路径的中心性指标。在连通图中，每对点都存在着至少一条最短路径，对于无权重图，最短路径是指路径所包含的关系数最少，对于权重图，最短路径是指路径所含边的权重之和最小。而每个点的中介中心性值就是通过这个点的最短路径的条数。更多描述见(https://neo4j.com/docs/graph-algorithms/current/algorithms/betweenness-centrality/)
我们仍然使用Cypher加载那个最大的社群并设置关系的weight阈值为100
CALL algo.betweenness.stream(
'MATCH (u:Hero) WHERE u.component = 136 RETURN id(u) as id',
'MATCH (u1:Hero)-[k:KNOWS]-(u2:Hero) WHERE k.weight >= 100 RETURN id(u1) as source,id(u2) as target',
{graph:'cypher'}) YIELD nodeId, centrality
WITH nodeId,centrality
ORDER BY centrality DESC LIMIT 10
MATCH (h:Hero) where id(h)=nodeId
RETURN h.name as hero, centrality美国队长仍然排在第一位，但这次野兽排到了第二位，这并不奇怪，因为他产中间和右边社群的桥梁。蜘蛛侠和浩克扮演着与野兽相同的角色，但不同的是，他们俩所关联的社群较小，所以，他们的中介中心性值也更低。
结点颜色由浅到深代表着接中介中心性值由小到大。
引用文献
[1] https://en.wikipedia.org/wiki/Centrality
[2] http://qualquant.org/wp-content/uploads/networks/2008+1-7-3.pdf
[3] https://infoscience.epfl.ch/record/200525/files/[EN]ASNA09.pdf?
[4] https://arxiv.org/pdf/cond-mat/0008357.pdf
[6] https://en.wikipedia.org/wiki/Betweenness_centrality
译者言：总算翻译完《漫威社交网络分析》的这个系列了，接下来可以坐等《复仇者联盟4》上映了。
