Understanding road network dynamics: Link-based topological patterns
Susana Freiria, Bernardete Ribeiro, Alexandre O. Tavares.,
Journal of Transport Geography, Volume 46, June 2015, pp. 55-66
2015/06/19 理論談話会

M2芝原まとめると…
n ネットワーク指標はそれぞれ表す特徴が異なる．
n いろいろ混ぜてクラスター分けを行う手法を適用．
n その成分比からクラスターに何が効いているか分析．
n 高速道路よりも下道の方が，ネットワーク寸断に効く道がある．
n むしろ切った方がネットワーク全体には良い道もある．

2015/06/19 Understanding road network dynamics: Link-based topological patterns

2０．Contents
1. Introduction
2. Literature review
3. Methodology
3-1．Structural characterizaion of the network
3-2．Biclustering technique3-3．Mean geodesic distance variation due to link interruptions

4. Case study
5. Results
5-1．Application of biclustering technique5-2．Mean geodesic distance variation due to link interruptions

6. Discussion
7. Conclusion
2015/06/19 Understanding road network dynamics: Link-based topological patterns

3

１．Introductionn 災害によるネットワークの寸断を想定– もっとも重要な道路を特定したい．

n ネットワークの構造的特徴から重要な街路の位置を特定する– 交通量が多いから切られると弱いという分けでもない．
（迂回路が多く接続しているとか）– ネットワークの指標が表す意味はそれぞれ異なっている．
（次数と媒介中心性など）n ネットワーク指標を重ね合わせて評価しよう．

2015/06/19 Understanding road network dynamics: Link-based topological patterns

4

３．Methodologyn 分析の流れ
1. ネットワークの構造を表す指標の設定
2. Biclustering tecniqueの適用
3. リンク寸断時のgeodesic distanceの算出，Biclusterとの比較

2015/06/19 Understanding road network dynamics: Link-based topological patterns

5

３．Methodology
1. ネットワークの構造を表す指標の設定n 次数5のリンクは次数3のリンクより大きい．次数だけでは全体の連結性は表せない．．．
n どの指標が道路の連結性のどの部分を表現できるかを想定すべき．
1. リンクとリンクの接続関係に直す．
2. 指標を計算し，何を評価しうるかを想定する．

2015/06/19 Understanding road network dynamics: Link-based topological patterns

6

３．Methodology
1. ネットワークの構造を表す指標の設定
都市空間Primal graphDual graphSyntaxnSpace
本研究では同じ街路に同じIDを与えるnamed-street
直線をリンクとし，approachを用いる．
その接続を見る手法

named-street
approach
同じ名前の通りをつなぐ手法

n ICNモデル
ICNモデル（Porta et al., 2006）は逐次更新された歴(Porta et al., 2006)
史的都市では不自然な結果になってしまう
リンクの接続角度（Masucci et al., 2014）から分割する手法
2015/06/19 Understanding road network dynamics: Link-based topological patterns

7

３．Methodology
1. ネットワークの構造を表す指標の設定n 7つの指標を考える（目的に応じて変えるべき．実際に効いていたのは1.α index，3.Bonacich Power，6．Degreeの3つ）．
1.
2.
3.
4.
5.
6.
7.

α index
Betweenness
Bonacich Power
Cluster Index
Cut level
Degreefragmentation

2015/06/19 Understanding road network dynamics: Link-based topological patterns

8３．Methodology
1. ネットワークの構造を表す指標の設定
n α index：ネットワーク内のcircuitの多さを示す

αi =ノードi を起点・終点とするcircuit数
ノードi を起点・終点とする，完全グラフのcircuit数

l − n +1=
2n − 5l ：リンク数
n ：ノード数

cycle

circuit2015/06/19 Understanding road network dynamics: Link-based topological patterns

9

３．Methodology
1. ネットワークの構造を表す指標の設定
n Bonacich Power：中心性の高いノードにつながるノードが高い中心性を持つ，とする指標n Degree：ノードi につながるリンクの数．

BPi = α (I − β R) R1

di = ∑ mij

