2022/09/25 #2 BinN Research Seminar Characteristic of transport network based on the eigenvalue analysis固有値解析に基づく交通ネットワークの特性分析熊本大学くまもと水循環・減災研究教育センター Kumamoto University Center for Water Cycle, Marine Environment and Disaster Management安藤宏恵(Hiroe ANDO) hiroeando@kumamoto-u.ac.jp
Eigenvalue analysis for transportation network 固有値解析を用いた交通ネットワークの分析Fiedler vector : Algebraic connectivity defined by the second smallest eigenvalue of the Laplacian 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) Leading eigenvalue :物流ネットワークのアクセシビリティ評価Identification of single additional links that contribute significantly to improve port network connectivity (Cheung et al, 2020)港湾ネットワークの連結性向上のための追加航路の特定2
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 the connections 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
• 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.重要なノードは隣接ノードの中心性を増加させるx(t + 1) = Ax(t) xi(t + 1) = x : the magnitude of effect A : adjacency matrix N: the number of nodes This iteration converges to the largest eigenvalue λmax xj > 0 (1 ≤ i ≤ N) Ax = λmaxX λmax: the largest eigenvalue of A Eigenvector centrality is obtained by the eigenvector corresponding to the largest eigenvalue of the adjacency matrix. 1st iteration : / x 1 (t + 1) /X1(t) x2(t + 1) 1 X2(t) X3(t + 1) X3(t) \x4(t + 1). \X4(t) AjjXj(t) 4
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.各リンクが重みを持つDirected and weighted adjacency matrix A Destination 1.5 () 3' () () Irigin 2 ( ) 2.5 1.5 we if e = (i,j) E E Aij = 0 otherwise
-  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. Ax = λx weight value of the link from node i to node j Aij = 0 otherwise 0.419 0.645 0.392 0.106 0.389 0.089 0.393 0.094 1.5 2 A = 1.5 (0.5 (2.5 Iterate to normalise for network size to avoid divergence. This iteration converges to the largest eigenvalue. The eigenvector corresponding largest eigenvalue should be all positive. (Perron-Frobenius theorem)
Target centrality measures
A small-scale road network in Gifu City Table. Spearman's rank correlation Capacity weighted ' The similarity between CC and EC. CCとECの相関が強いDC is significantly effected by bypass DCはバイパス道路の影響が強いes the characteristics of ECはDCとCCの両方の特性を持つ
The similarity suggests the big advantage of eigenvector centrality since the calculation of shortest pass is not needed. Classification of functional and geographical characteristics of road networks
To identify the potential common factors. Y = Af + ε Y: The set of observed variables,  Λ: The set of factor loadings of each variable and each factor, f: The set of common factors, ε: The set of unique factors ' 1) First factor loading Traffic Demand Factor Three common factors are extracted by factor analysis Second factor loading 2) Road Sparsity Factor 3) Third factor loading Road Rank Factor 13
-  Cluster 1【472 : 26%】“Rural part cluster” Gero City, Ena City, the north part in Shirakawa town and Hida 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
Average factor score in each cluster -  Cluster 2【372 : 21%】“Western urban part cluster.” Oogaki, Motosu, Ibigawa, Kaizu. Traffic demand : High demand Road 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
-  Target area : Gifu Prefecture, Japan ▷ 10,620 k㎡ in size and included mountainous and urban areas. -  Target years : 1990, 1999, 2005, 2010 ▷ The road networks have been improved year-on-year The number of nodes and links in road networks by year
Different weight settings for the same network Different weight values for the same weight setting Concept figure
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
The change of EC based on supply and demand
Scatter plots of logarithm eigenvector centrality values on supply side and demand side for each year各年度の供給側と需要側の対数固有ベクトル中心性の散布図
The slope of the linear approximation line through the origin
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 coefficients of both weights
The correlation between supply in 1990 and demand in 2010 is high, even though the EC is calculated with different weights and years.年度が離れているのにも関わらず，1990年供給量と2010年需要量の相関が最も高い-
or Demand increased by the results of road improvements.
Correlation coefficients of both weights
The correlation between supply in 1990 and demand in 2010 is high, even though the EC is calculated with different weights and years. Road network is improved because of the increase - in demand There should be the correlation between past demand and future supply.過去の需要に対して供給の年数が進むほど相関が強くなるはずThe correlation  coefficient continually decrease, this suggestion does not occurred. 23相関係数は減少し続けており，仮定と反する
Correlation coefficients of both weights
The correlation between supply in 1990 and demand in 2010 is high, even though the EC is calculated with different weights and years. Demand increased by the results of road 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 road improvements. 道路整備により供給側の接続性が向上したのちに，需要側の影響の拡がりが追従する相関係数は経年的に増加24
-  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 road rank) for characterizing the road network. -  The supply side and demand side evaluations by topological approach showed differences in impacts of 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.
The eigenvector centrality measure is relative evaluation index within a network, it is difficult to evaluate the impact of network topology changes due to disasters, urban development, etc. 固有ベクトル中心性指標はネットワーク内の相対的な評価指標であり、形状変化の影響を直接的に評価することはできない1. Absolute evaluation by the leading eigenvalue, an index uniquely determined for the entire network ネットワーク全体に対して一意に決まる指標である最大固有値による絶対評価• To obtain the unique leading eigenvalue in directed graph, the graph must be strongly connected. 有向グラフにおいて唯一に求めるには強連結なグラフでないといけない• The leading eigenvalue is evaluated higher when there are extremely strong parts. So, the evaluation by the leading eigenvalue has weak affinity with homogeneity and fairness．最大固有値は極端に強く接続する部分があればあるほど高い値を示し，均質性や公平性とは異なる視点となる2. Evaluate the impact of missing parts by the amount of the eigenvector centrality change from a criteria value determined by the network sizeネットワークサイズによって決まる基準値からの固有ベクトル中心性変化量によって、形状や特徴の変化がもたらす影響を評価する
Thank you！ 26