在neo4j中比较或区分两个图

zvms9eto  于 12个月前  发布在  其他
关注(0)|答案(4)|浏览(169)

我在neo4j数据库中有两个不相连的图。它们是非常相似的网络,但其中一个是同一图表的几个月后的版本。
有没有一种方法,我可以很容易地比较这两个图表,看看任何添加,删除或编辑,已完成的网络?

px9o7tmv

px9o7tmv1#

如果你想要一个纯Cypher的解决方案来比较两个图的结构,你可以尝试下面的方法(基于Mark Needham的文章从图https://markhneedham.com/blog/2014/05/20/neo4j-2-0-creating-adjacency-matrices/创建邻接矩阵)
基本思想是构造两个邻接矩阵,每个图一个,每个节点标识符(业务标识符,而不是节点id)的列和行进行比较,然后对两个矩阵执行一些代数运算以找到差异。
问题是,如果图不包含相同的节点标识符,那么邻接矩阵将具有不同的维度,使得实际比较更加困难,因此技巧是产生两个相同大小的矩阵,并使用第一个图的邻接矩阵填充一个,使用第二个图的邻接矩阵填充第二个。
考虑这两个图表:

图1中的所有节点都标记为:G1,图2中的所有节点都标记为:G2
步骤1是从两个图中找到所有唯一的节点标识符,在本例中是“name”属性:

match (g:G1)
with collect(g.name) as g1Names
match (g:G2)
with g1Names + collect(g.name) as collectedNames
unwind collectedNames as allNames
with collect(distinct allNames) as uniqueNames

uniqueNames现在包含两个图中所有唯一标识符的列表。(有必要展开收集的名称,然后再收集它们,因为distinct操作符在列表上不起作用-还有更多的收集和展开!)
接下来,创建两个新的唯一标识符列表来表示第一图的邻接矩阵的两个维度。

unwind uniqueNames as dim1
unwind uniqueNames as dim2

然后执行一个可选的匹配,以创建G1(第一个图)中每个节点与每个其他节点的笛卡尔积。

optional match p = (g1:G1 {name: dim1})-->(g2:G1 {name: dim2})

匹配的路径要么存在,要么从上面的match语句返回null。现在这些被转换为节点之间的边数,如果没有连接,则为零(邻接矩阵的本质)。匹配的路径被排序,以保持矩阵中的行和列的顺序在创建时正确。uniqueNames被传递,因为它将被用于构造第二图的邻接矩阵。

with uniqueNames, dim1, dim2, case when p is null then 0 else count(p) end as edgeCount
order by dim1, dim2

接下来,将这些边汇总为第二维的值列表

with uniqueNames, dim1 as g1DimNames, collect(edgeCount) as g1Matrix
order by g1DimNames

对第二图重复上述整个操作,以生成第二邻接矩阵。

with uniqueNames, g1DimNames, g1Matrix
unwind uniqueNames as dim1
unwind uniqueNames as dim2
optional match p = (g1:G2 {name: dim1})-->(g2:G2 {name: dim2})
with g1DimNames, g1Matrix, dim1, dim2, case when p is null then 0 else count(p) end as edges
order by dim1, dim2
with g1DimNames, g1Matrix, dim1 as g2DimNames, collect(edges) as g2Matrix
order by g1DimNames, g2DimNames

此时g1DimNamesg1Matrixg2DimNamesg2Matrix形成笛卡尔积。通过使用filter语句删除重复行,可以分解此乘积

with filter( x in collect([g1DimNames, g1Matrix, g2DimNames, g2Matrix]) where x[0] = x[2]) as factored

最后一步是确定两个矩阵之间的差异,这只是找到上面因子分解结果中不同的行的问题。

with  filter(x in factored where x[1] <> x[3]) as diffs
unwind diffs as result
return result

然后,我们最终得到一个结果,显示了什么是不同的,以及如何不同:

解释结果:前两列表示第一图的邻接矩阵的子集,后两列表示第二图的对应的逐行邻接矩阵。字母字符表示节点名称,数字列表表示矩阵中每个原始列(本例中为A到G)的相应行。
查看“A”行,我们可以得出结论,节点“A”拥有图1中的节点“B”和“C”,并且节点“A”拥有图2中的节点“B”一次,节点“C”两次。
对于“D”行,节点“D”在图1中不拥有任何节点,而在图2中拥有节点“F”和“G”。
这种方法至少有几个警告:
1.创建笛卡尔积是很慢的,即使是在很小的图中。(我一直在用这种技术比较XML模式,比较两个包含大约200个节点的图,每个图大约需要30秒,而上面的例子在我相当小的服务器上需要14毫秒)。
1.当节点的数量超过微不足道的数量时,阅读结果矩阵并不容易,因为很难跟踪哪个列对应于哪个节点。(为了解决这个问题,我将结果导出到CSV,然后将节点名称(从uniqueNames开始)插入到电子表格的第一行。

hyrbngr7

hyrbngr72#

虽然这可能是一个老问题,可能不再关心原来的询问者,我想提供一个答案的情况下,它证明有价值的任何人谁遇到它。
如果你阅读了所有答案的回复,你会发现每个答案都没有提供真正实用的解决方案,因为它们都有重要的问题。它们要么比较单个数据库中的子图,而不是比较2个不同的数据库,要么由于现有导出工具的实现选择而遇到复杂性。
Compare41是一个可以比较两个neo4j数据库的工具。你可以看到他们模型的差异,实际数据的差异,并同步子图或整个数据库。它可以在https://www.circles-arrows.com/上找到。
为了完全透明,我创建了Compare41,并与Circles Arrows有着密切的联系。

svmlkihl

svmlkihl3#

我想区分是最容易做的使用基于文本的工具。
我能想到的一种方法是使用https://github.com/jexp/neo4j-shell-tools将两个子图导出到GraphML,然后应用unix中的常规diff
另一种方法是在neo4j-shell中使用dump,并如上所述对结果进行比较。

xggvc2p6

xggvc2p64#

这在很大程度上取决于你想要的差异和图形本身的约束。

  • 如果节点和关系有一个标识符属性(不是内部Neo4j ID),那么你可以下拉每个图的节点和关系,并跟踪哪些节点被添加、删除或更改(区分属性)。
  • 如果关系不是唯一标识的(通过属性),但节点是,它们的 * 自然键 * 是开始节点,结束节点和类型,因为重复的关系不能存在。
  • 如果两者都没有托管标识符,但属性是不可变的,那么可以跨节点比较这些属性(可能代价很高),然后是方法中的关系。

相关问题