双方向的流れを持つネットワークの最適構造
理学専攻・情報科学コース 山下璃紗 (指導教員：河村1

はじめにみを決定する定数．µ = 1, 2 の時，V√はそれぞれ，表面∑1積，体積に対応する．また，Jˆmn =J 2 (k)生物的，人工的輸送ネットワークの構造がループ構造，ツリー構造のどちらを選択するかどうかは，長年の関心事項である．文献 [1] では，固定シンクでの最適構造はツリー構造が最適とされ，変動シンクでの最適構造はループ構造が最適とされている．また文献 [2] では，茎というソースが 1 点に固定されている葉脈ネットワークについて，葉の種類によってツリー構造とループ構造の最適な方が選択されていると述べられている．
しかし現在，物質流のソースとシンクが固定されていない場合，ループ構造とツリー構造どちらを取るのがネットワークとして最適かどうかについては未だ明らかになっていない．
そこで本研究では，物質流ネットワーク上の全ての点がソースになり得る場合に焦点を当て，最適なネットワーク構造を明らかにする. 具体的には輸送ネットワー
クにおいて，その構造を特徴づけるコスト関数 ([3]) を用いて各ノードがソースになる得る場合の最適ネットワークを求める. 特に最適構造が，ツリー構造になるか，ループ構造になるかに着目する.

2k∈K mnN(k)とし，Jmn はノード k がソースの時のノード m からノード n への流量，K はソースになり得るノードの集合とする (K = {0, . . . , N − 1})．式 (3) より発展方程式を求め，ṙmn = 0 を解くと，最適な太さ∗
rmn=4 ˆ2Jαµ mn1) µ+4(4)∗におけるコスト関数 H ∗ が求まる．という，rmn = rmn(k)様々なネットワーク構造に対して Jmn を求め，式 (5)よりコストの大きさを調べ，そのコストが最も低いものを最適ネットワークとする．

本研究では，ある一点のソースからその他全ての点に流体を運ぶパイプネットワークを考える．流体を輸送する各点をノード m(m = 0, . . . , N − 1)，各地点を結ぶ経路をエッジとし，各エッジは円柱形のパイプであるとする．また，ノード m と n をつなぐパイプの半径を rmn ，長さを Lmn ，流量を Jmn とする．
各ノードには外から流入と流出があり，Im をノードm からの流出とする (Im < 0 なら流入)．流れの保存
則から，∑Jmn = Im(1)

3

数値計算結果3.1

本研究で使用するネットワーク

本研究では 3 種類のネットワークを使用した (図 1)．
モデル (A) は二等辺三角形構造であり，底辺の長さをl，等辺の長さを底辺の β 倍である βl とした．β < 1の時，等辺より底辺の方が長く，β > 1 の時，底辺より等辺の方が長い二等辺三角形となる．β = 1 の時正三角形となる．モデル (B) は円上に N 個 (3 ≤ N ) のノードを等間隔に並べた正 N 角形構造である．モデル (C) は 7 ノード構造で，正六角形の真ん中にノードを 1 つ配置した構造である．
これら 3 種類のネットワークモデルに対して数値計算を行った．具体的には，まず，(i) ネットワークの各エッジに適当な初期値 rmn を与える．次に (ii) 式 (1) と(2) をガウスサイダル法を用いて解くことで流量 Jmnを求めた後，(iii) 式 (4) でその流量に対する最適な太∗∗さ rmnを求める．以降，rmnが収束するまで (ii) と(iii) を繰り返す．収束値が局所最適ネットワークであると期待される．

nが成立する．ソースとなる点では I = N − 1，その他のシンクとなる点では I = −1 である．またポワズイ
ユ流を仮定すると，流量は圧力差に比例し，Dmn(Pm − Pn )Lmn(が求まる．式 (4) を式 (3) に代入すると(µ )( ) 4+µ4( µ ) 4+µ2µ∑
444+µ∗
H = α 4+µ+Lmn Jˆmn
(5)4µm,n>mモデル

Jmn =哲也)(2)が成立する．ここで Dmn は rmn の 4 乗に比例し，エッジ mn の伝導性の大きさとする．
次のようなコスト関数を導入する．

H==E + αV∑ Lmn Jˆ2mnm,n>m4rmn+α∑µLmn rmn(3)

図 1:

本 研 究 で 使 用 す る ネット ワ ー ク モ デ ル ．

(A) 二等辺三角形構造 (B) 正 N 角形構造 (C)7 ノード構造

m,n>m

