机场航线环路分析

Jean

环路

查询

结点

机场

权重

开源

语句

本例

网络

航线

在阳光明媚一片芳菲的人间四月天，小峰的心里充满着对诗和远方的向往，想乘飞机环游一下祖国的大好河山，于是找来一份世界城市的航线图，先规划一下有限假期内自助游的航线。国内机场的航线网络那么稠密，他就用当程序猿时积累的小伎俩编了个小APP，先把感兴趣的航线找出来，然后虚开机票路演一下。五一假期有限，一趟环游的旅程最多只能有4站，然后想要个比较平均的行程，每一站间隔不要相差太远，以便安排作息。下面来看看小峰怎么完成这个小玩具。

一、数据模型

本例的数据来自 Neo4j GDS的教学案例，该文档中有载入数据建立图的Cypher语句，在此不再赘述，只看看它的数据模型，如图。机场航线是结点类型Airport到自身的HAS_ROUTE连接，然后Airport属于City、Region、Country、Continent，有到它们的连接，这是个加权有向图，HAS_ROUTE边的权重是机场之间的距离distance。该数据集有3503个机场和46389条航线，是个中小规模的网络。

二、Cypher查询语句

先看看查询国内机场环路的Cypher查询语句。这个语句返回国内机场指定跳数以内的环路。

1、先查询国内机场集合，集合targets用于保证环路中所有经过的结点都是国内的机场。它们通过[:IN_COUNTRY]类型边的code属性是否等于"CN"区分。

2、每条路径的源点和终点相同，因此构成一个环路。

3、使用可变长路径[r:HAS_ROUTE*2..4]来限定路径的长度在2~4跳之间。当然可以扩展到8~10跳，但计算量是指数上升的，4跳10秒内完成了，5跳大约3分钟，这取决于网络的规模与稠密程度。机场航线网络是比较稠密的网络，演示性质设到5跳以内，其它网络可能稀疏一点。

4、设定两个参数amplitude和threshold来过滤目标环路的特性，小峰要找的是权重稳定的强环路，threshold定义了环路中权重的均值阀值，均值小于阀值的就不看了。假定权重是机票的金额，小峰想舒服一点，太便宜的就不看了。amplitude定义了权重在均值上下波动的幅度，波幅超过amplitude的不是稳定的环路，对小峰来说也没有太大的意义。

这样，一条十几行的Cypher查询语句就找出了候选的稳定强环路。上图中的一条环路有5个结点5条边（5跳），权重是[830, 1058, 1177, 1177, 817]，均值是1011.8，最小值是817，最大值是1177，符合均值1000以上振幅20%以内的稳定强环路要求。

下图是该查询返回前3条路径的图，可以看到有几个结点处于单向环路中（这个数据集不完整，可能与实际情况有差异）。

三、Python参数化查询

定义了一个Python函数，从Python连接到Neo4j执行上面那条Cypher查询语句，返回所有从源点出发稳定强环路的边。这个函数用JupyterHub写的notebook调试，然后拷贝到Rstudio中的py程序文件中，在Shiny中由R语言程序调用，因为Neo4j没有官方的R语言Driver，GitHub上有几个个人开发的但不太好用。这个函数getRings(source, length, amplitude, threshold)定义了出发的机场、跳数、振幅与阀值4个参数，返回由环路上边的source、target、distance组成的dataframe，会有多条环路都经过的重复边，如果不想要重复边，加一行WITH DISTINCT flight就可以了。Neo4j可变长路径查询中的跳数不能作为参数传入（参阅 这篇文章），这里用拼接Cypher语句字符串的方式绕过，然后其它参数就象SQL一样用占位符传入。

四、Shiny APP

有关Shiny APP的介绍，请参阅我的 这篇文章。这里直接讲一下APP的几个R程序。

1.global.R。装入Python函数脚本，初始化全局变量国内机场列表。

