2022/09/25#2 BinN Research Seminar

Characteristic of transport network basedon the eigenvalue analysis
固有値解析に基づく交通ネットワークの特性分析

熊本⼤学 くまもと⽔循環・減災研究教育センター
Kumamoto University
Center for Water Cycle, Marine Environment and Disaster Management
安藤 宏恵 (Hiroe ANDO)
hiroeando@kumamoto-u.ac.jp

Eigenvalue-based evaluation for transportation network
Eigenvalue analysis for transportation network 固有値解析を⽤いた交通ネットワークの分析
Fiedler
vector :Algebraic connectivity defined by the second smallest eigenvalue of theLaplacian matrix (degree matrix - adjacency matrix), and the corresponding
eigenvector (Fiedler vector) to evaluate road network connectivity
Laplacian ⾏列の第⼆最⼩固有値によって定義される代数的連結度，それに対応する固有ベクトルを⽤いて道路ネットワークの連結性，接続性を評価

Ex. 中南ら(2018), Bell et al. (2017)
Wang and Van Mieghem (2008) studied on improving network connectivity by adding links
using algebraic connectivity index.

Directed network
Eigenvector
centrality :Port accessibility is evaluated by eigenvector centrality indices for delivery cargo network.
(Wang and Cullinane, 2008)
物流ネットワークのアクセシビリティ評価

Leadingeigenvalue :Identification of single additional links that contribute significantly to improve port network
connectivity (Cheung et al, 2020)
港湾ネットワークの連結性向上のための追加航路の特定

2

Topological analysis
Typical examples of topological based road network evaluation- Network efficiency• Latora and Marchiori (2001) defined a measure of information exchange which is the average
across all node pairs of the reciprocal of distance.
全ノード間距離の逆数の平均によってネットワーク効率性を定義• Mattson and Jenelius (2015) presented a global efficiency index, which indicates how direct theconnections are between all node pairs by comparing the Euclidean distances with the shortest
network distances.
ユークリッド直線距離に基づく最短距離とネットワーク効率性を⽐較することにより，グローバル効率性指標を定義- Node centrality• A measure of how important each node is on the network.
各ノードがネットワーク内でどれほど重要であるかの指標• There are several centrality indicators depending on what is defined as “important”.
何をもって重要とするかによって，さまざまな中⼼性指標が定義されている

Ex. Degree centrality (Proctor and Loomins, 1951), Closeness centrality (Beauchamp, 1965),
Eigenvector centrality (Bonacich, 1972), Betweenness centrality (Freeman, 1977)

3

Eigenvector Centrality (Bonacich, 1972)• If a node adjacent to the important nodes, the centrality of that node is also large.
重要なノードと接続するノードが隣接している場合，そのノードの中⼼性も⼤きくなる• Important node pushes up the centrality of adjacent nodes.
重要なノードは隣接ノードの中⼼性を増加させる