E はエネルギー散逸率で流体を流すために必要なコスト，V はネットワークを維持するコストであり，ノードとノードをつなぐパイプの体積が太くなればなるほど大きくなる．α は正の実数であり V の E に対する重3.2二等辺三角形構造の数値計算

モデル (A) について数値計算を行い，どのような構造が最適かについて検討する．考え得る構造は，三辺1全て繋いだループ構造，等辺のうち一辺を切断したツリー構造，底辺を切断したツリー構造の全部で 3 種類である．
数値計算の結果は図 2 のようになった．縦軸はコスト関数 H にある µ，横軸は二等辺三角形の底辺の長さに対する等辺の長さ β である．実線は β > 1 の時は二等辺三角形の等辺のうち一辺を切断したツリー構造とループ構造，β < 1 の時は二等辺三角形の底辺を切断したツリー構造とループ構造のコストの大きさ H ∗が同じ時の µ の値を示している．点線は β = 1 で，等辺と底辺の長さが逆転する境目を示す．実線と点線で区切られた 4 つの領域にそれぞれ示してある二等辺三角形構造は，その領域での最適構造である．µ が大きければ大きいほどループ構造が最適だということが分かる．

(a) 2 種類の正六角形構造に (b) パラメータ µ − N 空間における H ∗ の µ 依存性
おける正 N 角形の最適構造

図 3: 正 N 角形構造に対する数値計算結果(a) ツリー構造 1(c) ループ構造 1(b) ツリー構造 2(d) ループ構造 2(e) ループ構造 3

図 4: 考え得る 7 ノード構造示している．全体的に µ が大きくなるにつれてエッジを多く繋いだ構造，すなわちループ構造が最適になることが分かった．

図 2: パラメータ µ − β 空間における二等辺三角形構造の最適構造

3.3

正 N 角形構造の数値計算

モデル (B) について数値計算を行い，どのような構造が最適かについて検討する．計算を簡単にするため，最も近い隣合うノード同士のみを直線で繋ぐ場合を考える．したがって考え得る構造は，正 N 角形の一辺を切断したツリー構造と全てのエッジを結んだ正 N 角形のループ構造の 2 つである．
数値計算の結果は図 3 のようになった．図 3a は縦軸がコストの大きさ H ∗ ，横軸がコスト関数 H にあるµ である．紫の実線はツリー構造のコストの大きさを示し，緑の実線はループ構造のコストの大きさを示している．図 3b は縦軸がコスト関数 H にある µ，横軸が何角形か決める N である．実線は正 N 角形構造のツリー構造とループ構造のコストの大きさ H ∗ が同じ時の µ の値を示している．実線で区切られた 2 つの領域にそれぞれ示してある構造は，その領域での最適構造である．µ が大きければ大きいほど，ノード数 N が大きいほどループ構造が最適だということが分かる．

3.4

図 5: 5 種類の 7 ノード構造における H ∗ の µ 依存性

4

まとめと今後の課題

先行研究では固定ソース，固定シンク，変動シンクそれぞれの場合でツリー構造とループ構造どちらが最適かどうかについて調べられた．そこで本研究ではソースが可変な場合について調べたところ，構造は α には依存しないが，µ によって最適構造がループ構造とツリー構造に異なることが分かった．今後は数値計算を用いて他のネットワーク構造についてや，現存する様々なネットワークに適応するコスト関数も検討していきたい．

7 ノード構造の数値計算

参考文献

モデル (C) について数値計算を行い，どのような構造が最適かについて検討する．7 ノード構造はエッジが 12 本あり，エッジの繋ぎ方は 212 通り存在する．このため全構造に対してコストの大きさ H ∗ を調べるのは困難なので，最適構造になるのではないかと考え得る構造を 5 つに絞った (図 4)．
数値計算の結果は図 5 のようになった．縦軸がコストの大きさ H ∗ ，横軸がコスト関数 H にある µ である．
5 本の実線はそれぞれの構造のコストの大きさ H ∗ を[1] Dan Hu and David Cai. Adaptation and optimization of biological transport networks. Physical review letters, Vol. 111,
No. 13, p. 138701, 2013.
[2] Eleni Katifori, Gergely J Szöllősi, and Marcelo O Magnasco.
Damage and fluctuations induce loops in optimal transport
networks. Physical Review Letters, Vol. 104, No. 4, p. 048704,
2010.
[3] 中西智美. ロバストな輸送ネットワークの自己組織化モデル. 修士論文，お茶の水女子大学, 2018.

2