2、server.R。observe（）函数监测airport、hops、amplitude、threshold四个reactive输入变量，调用前面的Python函数，把所有边组成的图以json格式返回给浏览器，由JavaScript处理。 3、ui.R。这个程序比较长，有400多行，先贴上R语言UI的部分，全文请等我的书。3D可视化用的是葡萄牙人 Vasco Asturiano开发的 3D Force-Directed Graph，底层支持的是 ThreeJS/WebGL 与 d3-force-3d、 d3-force，非常好用。不过是纯粹的JavaScript库，没有Shiny所需配套的render()函数与output()函数，我是通过 Shiny的JavaScript与R通信机制来解决问题的，这也是Shiny中集成缺乏内置Shiny支持的JavaScript库的通用解决方案。ui.R的主体是操作3D Force-Directed Graph的JavaScript，它通过WebGL用XML描述的SVG图来实现3D渲染的效果，由底层那几个JavaScript库支持，所以缩放很方便，精度也没有损失，只需用3D Force-Directed Graph的API操作即可。读者可以到 我的演示页面上体验一下，写过WEB程序的人应该都知道怎样看到剩下的源码了。Force Directed Graph是一种安排图上各个结点可视化布局的算法，让关系较密切的结点彼此靠近，边交叉的情况尽量少，从而有较好的可视化效果。另一种布局算法是 React Force Graph，Vasco Asturiano也为它开发了JsvaScript库，有2D、3D、VR、AR各版本，也可以使用。 五、运行效果

下面的视频演示了自动高亮显示选中结点间的边，展开折叠结点间的多重边，以及根据边的权重来调整高亮边动画中质点的数量与速度。对于城市间有多个航班的情况来说，展开多重边是个必要的功能。动画增加了第4维时间维，可以反映网络权重（流量）在时间维度上的变化，具体可以用JavaScript以固定的时间周期，比如1~2秒，按时间序列的顺序更新边上的权重数据，然后自动刷新视图。一共有3个sliderInput来选择跳数、权重波幅及权重均值，用sliderInput主要是有些手机上用textInput时有点问题，会不正确的激活Shiny的Reactive机制（主要是不同手机浏览器其输入框的实现不同，是兼容性的问题）。

六、小结

本例完成了一个交互式4D分析探索各种网络的工具原型，替换不同的Cypher查询语句就可以分析不同的网络模型，本例的稳定强环路只是其中一种可能的网络模型，比如做成下拉列表选择不同的查询（模型）就可以做成通用的工具。在Cypher中可以调用 Neo4j GDS中各种强大的图算法，如PageRank、社团发现、机器学习等，也可以调用自己编写的扩展算法，如最小树形图算法等，我在前面的文章以及我的书中都有详细的介绍。从本例可以看到图数据库与Cypher（将来应该是主要以Cypher为骨干的国际标准GraphQL）在关系分析领域的强大与方便，一个其它方案很难搞定的稳定强环路查找任务，用Cypher写个十几行的查询就搞定了，简单、方便、灵活，高度参数化，性能还很不错。从这个APP的源码也可以看到，开发集成也非常简单灵活。

所以个人觉得要好好利用开源软件的资源，不必一切从零开始。罗马不是一天建成的，软件是个需要积累的行业，成熟优秀的开源软件是经过人们长时间在实际应用中充分检验的。Linux和OpenStack、Android等也都是开源的，大家不都在用嘛。本例用了几个开源的软件平台，各层关键的图数据库Neo4j社区版、Shiny社区版、3D Force-Directed Graph/ThreeJS/D3都是开源的，中间各种R语言与Python软件包也都是开源的。如何利用好开源软件去做大做强国产软件和国内的信息产业，是大家可以好好深入思考与探讨的课题，与自主创新是事情的两个不同方面，并不冲突，更多的是互相激励互相促进。往往是摸着石头过河，实践会先行于理论，就像本例一样，先有一个可行的解决方案摆出来抛砖引玉，不管白猫黑猫，姓社姓资，姓中姓外，然后有志气的人们就对标去努力，争取自己做出来做好；非关键核心没有卡脖子危害国家安全风险的，不妨宽容一点开放一点，充分利用全球化的资源，在国际的大循环中交流合作，促进共同的进步。

在全球化时代，海纳百川，有容乃大，这其中的度，随着形势变化应该可以适当调整，但大门应该坚定的保持打开。