论文：TrajGraph: A Graph-Based Approach to Studying Urban Network Centralities Using Taxi Trajectory Data
作者：Xiaoke Huang, Ye Zhao, Jing Yang, Chong Zhang, Chao Ma, Xinyue Ye
发表：VAST 2015
介绍
出租车轨迹在一定程度上反应了整个城市道路的动态交通信息，我们可以从出租车轨迹观察到真实的交通流以及城市级别的交通模式。为了反应道路结构，过去的研究往往采用图模型的方法，但是他们只考虑的静态的路网数据，没有使用真实的交通数据，进几年来的工作也不能反应城市范围的路网并且支持交互式分析。为此，作者提出了 TrajGraph。TrajGraph 同时结合了路网结构和真实的出租车数据。为了支持交互式分析，TrajGraph 做了空间简化，使用了图分割算法，把街道级别的图模型转换为区域级别的图模型。同时，为了研究分析城市中不同区域在交通中的重要程度，作者基于 TrajGraph 计算了图的中心性，包括 Pagerank 和 betweenness。这些中心性由三个联动的视图：结点连接图、地图和时间信息图可视化展示出来，用户可以交互式地分析探索城市交通的模式。
构造图
首先，基于路网和出租车轨迹信息，我们可以构造一个图模型。如下图，我们把每一个街道转换为一个结点，在街道间的转换就是一条边。比如，有一辆出租车从道路 D 行驶到道路 F，那么在对应的图模型中就会生成结点 D 和 F 以及边 DF。这是考虑了一些道路上的约束，比如不能从道路 C 行驶到道路 A，这样的约束很容易在这样的图模型中表示出来。边的权重统一设为 1，结点的权重可以有四种，路段长度、出租车数量、平均通行时间和平均速度。前一个反应了道路结构，后三个都是反应了交通信息。
这样产生的图模型会有 37634 个顶点和 1512691 条边，虽然这个数据量对计算机来说不大，但是计算图的中心性需要耗费大量的时间，用户无法进行实时交互，并且过多的元素无法进行有效地可视化分析。因此需要做一些空间简化，使用了图分割算法 METIS，把原图分割成 K 个块，在保证每个块的权重近似的情况下，最小化块之间的连接边的数量，把街道级别的图模型转换为区域级别的图模型。
计算图的中心性
为了研究分析城市中不同区域在交通中的重要程度，作者计算了两种中心性，基于出租车数量权重计算 Pagerank 和基于平均通行时间计算 betweenness。如此计算得到的含义是：越高的 Pagerank 值表明，这块区域是出租车采用的到其他地方的中心，比如市中心；越高的 betweenness 代表是最快路径上的主干道，比如隧道、大桥等。
可视化设计
为了展示以上的中心性，如下图，整个系统包括一下三个联动视图：结点连接图、地图和时间信息图。结点连接图中结点处于街道区域的地理中心，整个图反映了路网结构。数字代表了一个编号， 颜色代表了归一化得中心性或者权重的数值，因为我们对高中心性和低中心性的区域更感兴趣吗，所以使用了两种颜色，红色代表数值高，蓝色代表数值低。用户点击结点，可以看到在地图上对应的区域，颜色也对应于某一种中心性或者权重，rose chart 展示数值在一天中的变化。在时间信息图中，我们可以查看这些数值在时序上的变化，可以同时比较多个区域的数值变化。
案例分析
图（2）展示了一天中 betweenness 数值在路网中的分布，我们看到 95 号结点的颜色比较深，所以点击 95 把它的信息展现在地图上来研究。图（4）中，我们发现 95 号结点是在一座山的背面，这座山对城市交通研究很重要，因此我们想探索他与周围道路的关系。然后我们查找他周围的区域，比如山南面的区域 36 号结点，95 号结点代表的区域和 36 号的区域由一条隧道连接起来。通过图（3）我们看到这两块区域的 betweenness 的值得变化是一致的，说明他们是连接深圳南北两部分很重要的部分。但是他们的 Pagerank 值就有很大不同（图（5）），在 6 点左右结点 36 的 Pagerank 值比较高而 95 的值比较低。我们把地图上的颜色编码改为通行时间，我们可以看到 95 处通行时间都比较高，可能是有交通拥堵，因此出租车司机会避免进入这块区域，所以这里不是一个中心，pagerank 值比较低。相反，我们看到 36 处通行比较流畅，所以出租车司机会把这里作为通行的枢纽，Pagerank 值比较高。通过这个案例，我们认为区域 95 需要在城市规划交通控制上找一些对策。
总结
这个工作提出的 TrajGraph 结合了路网信息和轨迹信息，并且使用了图上的一些概念比如中心性来反应局部区域在整个交通网络中的作用。用图的形式来研究轨迹是一个很好的思路，作者提出未来的工作可以考虑更多地基于图的算法，比如最小生成树或者社团分析等。
✉️ minfeng_zhu@zju.edu.cn