「ジャムのマッピング：グラフ理論を用いた交通分析」

Jam Mapping Traffic Analysis Using Graph Theory

都市のインフラストラクチャーをグラフ理論を用いて潜在的な重要ポイントを見つける方法を学びましょう

グラフ理論は、社会ネットワーク、分子生物学、または地理空間データなどの現実の問題に多くの応用があります。今日は、都市の道路配置を分析して、重要な通りや交差点を予測し、インフラストラクチャーの変更がどのように影響するかを紹介します。まずは基本から始めましょう。

グラフとその中心性指標

グラフは頂点とそのエッジの集合です：

エッジはノード間の接続を表します。エッジに方向がない場合、グラフを無向グラフと呼びます。無向グラフの現実の例としては、化学分子があります。ここでは、頂点が原子であり、結合がエッジで表されます。

ただし、エッジがuからvへ、vからuへ、または両方の方向に向かうかどうかの情報が必要な場合もあります。例えば、マークがアリスを好きだとしても、それが相互であるとは限りません（☹）。そのような状況では、エッジを順不同のタプルではなく、順序付けされたタプルとして定義することができます。

• 「OLAP vs. OLTP：データ処理システムの比較分析」
• Pythonによる地理空間データの分析
• MEMSセンサーデータの探索的分析

グラフ構造を使用することで、中心性指標を定義することができます。これは、以下の質問に対するメトリックです：

この頂点/エッジはグラフ内でどれくらい重要ですか？

そして、それには多くの方法があります。

グラフのコンポーネントの重要性を評価するための異なる方法

タスクによって、中心性の評価を異なるポイントから始めることができます。最も一般的な指標の一つは次のとおりです：次数、近接度、中間性。Zacharyのカラテクラブのグラフを使用してこれらについて議論します。それは異なるカラテクラブのメンバー間の関係を示しています。以下に、図を生成するために使用されたコードを見つけることができます。

次数中心性

最も基本的な中心性です。頂点にのみ定義され、頂点の次数（隣接する頂点の数）と等しいです。例えば、人間関係のグラフに戻って考えると、人々の友情の場合、このメトリックは次の質問に答えます

この人物はどれくらい人気がありますか？

グラフ内のパス

次の2つの中心性指標について、グラフ理論の知識にいくつかの概念を導入する必要があります。それらはすべて非常に直感的であり、エッジの重みから始まります。エッジに重みを追加することで、それらの間に違いを示すことができます。たとえば、これは交通グラフの場合には道路の長さである可能性があります。

グラフでは、AからBに移動するために通過する必要がある頂点のリストであるパスを定義することができます。パス内の連続する頂点は隣接しており、最初の頂点がAであり、最後の頂点がBです。パスの距離は、それに沿ったエッジの重みの合計です。AとBの間の最短パスは、距離が最も小さいパスです。

近接中心性

これらの新しい知識を持って、メトリクスに戻ることができます。次に紹介するのは、近接中心性です。これは、ノードがグラフの残りの部分に対してどれだけ近いかを示すものです。特定の頂点に対して、最短パスの平均の逆数として定義されます。このように、より短い平均パスはより高い近接中心性に対応します。

媒介中心性

媒介中心性は、グラフ内のどのノードが通過する交通にとって重要かを示す情報を提供します。交通量の多い広範な道路網がある都市を想像してみてください。各交差点がノードとなります。その中には日常の通勤において重要な接続点があり、他の交通の流れにほとんど影響を与えない袋小路もあります。前者は、交差点を通過する最短パスの割合として計算される高い媒介中心性スコアを持っています。

都市計画としてのグラフ

これで、グラフを記述し、分析するためのツールを持っているので、都市計画をグラフ形式に変換できます。そのためには、osmnxライブラリを使用してPythonでOpen Street Maps（OSM）をインポートします。作業の時間と効率を改善するために、追加のプロセスを適用する必要があります。

グジェゴジキはクラクフ市の18の地区の1つであり、モギルスキエとグジェゴジェツキエの2つの複雑なロータリーと多くの交差点があります。したがって、データエンジニアリングの潜在的な問題の多くを見ることができます。

グジェゴジキの行政区域。[©Google]

OSMリポジトリからデータをPythonグラフにインポートし、結果をプロットすることから始めましょう。

このグラフには問題があります – 何が間違っているか見つけることができますか？

私たちは、道路の単一セクションに複数のエッジを取得し、ほぼ3,000の「ジャンクション」をもつグラフを作成します。これは正しい表現を提供しません（道路の途中でUターンをすることはできませんし、すべてのノードが計算を遅くします）。この状況を修正するために、2つのジャンクション間の道路上のすべてのノードを削除することにより、グラフのトポロジーを簡素化します。OSMnxでは、これに対してox.simplify_graph()という関数があります。

さらにもう1つの注意点があります。ほとんどの道路には2つのエッジがあります。一方は通行方向ごとにあります。そのため、交差点ごとに複数のノードがあり、これは望ましくない動作です。ジャンクションにいて、左折をしようとしても左折専用レーンがない（または既に満員）場合を想像してください。左折ができない限り、他の車はブロックされます。現在のグラフでは、これは真実ではありません。左折は2つの独立したノードで構成されており、1つは左折、もう1つは対向車線の横断を表しています。これはそれらが2つの独立した操作であるかのように示唆していますが、実際にはそうではありません。

そのため、交差点を統合することにします。つまり、お互いに近い複数のノードを1つに結合します。統合半径は、交差点の複数の部分を1つに統合するのに十分大きくなるように選択しますが、ラウンドアバウトは複数のノード構造のままにし、部分的にのみブロックされる可能性があるためです。これにはosmnxのox.consolidate_intersections()関数を使用します。

