GraphGists

引言

现代金融市场由于算法交易而运行得非常快。本质上,计算机根据信息输入和巧妙的算法自动执行交易。这一切都发生得非常迅速。事实上,计算机在快速执行交易方面表现得如此出色,以至于信息从一个城市传输到另一个城市的速度实际上成为了一个限制因素。例如,如果在华盛顿特区发布了一项影响金融市场的公告,纽约州的交易员可能会比华盛顿州的西雅图等地的交易员更早“听到”该消息。

由于信息传输速度不能超过光速(实际上,由于沿途需要进行各种处理,信息传输速度要慢得多),我们可以计算出特定信息从一个城市发布到其他城市所需时间的下限。正如您所料,这个问题涉及网络中的流动,因此在Neo4j(或任何图数据库)中建模起来相当简单。

数据模型

我们的数据模型包含一组城市,每个城市都有经度和纬度,我们将用它们来计算距离(我们可以将距离作为数据输入,但使用Neo4j来完成这项任务更有趣,并且在更通用的情况下,您可能希望节点能够移动)。每个城市通过`:BACKBONE_TO`关系连接到一个或多个其他城市。这表示关系涉及的两个城市之间运行着互联网骨干网络。在此示例中,我们大多是虚构的骨干网络,但连接到东京的骨干网络根据实际的海底电缆拓扑是准确的。

Information network data model
图1. 信息网络数据模型

距离计算

在确定信息在城市间传输所需时间的下限之前,我们必须计算由互联网骨干网络连接的城市之间的距离。我们假设连接城市的电缆位于大圆上,换句话说,每条电缆都位于城市之间最短可能的连线上。

// Find the great circle distance from Tokyo to Seattle
MATCH (c1:City { name: "Tokyo" })
MATCH (c2:City { name: "Seattle" })
RETURN 2 * 6371 * asin(sqrt(haversin(radians(c1.lat - c2.lat)) + cos(radians(c1.lat)) * cos(radians(c2.lat)) * haversin(radians(c1.lon - c2.lon)))) AS Distance

在我们的例子中,我们希望记录由互联网骨干网络连接的城市之间的距离。我们可以将这些数据存储在`:BACKBONE_TO`边缘上。请注意,我们不必担心重复计算,因为我们已经指定了关系方向,所以每个距离只会计算一次。如果我们省略方向,每个距离将计算两次,尽管最终结果将完全相同。

// Add distance to backbone edges
MATCH (c1:City)-[r:BACKBONE_TO]->(c2:City)
WITH 2 * 6371 * asin(sqrt(haversin(radians(c1.lat - c2.lat))+ cos(radians(c1.lat))* cos(radians(c2.lat))* haversin(radians(c1.lon - c2.lon)))) AS dist, r, c1, c2
SET r.dist = dist
RETURN c1.name, c2.name, r.dist

映射信息流

我们的下一步是找到从一个城市到另一个城市的候选路径。一旦找到这些路径,我们就可以计算信息沿每条路径传输所需的最小时间,并找到它们之间的最短路线。首先,我们可以找到从一个城市到另一个城市的所有唯一且简单的(没有重复城市)路径。以下是东京和芝加哥的示例

// Find all unique, simple paths from one city to another
MATCH p=(:City { name: "Tokyo" })-[:BACKBONE_TO*]-(:City { name: "Chicago" })
WHERE all(c IN nodes(p) WHERE 1=size([m IN nodes(p) WHERE m=c]))
RETURN DISTINCT [ n IN nodes(p) | n.name] AS Path, length(p) AS Length

接下来,我们希望找到距离最短的路径

// Find the shortest distance path from one city to another
MATCH p=(:City { name: "Tokyo" })-[:BACKBONE_TO*]-(:City { name: "Chicago" })
WHERE all(c IN nodes(p) WHERE 1=size([m IN nodes(p) WHERE m=c]))
WITH reduce(s = 0, hop IN relationships(p) | s + hop.dist) AS distance, p
ORDER BY distance LIMIT 1
RETURN DISTINCT [n IN nodes(p) | n.name] AS Path, length(p) AS Length, distance AS Distance

下一步是将距离转换为时间。我们将假设信息在城市之间以光速传播。正如前面提到的,这并非完全准确,但由于我们正在寻找信息从一个城市传输到另一个城市所需时间的下限,因此使用信息流本身可能达到的最快速度是合理的。

另外,我们可以通过考虑沿途每个连接点的处理时间来使这个模型更复杂,也许更准确。当信息到达网络中的某个特定节点时,必须将其路由到沿其路径的下一个节点,这需要一些非零时间。因此,我们实际上可能希望在每个“跳跃”都有成本的约束下,最小化信息必须传输的距离。在这种情况下,我们往往会偏爱不太复杂的路径,即使它们稍微长一些。

我们可以使用下面的查询计算信息在城市之间传输所需的毫秒数。请注意,我们只需将距离除以300即可得到毫秒,因为光速为每秒300,000公里。

// Find the shortest distance path from one city to another
MATCH p=(:City { name: "Tokyo" })-[:BACKBONE_TO*]-(:City { name: "Chicago" })
WHERE all(c IN nodes(p) WHERE 1=size([m IN nodes(p) WHERE m=c]))
WITH reduce(s = 0, hop IN relationships(p) | s + hop.dist) AS distance, p
ORDER BY distance LIMIT 1
RETURN DISTINCT [n IN nodes(p) | n.name] AS Path, length(p) AS Length, distance AS Distance

然后我们可以将此查询推广到计算信息在任意一对城市之间传输所需的时间。

// Compute the minimum travel time between all pairs of cities
MATCH p=(c1:City)-[:BACKBONE_TO*]-(c2:City)
WHERE c1.name <> c2.name and all(c IN nodes(p) WHERE 1=size([m IN nodes(p) WHERE m=c]))
WITH reduce(s = 0, hop IN relationships(p) | s + hop.dist) AS distance, p, c1, c2
ORDER BY distance
RETURN c1.name AS `Start City`, c2.name AS `End City`, collect(distance / 300)[0] AS ms
ORDER BY c2.name

关于

创建者:George Lesica (@glesica) 和 William Lyon (@lyonwj)。

© . All rights reserved.