α ：スケールを合わせるための係数
R ：グラフの隣接行列
I ：単位行列β ：隣接行列の重み付けパラメータ
1 ：全要素1の行列

mij ：隣接行列のij成分−1j2015/06/19 Understanding road network dynamics: Link-based topological patterns

10

３．Methodology
1. ネットワークの構造を表す指標の設定
n Betweenness：ネットワーク内の最短経路に位置する割合

g jk (ni )CB (ni ) = ∑j<kg jk
g jk (ni ) ：ノードj からノードk への最短経路数のうち，g jk

ノード ni を通る経路数：ノードj からノードk への最短経路数

2015/06/19 Understanding road network dynamics: Link-based topological patterns

11

３．Methodology
1. ネットワークの構造を表す指標の設定
n Cluster Index：ノード周辺のリンクのつながり具合を表す指標

MiCi =ki (ki −1) / 2
M i ：ノードi のサブグラフに含まれるリンク数
ki ：ノードi の次数

2015/06/19 Understanding road network dynamics: Link-based topological patterns

12

３．Methodology
1. ネットワークの構造を表す指標の設定
n Cutpoints：コミュニティAとBのつながりを示す．

cut(A, B) =

∑ w

ij

i∈A, j∈Bi ∈ A, j ∈ B ：コミュニティ

wij：ij 間にリンクがあれば1，なければ02015/06/19 Understanding road network dynamics: Link-based topological patterns

13

３．Methodology
1. ネットワークの構造を表す指標の設定
n Cutpoints：つながっていないノードペアのネットワー
ク全体における比率

Fi =rij2∑ ∑ rijij<in(n −1)：ノードi からノードj に到達できれば1，できなければ02015/06/19 Understanding road network dynamics: Link-based topological patterns

14

３．Methodologyn Degreeはリンクの接続の強さを扱えない．全て等価に扱っている．
n Bonacich Powerはノードの重要性を表すが，重要な街路に接続する街路が重要であるという決め方．代替経路があれば，リンクが切れても大丈夫だが，その評価には使えない．
n α indexは全体のネットワーク連結性（代替経路の存在）を評価している．
n ケーススタディでは，これらの指標の多重共線性も確認する．

2015/06/19 Understanding road network dynamics: Link-based topological patterns

15

３．Methodology
2．Biclustering tecniqueの適用
n 道路のコミュニティ分割（行列の列成分）n 道路の特徴（行列の行成分）を同時に決定する．
n n列（道路番号），m行の特徴量n 列を近い関係のデータを分割する．
n Additive-relatedとmultiple-relatedの2種類がある．本研
究ではadditive-relatedを用いる．

2015/06/19 Understanding road network dynamics: Link-based topological patterns

16

３．Methodology
2．Biclustering tecniqueの適用
n n個のノードそれぞれにm個の属性があるとする．

i1
1

j：リンク番号：ノード番号n

R = {1…n}C = {1…m}xijX(I, J )m
2015/06/19 Understanding road network dynamics: Link-based topological patterns

X∈Rn*m17

３．Methodology
2．Biclustering tecniqueの適用
n 4つのパラメータを設定．
1. Noise threshold ε
2. Minimum percentage of rows
Nr
3. Minimum numbers of columns
Nc
4. Maximum bicluster overlap in percentage

Po

2015/06/19 Understanding road network dynamics: Link-based topological patterns

18

３．Methodology
2．Biclustering tecniqueの適用

Br = (I e, J r )r = 1,..., tn MSRS（Mean Square Residue Score）：低いほど良い

12MSRS =(x−x−x+x)∑ijiC
Rj
RCnm i∈R, j∈CMSRS ≤ ε なら，正しいBicluster

xiC =1xij∑m j∈Cx RC =x Rj =1xij∑
n i∈R1xij∑nm i∈R. j∈Cn ACV（Average Correlation Value）：高いほど良い$∑(& i, j∈R CorRij − m ∑k,l∈C CorCkl − n &ACV = max %,)n(n −1)m(m −1)&'&*CorRij CorCkl ：列ij 間，行kl 間の相関係数
2015/06/19 Understanding road network dynamics: Link-based topological patterns

