关东建设有限公司网站,网站信息发布和内容建设自查报告,wordpress 显示当前位置,网络安全设计报告上周#xff0c; 我写了关于中间性中心性算法以及使用graphstream 理解它的尝试 #xff0c;在阅读源代码时#xff0c;我意识到我可以使用neo4j的所有最短路径算法将某些东西放在一起。 概括地说#xff0c;中间性中心度算法用于确定图中节点的负载和重要性。 在与Jen讨… 上周 我写了关于中间性中心性算法以及使用graphstream 理解它的尝试 在阅读源代码时我意识到我可以使用neo4j的所有最短路径算法将某些东西放在一起。 概括地说中间性中心度算法用于确定图中节点的负载和重要性。 在与Jen讨论这一点时她指出计算整个图上节点之间的中间性通常是没有意义的。 但是了解在您感兴趣的较小子图中哪个节点最重要可能很有用。 在这种情况下我有兴趣在一个非常小的有向图中确定节点的中间性 让我们简要回顾一下算法 [中间性中心]等于从所有顶点到经过该节点的所有其他顶点的最短路径数。 这意味着我们排除了直接在两个节点之间而不经过任何其他路径的任何路径这是我最初没有掌握的。 如果我们手工确定适用的路径我们将得到以下结果 A - B: Direct Path Exists
A - C: B
A - D: E
A - E: Direct Path Exists
B - A: No Path Exists
B - C: Direct Path Exists
B - D: E or C
B - E: Direct Path Exists
C - A: No Path Exists
C - B: No Path Exists
C - D: Direct Path Exists
C - E: No Path Exists
D - A: No Path Exists
D - B: No Path Exists
D - C: No Path Exists
D - E: No Path Exists
E - A: No Path Exists
E - B: No Path Exists
E - C: No Path Exists
E - D: Direct Path Exists 给出以下中间性中心值 A: 0
B: 1
C: 0.5
D: 0
E: 1.5 我们可以针对最新版本的graphstream 考虑方向编写测试以确认我们的手动算法 Testpublic void calculateBetweennessCentralityOfMySimpleGraph() {Graph graph new SingleGraph(Tutorial 1);Node A graph.addNode(A);Node B graph.addNode(B);Node E graph.addNode(E);Node C graph.addNode(C);Node D graph.addNode(D);graph.addEdge(AB, A, B, true);graph.addEdge(BE, B, E, true);graph.addEdge(BC, B, C, true);graph.addEdge(ED, E, D, true);graph.addEdge(CD, C, D, true);graph.addEdge(AE, A, E, true);BetweennessCentrality bcb new BetweennessCentrality();bcb.computeEdgeCentrality(false);bcb.betweennessCentrality(graph);System.out.println(A A.getAttribute(Cb));System.out.println(B B.getAttribute(Cb));System.out.println(C C.getAttribute(Cb));System.out.println(D D.getAttribute(Cb));System.out.println(E E.getAttribute(Cb));} 输出是预期的 A0.0
B1.0
C0.5
D0.0
E1.5 我想看看是否可以使用neo4j做同样的事情所以我使用以下cypher语句在空白数据库中创建了图形 CREATE (A {name: A})
CREATE (B {name: B})
CREATE (C {name: C})
CREATE (D {name: D})
CREATE (E {name: E})CREATE A-[:TO]-E
CREATE A-[:TO]-B
CREATE B-[:TO]-C
CREATE B-[:TO]-E
CREATE C-[:TO]-D
CREATE E-[:TO]-D 然后我编写了一个查询该查询找到了图中所有节点集之间的最短路径 MATCH p allShortestPaths(source-[r:TO*]-destination)
WHERE source destination
RETURN NODES(p) 如果运行它将返回以下内容 ---------------------------------------------------------| NODES(p) |---------------------------------------------------------| [Node[1]{name:A},Node[2]{name:B}] || [Node[1]{name:A},Node[2]{name:B},Node[3]{name:C}] || [Node[1]{name:A},Node[5]{name:E},Node[4]{name:D}] || [Node[1]{name:A},Node[5]{name:E}] || [Node[2]{name:B},Node[3]{name:C}] || [Node[2]{name:B},Node[3]{name:C},Node[4]{name:D}] || [Node[2]{name:B},Node[5]{name:E},Node[4]{name:D}] || [Node[2]{name:B},Node[5]{name:E}] || [Node[3]{name:C},Node[4]{name:D}] || [Node[5]{name:E},Node[4]{name:D}] |---------------------------------------------------------10 rows 我们仍在返回节点之间的直接链接但是通过基于路径中节点的数量过滤结果可以很容易地纠正这一点 MATCH p allShortestPaths(source-[r:TO*]-destination)
WHERE source destination AND LENGTH(NODES(p)) 2
RETURN EXTRACT(n IN NODES(p): n.name) --------------------------------| EXTRACT(n IN NODES(p): n.name) |--------------------------------| [A,B,C] || [A,E,D] || [B,C,D] || [B,E,D] |--------------------------------4 rows 如果我们稍微调整密码查询我们可以获得每个源/目标的最短路径的集合 MATCH p allShortestPaths(source-[r:TO*]-destination)
WHERE source destination AND LENGTH(NODES(p)) 2
WITH EXTRACT(n IN NODES(p): n.name) AS nodes
RETURN HEAD(nodes) AS source, HEAD(TAIL(TAIL(nodes))) AS destination, COLLECT(nodes) AS paths ------------------------------------------------------| source | destination | paths |------------------------------------------------------| A | D | [[A,E,D]] || A | C | [[A,B,C]] || B | D | [[B,C,D],[B,E,D]] |------------------------------------------------------3 rows 当我们有一种使用cypher来对集合进行切片的方法时从这里获得节点间的中间性得分并不难但是现在使用通用的编程语言要容易得多。 在这种情况下我使用了Ruby并提出了以下代码 require neography
neo Neography::Rest.newquery MATCH p allShortestPaths(source-[r:TO*]-destination)
query WHERE source destination AND LENGTH(NODES(p)) 2
query WITH EXTRACT(n IN NODES(p): n.name) AS nodes
query RETURN HEAD(nodes) AS source, HEAD(TAIL(TAIL(nodes))) AS destination, COLLECT(nodes) AS pathsbetweenness_centrality { A 0, B 0, C 0, D 0, E 0 }neo.execute_query(query)[data].map { |row| row[2].map { |path| path[1..-2] } }.each do |potential_central_nodes| number_of_central_nodes potential_central_nodes.sizepotential_central_nodes.each do |nodes|nodes.each { |node| betweenness_centrality[node] (1.0 / number_of_central_nodes) }end
endp betweenness_centrality 输出以下内容 $ bundle exec ruby centrality.rb
{A0, B1.0, C0.5, D0, E1.5} 它似乎可以完成任务但是我敢肯定在某些情况下它无法处理成熟的库需要处理的问题。 作为一个实验看看有什么可能我认为还算不错 该图位于neo4j控制台上 以防有人感兴趣。 参考 图处理betweens中心性–来自Mark Needham博客博客上我们JCG合作伙伴 Mark Needham的neo4j密码与图流 。 翻译自: https://www.javacodegeeks.com/2013/08/graph-processing-betweeness-centrality-neo4js-cypher-vs-graphstream.html