これらの操作の後、分析の準備がほぼ整いました。最後の注意点は、クラクフの自治体の境界です。多くの人々が隣接する町から移動するため、グラフの分析にはグラフ内のデータのみが含まれているため、これらのエリアを含める必要があります。次の章では、それを行わなかった場合の影響を紹介します。そして、ここが私たちのグラフです：

このマップを生成するために使用されたソースコード、および次の章で使用されるすべてのグラフィックは、このjupyterノートブックにあります。

道路レイアウトの媒介中心性

このケーススタディでは、道路交通の推定のための媒介中心性の測定に焦点を当てます。将来的には、グラフ理論の他の技術、GNNの使用（グラフニューラルネットワーク）などに拡張されるかもしれません。

道路レイアウトのすべてのノードとエッジの媒介中心性の測定を計算するため、NetworkXライブラリを使用します。

グラフ上の多くの道路があるため、交通にとって最も重要なコンポーネントがどれかを見るのは困難です。グラフの中心性測定の分布を見てみましょう。

これらの分布を使用して、重要でない交差点や道路を除外することができます。以下の閾値値を持つ各々の上位2％を選択します：

• ノードの場合、0.047
• エッジの場合、0.021

次に示されているように、媒介中心性によって最も重要な道路セグメントは次のとおりです：

• クラクフの環状道路であるA4高速道路とS7（クラクフには環状道路の北部がないことに注意）
• 2番目の環状道路の西部とA4への接続
• 3番目の環状道路の北部（欠落している北部の環状道路の代替）
• クラクフの北東部と2番目の環状道路を結ぶNowohucka通り
• 市中心部から南東部の高速道路へとつながるWielicka道路

これらの情報をGoogleマップのクラクフの実際の交通地図と比較してみましょう：

私たちの洞察が交通レーダーの結果と関連していることがわかります。そのメカニズムは非常にシンプルです – 媒介中心性の高いコンポーネントは、グラフ内のほとんどの最短経路を通勤に使用するものです。車の運転手が最適な経路を選択する場合、交通量が最も多い道路と交差点は媒介中心性が最も高いものとなります。

次に、グラフのエンジニアリングの最後のパートであるグラフ境界の拡張に戻りましょう。都市の境界のみを分析に使用した場合に何が起こるかをチェックできます：

クラクフの重要なコンポーネントであるA4高速道路は、全体のグラフで最も低い中心性測定を持っています！これは、A4が都市の郊外にあるため、その交通のほとんどが外部から来るため、媒介中心性にこの要素を含めることができないためです。

レイアウト変更が交通に与える影響を分析するために媒介中心性を使用する方法

グラフ分析の別のシナリオを見てみましょう。道路の閉鎖（例：事故による）が交通にどのような影響を与えるかを予測したいとします。媒介中心性の測定値を使用して、2つのグラフ間の違いを比較し、中心性の変化を調べることができます。

この研究では、一般的な出来事であるA4–7高速道路セグメントの交通事故をシミュレートします。事故によりセグメントが完全に閉鎖されます。

A4–7セグメントをグラフから削除し、中心性測定を再計算することで、新しい道路ネットワークを作成します。

中心性の分布を見てみましょう：

これはまだ元のものに非常に似ていることがわかります。中心性測定の変化を調べるために、残差グラフを計算します。ここで、中心性測定は元の道路レイアウトと事故後の差です。正の値は、事故後の中心性が高いことを示します。A4–7号高速道路セグメントなどのグラフのいずれかに欠落しているノードやジャンクションは、残差グラフに含まれません。以下は残差の測定分布です：

再び、影響を受けた上位2%のストリートとノードをフィルタリングします。今回の閾値の値は：

• ノードに対して0.018、
• エッジに対して0.017。

このように、ベルトウェイの分裂部を市中心部に接続する道路の増加が見られます。最も大きな変化は、市の西側にあるヴィスワ川上の2つの橋のうちの1つを含む2番目の環状道路に見られます。

道路ネットワークにおけるグラフ中心性分析ではできないこと

グラフ分析中に考慮できないことがいくつかあります。この分析で見ることができた最も重要な2つは次のとおりです：

• グラフ中心性分析では、ノード間のトラフィックの均一な分布を前提としています。

これはほとんどの場合には誤りです。村や都市は異なる人口密度を持っています。ただし、隣接する村に住んでいる人々の数が多い場合、市中心部に住んでいる人々と比較して、通勤手段として車を選ぶ人々の割合が高くなるなど、これを低減する他の効果もあります。

• グラフ分析は、グラフ内に存在するもののみを考慮に入れます。

これは提供された例では見るのが難しいですが、特にクラクフ外の人にとってはそうです。では、ザコピアンカを見てみましょう。これは、市中心部とクラクフ南部のほとんどの自治体を結ぶ主要な交通動脈であり、また、全国を横断するDK7（国道7号）の一部でもあります。

クラクフのDK7道路の典型的な交通量を中心性測定と比較すると、まったく異なります。平均媒介中心性は約0.01であり、上位2%の閾値よりも2倍小さい値です。しかし現実には、最も混雑している区間の1つです。

まとめ

グラフ理論とその分析は、この研究で示された交通分析など、複数のシナリオで応用されています。グラフ上の基本的な操作やメトリクスを使用することで、シミュレーションモデルを構築するよりも短時間で貴重な洞察を得ることができます。

この分析全体は、数十行のPythonコードを使用して実行することができ、道路のレイアウトに限定されることはありません。また、グラフ理論から他の分析ツールに非常に簡単に移行することもできます。

この方法には、一様な交通分布に関する仮定やグラフ構造に制限される範囲など、欠点もあります。

この研究で使用されたコードが含まれるGitHubリポジトリはこちらから見つけることができます。

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!