𝐱 𝑡 + 1 = 𝐀𝐱 𝑡
%𝑥! 𝑡 + 1 = ( 𝐴!" 𝑥" 𝑡"#$𝑥 : the magnitude of effect𝐀 : adjacency matrix
𝑁: the number of nodes

1st iteration :𝑥$ 𝑡 + 1
𝑥% 𝑡 + 1=𝑥& 𝑡 + 1
𝑥' 𝑡 + 1

00
1
1

100
1

100
1

1
1
10

1

2

3

4𝑥$ 𝑡
𝑥% 𝑡
𝑥& 𝑡
𝑥' 𝑡

This iteration converges to the largest eigenvalue 𝜆!"#𝐀𝐱 = 𝜆&'( 𝐱𝑥! > 0 1 ≤ 𝑖 ≤ 𝑁𝜆!"# : the largest eigenvalue of 𝐀Eigenvector centrality is obtained by the eigenvector corresponding
to the largest eigenvalue of the adjacency matrix.

4Construct of weighted network
Type of network- Directed network 有向グラフ• Each link has a direction. Each link connects from tail node to head node.
各リンクが⽅向を持つ- Weighted network 重み付きグラフ• Each link have element as weight.
各リンクが重みを持つ

Link1

Directed and weighted adjacency matrix A

11.5

2Origin

Destination𝑎() =0 1.5 00 00
2 000 2.5 1.5

𝑤* if 𝑒 = (𝑖, 𝑗) ∈ 𝐄0 otherwise

3000Link2

Link3

23

2.5

3

1.5

4

Link5

Link45

Road Network Evaluation by Eigenvector Centrality- Set the various feature values as weight for each link to consider the traffic function.
- Evaluate the effect based on each weight setting by weighted eigenvector centrality.
1 1

𝐀𝐱 = 𝜆𝐱
weight value of the link from node 𝑖 to node 𝑗𝑎!" = #0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
0.419
1

1.5

0.645
20.392
1

1.5

0.106
20.5

2.5
32

1 3
0.389
12 1

1.5

1.5

1.5

1

2.5
14 1
0.089
2

𝐀=
000.5
2.5
0.393
1

1.5
00
2.5
1.5

200
1.5

3
1
100.0942

2.5 to normalise for0.network
2.5
2.5
2.5
0.
- 0.Iterate
size
0.
2.5
2.5to avoid divergence.
2.5
2.5
5
5
5
5
1
1
1
1-2 This iteration
converges
tothelargest
eigenvalue.
Theeigenvector
corresponding
222
3
3
3
3
largest eigenvalue should be all positive. (Perron-Frobenius theorem)
1.5
3
10.09740.4191.5
3
10.15940.3431.5
310.13940.3831.5
310.14540.368 6

Comparison with other centrality measures
Target centrality measures
Centrality measure

Reference

Formulation

Degree Centrality

Proctor & Loomis(1951)

Closeness Centrality

Beauchamp(1965)

𝑥! =𝑛∑" 𝑑!"The mean distance from a node to other nodes using theshortest path through a network between two nodes.

Eigenvector Centrality

Bonacich(1972)

𝑥! = ( 𝐴!" 𝑥"

A node's importance in a network is increased by having
connections to other nodes that are themselves important.

Betweenness Centrality

Freeman(1977)!
𝑛$%𝑥! = ($% 𝑔$%

The extent to which a node lies on the shortest paths
between other nodes.

#𝑥! = ( 𝑎!"""Definition

The number of links connected to the node.

7

Comparison with other centrality measures
A small-scale road network in Gifu City

Degree Centrality

Closeness Centrality- The similarity between CC and EC.

Betweenness Centrality

DegreeCentrality

DCはバイパス道路の影響が強い- EC includes the characteristics ofboth DC and CC.
ECはDCとCCの両⽅の特性を持つ

Eigenvector Centrality
Capacity weighted

Table. Spearman's rank correlation

CCとECの相関が強い- DC is significantly effected by bypassroad.

Eigenvector Centrality

ClosenessCentralityBetweenness
Centrality

Eigenvector
Centrality

Degree Centrality

1.0000

Closeness Centrality

0.50041.0000Betweenness Centrality

0.55540.51321.0000Eigenvector Centrality

0.57170.76790.35461.0000Eigenvector Centrality
Capacity weighted

0.49740.92630.46460.8405

Eigenvector
Centrality
Capacity weighted

1.0000The similarity suggests the big advantage of eigenvector centrality since the calculation ofshortest pass is not needed.

8Classification of functional and geographicalcharacteristics of road networks

Weight settings on eigenvector centrality
Classification ofChallenges
The evaluation ofroad improvement

Characterised theregion on the roadnetwork

The usage situationof road network

WeightEquation

Eigenvector Centrality

Capacity𝑤& = 𝐶&The magnitude and strength of movement ability on road network. Connectivity
considering the ease of link disruption based on the traffic capacity.

Road area

𝑤& = 𝐿& 𝐶&Contribution for the supply performance by the road improvements.

Speed

𝑤& = 𝑆&The distribution of road rank connectivity.
Connectivity distribution of links with high and low speed limits.

Capacity𝑤& = 𝐶&The magnitude and strength of movement ability on road network. Connectivity
considering the ease of link disruption based on the traffic capacity.

BPR
function

𝑤! = 𝑡"#$1 + 𝛼𝑃!

The distribution of road rank connectivity.
Connectivity distribution of links with short and long travel time consideringcongestion.

Travel time

𝑤& = 𝑡&

The distribution of road rank connectivity.
Connectivity distribution of links with short and long travel time.

Distance

𝑤& = 𝐿&The spatial density of network by the connectivity of length on each link.

Congestionrate

𝑤& =𝑉&𝐶&Concentration and distribution of crowded roads.

Trafficvolume

𝑤& = 𝑉&Concentration and distribution of traffic volume.

10

Weight settings on eigenvector centrality
Classification ofChallenges
The evaluation ofroad improvement

Characterised theregion on the roadnetwork

The usage situationof road network

WeightEquation

Eigenvector Centrality

Capacity𝑤& = 𝐶&The magnitude and strength of movement ability on road network. Connectivity
considering the ease of link disruption based on the traffic capacity.

Road area

𝑤& = 𝐿& 𝐶&Contribution for the supply performance by the road improvements.

Speed

𝑤& = 𝑆&The distribution of road rank connectivity.
Connectivity distribution of links with high and low speed limits.

Capacity𝑤& = 𝐶&The magnitude and strength of movement ability on road network. Connectivity
considering the ease of link disruption based on the traffic capacity.

BPR
function

𝑤! = 𝑡"#$1 + 𝛼𝑃!

The distribution of road rank connectivity.
Connectivity distribution of links with short and long travel time consideringcongestion.

Travel time

𝑤& = 𝑡&

The distribution of road rank connectivity.
Connectivity distribution of links with short and long travel time.

Distance

𝑤& = 𝐿&The spatial density of network by the connectivity of length on each link.

Congestion
rate𝑤& =𝑉&𝐶&Concentration and distribution of crowded roads.

Traffic
volume𝑤& = 𝑉&Concentration and distribution of traffic volume.

11

Eigenvector Centrality by Each Traffic Feature Values

1 : Top 20% of Rank
2 : 20% - 40%
3 : 40% - 60%
4 : 60% - 80%
5 : 80% - 100%12

Factor Analysis
To identify the potential common factors.

𝐘 = 𝚲𝐟 + 𝛆
𝐘: The set of observed variables, 𝚲: The set of factor loadings of each variable and eachfactor, 𝐟: The set of common factors, 𝛆: The set of unique factors- Three common factors are extracted by factor analysis

Traffic Demand Factor

Road Sparsity Factor

Road Rank Factor

13Cluster classification- Cluster 1【472 : 26%】“Rural part cluster”
Gero City, Ena City, the north part in Shirakawa town andHida City,- Cluster 2【372 : 21%】“Western urban part cluster.”
Oogaki, Motosu, Ibigawa, Kaizu.
- Cluster 3【140 : 8%】“Northern urban part cluster”
Takayama City
- Cluster 4【678 : 38%】“Central urban part cluster”
Gifu, Kakamigahara, Minokamo, Seki, Gujo
- Cluster 5【121 : 7%】“Expressway cluster”
Nodes are mainly located along the expressway

Result of factor analysis by using eigenvector centrality classified the road network
by functional and geographical characteristics.
ECに基づく因⼦分析により，道路ネットワークを機能的・地理的特性によって分類14

Cluster classification
Cluster

The numberof nodes

Percentage

Average factor score 1“Traffic demand”

Average factor score 2“Road sparsity”

Average factor score 3“Road rank”

1

472

26%

-0.3760.348-0.830

2372

21%

0.378

-1.267-0.729

3

140

8%

0.247

2.252

-0.5414678

38%

0.4790.060

0.861

5121

7%

-2.665-0.402

1.281

Average factor score in each cluster- Cluster 2【372 : 21%】“Western urban part cluster.”
Oogaki, Motosu, Ibigawa, Kaizu.

Traffic demand : High demandRoad sparsity : Dense
Road rank : Low
Large capacity roads are insufficient despite high demand and dese networks. For road
improvement, capacity expansion of existing links is effective.
需要が⾼いにも関わらず⼤容量の道路が不⼗分，ネットワーク構造は発達している．既存リンクの容量拡⼤が有効．

15Relationship between road improvement
and usage in the long termWeight settings on eigenvector centrality
Classification ofChallenges
The evaluation ofroad improvement

Characterised theregion on the roadnetwork

The usage situationof road network

WeightEquation

Eigenvector Centrality

Capacity𝑤& = 𝐶&The magnitude and strength of movement ability on road network. Connectivity
considering the ease of link disruption based on the traffic capacity.

Road area

𝑤& = 𝐿& 𝐶&Contribution for the supply performance by the road improvements.

Speed

𝑤& = 𝑆&The distribution of road rank connectivity.
Connectivity distribution of links with high and low speed limits.

Capacity𝑤& = 𝐶&The magnitude and strength of movement ability on road network. Connectivity
considering the ease of link disruption based on the traffic capacity.

BPR
function

𝑤! = 𝑡"# 1 + 𝛼𝑃!

Travel time

𝑤& = 𝑡&

The distribution of road rank connectivity.
Connectivity distribution of links with short and long travel time.

Distance

𝑤& = 𝐿&The spatial density of network by the connectivity of length on each link.

Congestionrate

𝑤& =𝑉&𝐶&Concentration and distribution of crowded roads.

Traffic
volume𝑤& = 𝑉&Concentration and distribution of traffic volume.

$The distribution of road rank connectivity.
Connectivity distribution of links with short and long travel time consideringcongestion.

17

Multiple-year data
The number of nodes and links in road networks by year

- Target area : Gifu Prefecture, JapanØ 10,620 ㎢ in size and included mountainous andurban areas.
- Target years : 1990, 1999, 2005, 2010
Ø The road networks have been improved year-on-year

1990

1999

2005

2010

Node1727

1770

1791

1793

Link
(Ordinary roads)

4494

4618

4717

4723

Link(Expressway roads)

35

52

69

73

Total lengths (km)

9000

9495

9798

9857

Different weight settings
for the same network

2010

YearYear2005
1999
Different weight values forthe same weight setting

1990
Supply Side : 𝑤! = 𝐿! 𝐶!

Demand Side : 𝑤! = 𝑉!
Concept figure

18

The change of road network in Gifu
Improvement of road network

Tokai Hokuriku Expressway
Partial opened in 1986
All opened in 2008
Under construction for 4 lanes

Tokai Ring Expressway
East side opened in 2005
Under constriction for west side

Chuo Expressway
All roads have been opened

Meishin Expressway
All roads have been opened

19Impact of road improvements on supply and demand
The change of EC based on supply and demand
2005

2010

𝑤! = 𝐿! 𝐶!

1999

Demand𝑤! = 𝑉!

Supply1990

20

Impact of road improvements on supply and demand
Scatter plots of logarithm eigenvector centrality values on supply side and demand side for each year
各年度の供給側と需要側の対数固有ベクトル中⼼性の散布図

1990
1999
2005
2010
The log-scaled EC on demand side 0-120-100-80-60-40-20

0-40-60-80-100

The log-scaled EC on supply side-20

The slope of the linear approximation line through the origin
YearSlopeR'

1990

0.808

0.880

1999

0.834

0.755

2005

0.737

0.712

2010

1.0020.774

In 1990-2005, many nodes havelower demand side evaluations thansupply side evaluations
2005年までは需要側の評価が供給側の評価より低いノードが多い-120

Connectivity on road performance have improved by road development on the supply
side, however impacts on the demand side are not as large as the supply side?
道路整備により供給側が⽰す道路性能の接続性は向上したが，需要側への影響はそれほど⼤きくないのか？

21

Correlation of supply and demand
Correlation coefficients of both weights
SupplyDemandYear

1990

1999

2005

2010

1990

0.720

0.300

0.140

0.131

1999

0.715

0.289

0.154

0.140

2005

0.728

0.289

0.157

0.14320100.764

0.478

0.361

0.349

The correlation between supply in 1990 and demandin 2010 is high, even though the EC is calculated withdifferent weights and years.
年度が離れているのにも関わらず，1990年供給量と2010年需要量の相関が最も⾼い- Road network is improved because of the increasein demandor- Demand increased by the results of roadimprovements.

22

Correlation of supply and demand
Correlation coefficients of both weights
SupplyDemandYear

1990

1999

2005

2010

1990

0.720

0.300

0.140

0.131

1999

0.715

0.289

0.154

0.140

2005

0.728

0.289

0.157

0.143

2010

0.764

0.478

0.361

0.349

The correlation between supply in 1990 and demandin 2010 is high, even though the EC is calculated withdifferent weights and years.
- Road network is improved because of the increasein demand

There should be the correlation between past
demand and future supply.
過去の需要に対して供給の年数が進むほど相関が強くなるはず

The correlation coefficient continually decrease,this suggestion does not occurred.
相関係数は減少し続けており，仮定と反する

23

Correlation of supply and demand
Correlation coefficients of both weights
SupplyDemandYear199019992005

2010

1990

0.720

0.300

0.140

0.13119990.715

0.289

0.154

0.140

2005

0.728

0.289

0.157

0.143

2010

0.764

0.478

0.361

0.349

The correlation between supply in 1990 and demandin 2010 is high, even though the EC is calculated withdifferent weights and years.

- Demand increased by the results of roadimprovements.
There should be the correlation between past supply
and demand subsequence year.
過去の供給に対して需要の年数が進むほど相関が強くなるはず

The correlation coefficient continually increase.
相関係数は経年的に増加
There is a lagged effect of road investment.
Demand-side connectivity increases as supply-side connectivity becomes better by road24
improvements. 道路整備により供給側の接続性が向上したのちに，需要側の影響の拡がりが追従する

Conclusions- Eigenvector centrality analysis showed that it is possible to evaluate a road network from different
perspectives by using some weight settings.
- Factor analysis has been used to identify important factors (traffic demand, road density and roadrank) for characterizing the road network.
- The supply side and demand side evaluations by topological approach showed differences in impactsof road network improvement.
- The evaluation of changes over a 20-year period using real road networks suggests that there may
be a time lag in the impacts of road network improvement on demand side.

25

Network inherent structure
The eigenvector centrality measure is relative evaluation index within a network, it isdifficult to evaluate the impact of network topology changes due to disasters, urbandevelopment, etc. 固有ベクトル中⼼性指標はネットワーク内の相対的な評価指標であり、形状変化の影響を直接的に評価することはできない

1. Absolute evaluation by the leading eigenvalue, an index uniquely determined forthe entire network ネットワーク全体に対して⼀意に決まる指標である最⼤固有値による絶対評価• To obtain the unique leading eigenvalue in directed graph, the graph must bestrongly connected. 有向グラフにおいて唯⼀に求めるには強連結なグラフでないといけない• The leading eigenvalue is evaluated higher when there are extremely strong parts.
So, the evaluation by the leading eigenvalue has weak affinity with homogeneityand fairness. 最⼤固有値は極端に強く接続する部分があればあるほど⾼い値を⽰し，均質性や公平性とは異なる視点となる
2. Evaluate the impact of missing parts by the amount of the eigenvector centralitychange from a criteria value determined by the network size
ネットワークサイズによって決まる基準値からの固有ベクトル中⼼性変化量によって、形状や特徴の変化がもたらす影響を評価する

Thank you ! 26