19

３．Methodology

2015/06/19 Understanding road network dynamics: Link-based topological patterns

20

2015/06/19 Understanding road network dynamics: Link-based topological patterns

21

３．Methodology
2．Biclustering tecniqueの適用
n Biclustering Argorithm

2015/06/19 Understanding road network dynamics: Link-based topological patterns

22

３．Methodology
2．Biclustering tecniqueの適用
n Biclustering Argorithm

2015/06/19 Understanding road network dynamics: Link-based topological patterns

23

３．Methodology
2．Biclustering tecniqueの適用
n あと重回帰分析もやりました．

y = β0 + β1 x1 + β2 x2 +!+ βk xk + ε

SSR
R =2
∑(yi − y)2

2015/06/19 Understanding road network dynamics: Link-based topological patterns

24

３．Methodology
3．リンク寸断時のgeodesic distanceの算出
n 従来の評価は旅行時間増加やトリップ長増加が多い．
n 本研究ではgeodesic distanceを用いる．

GinG jn
Gl =SPijGl ：ノードij で表されるリンクlの平均最短経路距離
Gin ：ノードi 発，任意ノード着の最短経路距離の合計
G jn ：ノードj 発，任意ノード着の最短経路距離の合計
SPij ：ノードij 間の最短経路数

2015/06/19 Understanding road network dynamics: Link-based topological patterns

25

３．Methodology
3．リンク寸断時のgeodesic distanceの算出∑∑ G GG =∑ ∑ SPi

in

j

jnoi

ij

j

∑∑ G GG =∑ ∑ SPi

j

ina

ai

j

original scenarioでの平均測地距離

jnalink aが切れたときの平均測地距離ij

La = Ga − L0link aがないときの全体の距離増加分

2015/06/19 Understanding road network dynamics: Link-based topological patterns

26

３．Methodology
3．リンク寸断時のgeodesic distanceの算出
n BiclusterとMean geodesic distanceを比較．

x = a + by

x：biclusterごとの平均距離増加分
by：biclusterのregression resultx = a + bbp

bbp：biclusterごとの平均Bonacich Powerx = a +α

α：biclusterごとの平均alpha index

x = a+dd：biclusterごとの平均次数

当てはまりを決定係数から判断する．
2015/06/19 Understanding road network dynamics: Link-based topological patterns

27

４．Case studyn Coimbra in Portugaln 総道路延長：509kmn 様々な道路で構成される都市圏．

2015/06/19 Understanding road network dynamics: Link-based topological patterns

28

５．Resultsn 結果．24%のリンクがクラス分けされずに残った．似たような特徴を持っていないため．
n 重回帰から，alpha index:100%，Bonacich Power：44%，Degree：30%と出た．

2015/06/19 Understanding road network dynamics: Link-based topological patterns

29

５．Resultsn bicluster4に最重要のリンクが含まれている．平均値が全行で最も高い．全リンク長の5%ほどしかなく，ネットワークが集中している．
1.
2.
3.
4.

Noise threshold
Minimum percentage of rows
Minimum numbers of columns
Maximum bicluster overlap in percentage

ε = −2N r = −5
Nc = 5
Po = −10

2015/06/19 Understanding road network dynamics: Link-based topological patterns

30

５．Results

2015/06/19 Understanding road network dynamics: Link-based topological patterns

31

５．Resultsn bicluster3の道路は付随的な道路．自治体の分割で生じることが多い．
n 高速道路はヒエラルキーの頂点にあるが，重要なbiclusterには含まれていない．

2015/06/19 Understanding road network dynamics: Link-based topological patterns

32

５．Resultsn bicluster4のリンクを切ると57m増える．
n bicluster3のリンクを切るとむしろスムーズになる．
（孤立した道が多い？）

2015/06/19 Understanding road network dynamics: Link-based topological patterns

33

６．Conclusionn ネットワークの構造的特徴量を重ねて評価する手法を提案．
n Biclustering 手法を適用．
n その成分比と，geodesic distanceとの関係から切った方が良い道もある．

2015/06/19 Understanding road network dynamics: Link-based topological patterns

34