『経済研究』（明治学院大学）第 145 号

2012 年

スケールフリーネットワーク評価のための平均距離の分析

浜口幸弘

1．本稿の概要
本稿は浜口（2010）の続編に相当する。浜口（2010）では，Li et al.（2005）の提案したネットワークを識別するための新たな基準量 s- 値に基づき，次数列が与えられたときに s- 値を最大にする木 Tmax*とその中の特徴的な T maxについて考察した。本稿では，その考察をさらに深め，次数列が与えられた

とき，ネットワークの主要基準量の１つである 2 頂点間の平均距離に関して，それをできる限り小さくするような木 Tmax ついて考察する。

2．定義と基本的概念
Caldarelli（2007）はネットワークを特徴づけるための基準量の重要性を指摘しているが，本稿では主要な基準量の 1 つである 2 頂点間の平均距離を用いて，Li et al.（2005）の提案する s- 値を最大にす*については，る木 Tmax を対象に分析を行う。s- 値を最大にする木 Tmax およびその中の特徴的な T max

浜口（2010）でその構成方法および性質を考察し，幾つかの命題を与えている。本稿では，さらに平均距離という基準量の視点からより詳細な分析を試みる（本文中の記号の表記および概念の定義については浜口（2010）に従う）。
まず平面上における木 T の描画として，木の最大次数の頂点の 1 つを根 r として最上レベル 0（l0 と記す）に置き，r から下方に向けて距離が 1 にある頂点の位置をレベル 1（l1），距離が 2 にある頂点の位置をレベル 2（l2），…とする。さらに議論をしやすくするために，次のような定義を与える。
定義 1（平面上における木の頂点の位置づけ）
平面上の木 T に対して，その l1 において頂点を左端から右端に次数の大きいものから並べる。任意の頂点 v の下流の隣接点は，次数の大きい順に左から並べる。また，任意の頂点 u と v が同じレベルで91

『経済研究』（明治学院大学）第 145 号

左からこの順に並ぶとき，それぞれの下流の任意の隣接点 α と β は，α が β より左になるようにする（このような位置づけによって得られる木は元の木と同型である）。また頂点の位置を数字で表すために，根 r を 1 とし，次に l1 の左端から 2，3，…として，以降各レベルにおいて左端から右端に進みながら番号を順次与え，すぐ下のレベルに進んで同様に番号をつけていく。
さて，グラフの頂点次数列（非増加列とする）が与えられたとき，それを満たす木の存在条件について述べると，次の簡単な命題が成り立つ。
命題 1
グラフの頂点次数列 D=（d1，d2，…，dn）に対して，∑i di＝2（n−1）が成り立つならば，この次数列を満たす木が存在する。ただし，次数列は非増加列とする。
証明

n に関する帰納法による。D=（d1，d2，…，dn）
2 n−1）とする（次数列（dn＝1）に対して，∑i di＝（は大きさの順）。n−1 に対して，主張が成り立つと仮定する。
2（n−1）
このとき，次数列 D′＝−1）（d1−1，d2，…，dn−1）に対して，（d1−1）＋d2＋…＋dn−1＝（となるから，帰納法の仮定より D′ を満たす木が存在する。そこで，次数 d1−1 の頂点に次数 dn＝1 の頂点を接続すれば，n の場合も成り立つ。□
以下の議論では，頂点次数列 D が与えられ，この前提条件が満たされているとする。
頂点数 n の木 T に対して，任意の 2 頂点間の道 P の長さの平均距離は，一般に次式のように与えられる（任意の 2 頂点間の道の数は 1 つである）。

n（T）＝（T 上の任意の 2 頂点間の道 P の長さの総和）/ 2（ ）*次に，本稿で必要とする T maxの特徴について以下に述べる（詳細は浜口（2010）参照）。

頂点の位置づけに従う任意の木 T に対して，fi をレベル i の頂点の個数（i ≥ 1）とし，f0＝1 とする。

ni をレベル i の左端の頂点の番号（i ≥ 1）とし，n0＝1 とする。さらに，d（ j ）を頂点番号 j の次数（ 2 ≤ j ≤ n）とし，d（1）＝d（n0）＝f1 とする。このとき，

ni ＝ f0＋f1＋…＋fi−1＋n0 ＝ ni−1＋fi−1であり，また，

fi ＝（d（ni−1）−1）＋（d（ni−1＋1）−1）＋…＋（d（ni−1）−1）である。よって，
n i−1−1n1 ＝ 2，（ d（ j ）−1）（i ≥ 2）となる。
Σj =2

ni = 2 + d（1）+*
ここで，T maxの ni を ni とおき，d（ j ）を d（ j ）とおき，fi を fi とおく。このとき， ni ≥ ni である。

**

*

*

*，m を T maxの深さとすれば，明らかに m ≤ m
また，m を Tmax の深さ（根から端点までの最大距離）である。

92

スケールフリーネットワーク評価のための平均距離の分析*
3．特定の次数列を満たす（T max）の評価

一般に，木 T の 2 点間の道の平均距離を求めるには，かなりの計算量を要するし，また，その効率*と一般的的なアルゴリズムも知られていない。そこで，以下のような次数列の簡単な例を与え，T max

Tmax の平均距離を比較することで，一般的な次数列を満たす Tmax の場合を予想評価する。
d1＝d（ ≥ 3），d2＝2，…，dn−d＝2，dn−d + 1＝1，…，dn＝1（n ≥ 4）とする。また，便宜上，n≡1（mod d）とし，この木を T0 とする（この次数列を満たす任意の木は，自然に Tmax となる）。
木 T0 の根 r に接続する部分木を左から T1，T2，…，Td とする（根は除く）。そして，その頂点数をそれぞれ x1，x2，…，xd として，1 ≤ x1 ≤ … ≤ xd ≤ n−d とする。このとき，x1＋…＋xd＝n−1 となる。
xΣif（x）=xy=1=1（i+j）ΣΣji㷅（x, y）=i x−（i−1））（,=1f x）は 2 個の端点がともに { r }∪Ts（xとすれば，任意の 1 ≤ s ＜ t ≤ d に対して，（きの道の距離の総和で，㷅（x，y）は 2 個の端点がそれぞれ Ts と T（t x| Ts |，y| Ts |）にあると| Tt |）にあるときの道の距離の総和を表すものとする。よって，dnf（ xs ）+ Σ 㷅（ x s , x t ）（ 2 ）=Σ
ss t d（Tmax）

1≤ < ≤=1d3xx2xx x xx2（ + t+ ）s+ s + s ）+ Σ （ s t sΣ（）62
32s t ds=

1≤ < ≤=1

16dΣ
s=x s3 +=112

Σs t d1≤ < ≤2（ n−1）x s x（t xs + xt ）+

2+n−1
3

ここで，dh（ x 1 , …, x d ） =x s + 3 Σ xs x t（ xs + x t ）Σss t d31≤ < ≤

=1とおくと，
3（3 d −2（）n −1）h（ x 1 , … , xd ）−d2

3
（3 d −2（）x1 + … + xd ）= h（x 1 , … , xd ）−=d2d−2
3 d−22x ≥ 0（x − x t ） xs + x t +d−2 1 ≤ i≠s t ≤ d id 2 1≤s<t≤d s,

Σ（Σ）

n−1*のとき，すなわち，T maxの場合である。
dさらに別の視点から考え，n＋1 番目の頂点 v を Ti または T（j xi ≤ xj）に接続した場合の，距離の総となるから，（Tmax）の最小値は，x1 ＝ … ＝ xd ＝和の増加分をそれぞれΔLi，ΔLj とする。このとき，（n−1−xi−xj）≤ 0
ΔLi−ΔLj＝（xi−xj）
93

『経済研究』（明治学院大学）第 145 号である。すなわち，木 T0 に頂点を 1 個接続するとき，深さの最も小さい部分木に加えると，距離の総和の増加分は最も小さくなる。
*の場合も，他の Tmax に比べて 2 点間の道の平均距以上のことから，一般的な次数列を満たす T max

離は小さいと予想できる。

*4．（T max）の評価*
前述のように，T maxの 2 点間の道の平均距離は小さくなると予想される。ここでは，それを一般的*に拡張して評価を試みる。
な次数列を満たす T max

まず，一般木 T において，A を任意の 2 頂点間の道 P の集合とし，Bi を端点の最高レベルが li である P と内点の最高レベルが li である P を合わせた集合とすれば，A＝∪i Bi および Bi∩Bj ＝ （i≠j）
が成り立つ。よって，各レベルごとに任意の道を扱えば，重複なくすべての道を扱えることに注意する。
次に，Tmax 上のレベル i（li と表記）における j 番目の頂点に対して，以下のように記号を定義する。

N（1 i） ：端点の最高レベルが li である P の総数
N（2 i） ：内点の最高レベルが li である P の総数
L1,（：j 番目の頂点を端点とし，その最高レベルが li である P の長さの和i j）
L2,（：j 番目の頂点を内点とし，その最高レベルが li である P の長さの和i j）
L ,（i j ） ， L（ i ）=ΣL （,i j ）Σjj

L（=1 i）

1L（ i ）
Σi

L1 =

12，2L（ i ）Σi

L2 =2*の場合については，記号にとする。また，T max＊をつけることにする。このとき，

mfk
Σ
k iN（1 i−1 ）= f i + N（1 i ）= f i + f i + 1 + … + f m ==であり，N（ i ） ，N =ΣN（ i ）， N + N =Σii

N1 =

12

2

1n（ n −1）22である。また，m（ k−i + 1 ）f kΣ
k i

L（= f i + N（+ L（= f i + 2 f i +1 + … +（ m− i + 1 ）fm =1 i −1 ）
1 i）
1 i）

=である。ただし，m は Tmax の深さとし，長さ０の道は考えない。
mf k すなわち，レベル i 以下の頂点数が最小となる（浜口（2010）
Σk i*T maxは任意のレベル i に対して，=の命題 8−（b）の証明を参照）。よって，

L（i）
**N（
N 1* ≤ N1 かつ L（を得る。また， 1は端点の最高レベルが li1 i）≤ N（1 i）すなわち1 i）≤ L（1 i）
N（1 i）94

スケールフリーネットワーク評価のための平均距離の分析である P の長さの平均値を表し，mk（ k +1）fk2
L1k=1=mN1k fkΣΣk=1は木全体におけるその平均値を表す。さて，これまでの定義に基づき，以下の命題が成り立つ。
命題 2＊*m は T maxの深さとする（m ≥ 1）。任意の 1 ≤ i ≤ m に対して，＊L1（i−1） L（i）＞ 1＊が成り立つ。
＊N（i1N）（1 −1 i）

証明

i＝m の場合は，明らかに成り立つ。そこで，1 ≤ i ≤ m −1 の場合について考える。
ま ず， 以 下 の よ う に 帰 納 法 を 適 用 す る。 明 ら か に，f 0* ≤ f 1* で あ る。li−1（i ≥ 2） に 対 し て，f 0* ≤ f 1* ≤ … ≤ f i*−1 が成り立ち，li−2 には次数 1 の頂点が存在しないと仮定する。li−1 に次数 1 の頂点が存在しないならば，m ≥ i であり，f 0* ≤ … ≤ f i*−1 ≤ f i* となるので，引き続き li について最初から同様に考える。
*の定義から li には次数 2 の頂点が存在しない。よっ一方，li−1 に次数 1 の頂点が存在するならば，T max*で あ り， 後 者 の 場 合，て，m ＝i−1 ま た は，m ＝i と な る。 前 者 の 場 合，f 0* ≤ f 1* ≤ … ≤ f m'***f 0* ≤ f 1* ≤ … ≤ f m'
または，f 0* ≤ f 1* ≤ … ≤ f m'−1 ＞ f m' である。

この結果を利用すれば，以下のように式を評価できる。
＊＊L（L（i ）1 i−1 ）− 1＊
＊N（i1N（1 −）1 i）
m′f i*=m′Σ
k i= +1m′

f k*
Σ
Σ
k i
k i（k −i ）f k* −

fk*

=m′m′

=

= +1= +1f k* Σ f k*Σk i
k im′m′（Σk i） （Σk i

f k* − f i* f i*+1 +==m′）=m′m′

ΣΣ f k*
k i
k i
f k*

=

=m′m′

= +1=

ΣΣ f k* −（ j−i ）f i* ）f j*j i （ k im′m′ΣΣ
k ik if k*=f k −（ m −i ）f i ）f m（Σk if k* − 2 f i* f i*+2 + … += +1＞0

fk*= +1

したがって主張を得る。□
ここで，以下の条件 A を設定する
95*=′**′

『経済研究』（明治学院大学）第 145 号（ 1 ≤ i ≤ m2 − 1 ）が成り立つ。

条件 A：木 T のレベル i における頂点数 fi に対して，fi = f i*
このとき，次の命題が成り立つ。
命題 3L*
N1

条件 A のもとで， 1* より小さいL1N1をもつ木はない。

証明*の深さ任意の木 T に対して，f0，f1，…，fm を既述のように定義し，m を Tmax の深さ，m を T maxとする。m ≥ 2 で，m＞m の場合を考えればよい。そこで，mh 0 :=L1=N1k（ k + 1 ）fkΣ2k=1mk fk
Σk=1とし，fm を fm−1 および fm−1 を fm−1＋1 と操作した場合に対して，同様に
m−2k（ k + 1 ）f + m（ m−1 ） fm（ m + 1 ） f（ m + 1）+（ m− 1 ）kΣ222k−1h 1 :==1m−2） fm + 1 ）+ m（ fm−1）
k fk +（ m−1 （Σk−1=1とする。分母をそろえて整理すれば h0−h1 の分子は次のようになる。
m（ + ）
mk −Σ（）fk ＞ 0 。
2kk k 1=1

よって，h0 ＞ h1 となる。以降，操作の回数 j に対して，hj を同様に定義する。ここで表記を簡単にするため，f1，…，fm−2 ，fm−1＋1，fm−1 を最初から順に改めて，f1，…，fm と置き直し，m＝m となるまで同様の操作を繰り返す（ fm−1 が 0 になれば，これは除外するので，m は小さくなる）。そして，m*m＝m となるとき，T max
は任意のレベル i に対して，fk すなわち，レベル i 以下の頂点数が最小
Σk i=となるから，fm ≥ f m' である。また，これ以降は m の大きさを固定する（すなわち，m＝m ）。
*i ≤ m の場合も添え字の大きい順から考えて，fi ＞ f i* ならば（上記と同じ理由から常に fi ≥ f i* である）
，上述と同様に fi を fi−1 かつ fi−1 を fi−1＋1 と操作する。このとき，この fi 以前に行った操作の回数を j とすれば，hj ＞ hj＋1 である。この操作を fi ＝ f i* となるまで繰り返す。そして，fi ＝ f i* となれば，*i を 1 減らして同様に考える。これら一連の操作を続けていけば，ある t 回目の操作に，f 0*，f 1*，…，f m'となって操作は終了する。したがって，

h0 ＝L1L*＞…＞ ht ＝ 1*N1N1となり主張を得る。□*）の最小性について評価するが，それを直接考えることは難しい。そこで，命題 3 をさて，（T max用いて近似して評価を試みる。
96スケールフリーネットワーク評価のための平均距離の分析

まず，Tmax において，内点の最高レベルが li である道 P は端点の最高レベルが li である 2 つの道から構成されるので，それぞれについて全体の平均の長さを考えると，

L2L1N2 㲔 2 N1*）は最小に近い可能性を持つと言える。ここでは，と仮定できる。よって，大雑把に評価して （T max

N1 と N2 の比（すなわち重み）については考えていないが，それを考慮してもう少し厳密に扱うと次のようになる。上述の仮定を使えば，（Tmax）=

L1 + L2
N1 + N2=

N2L1L2N1+N1 +N2 N1
N1 +N2 N2㲔

N1 + 2 N2 L 1
N1 + N2 N1N2L1（ 1 + N +N ）N=

12N11L1（ 1− n（n −1））N= 21となる。以下，n を固定して考える。

mN1≥n（ n−1）
n*と同じ s- 値をもつ Tmax において，その深さ m が m
だから，T maxn となるならば（すなわち，次数*）≤ （Tmax）となる可の大きな頂点の比率が大きい場合），条件 A のもとでは，命題 3 より，（T max*）が最小になり得る。
能性が高い。よってこの場合には，（T maxLN1

また， 1 を次のように変形して考える。

L1） L（N（0N（11 0）
1 m） L（1 m）=+ …+N1N1 N（N（N11 0）1 m）
m

N（ i）= 1 である。
ΣNi1

このとき，=01LN1

よって， 1 は各レベルを端点とする道 P の長さの平均値に重みを乗じた和となる。Tmax において，明らかにL（1 i）はおおよそ減少傾向にある。よって，mN（1 i）が小さいとき，重みの変化分n で複数の Tmax が同じ深さ m であれば，ifN（L1 i−1） N（1 i）−= i すなわち，f i が大きいと， 1 が小さくなるので，
N1N1N1N197

『経済研究』（明治学院大学）第 145 号（Tmax）がより小さくなると予想される。

5．一般木の平均距離を算出するアルゴリズム
前述のことからわかるように，一般的な木の平均距離を求めるには膨大な計算を要する。ここでは，一定の条件が与えられれば効率的に一般木の平均距離を求められる方法を示す。
頂点の次数列が与えられたとき，次数列を満たす頂点の位置づけに従う任意の木 T が構成できるとする。T に対して d（ j ）を頂点番号 j の次数（ 1 ≤ j ≤ n）とすれば，以下のようなアルゴリズムを提案できる。
［アルゴリズム］
入力値：d（ j ）（ 1 ≤ j ≤ n）
手続き：

n0＝1 とし，ni をレベル i の左端の頂点の番号（i ≥ 1）とする。本稿 2 章より，
n i−1−1（ d（ j ）−1 ）Σjn i = 2 + d（ 1）+=2である。

k ≥ 1）番目（すなわち，根 r か
そこで，頂点の位置づけに従う木 T のレベル i に対して，左端から （ら数えて ni＋k−1 番目）の頂点の次数を d（i k）とし，その下流の隣接点（レベル i＋1 に属す）の集合を A（i k）とする。よって，d（（ n i + k−1 ）i k ）= dk−1k−1｛ ΣjΣj−1 ）+ d（−2A（−1 ）, …, 1 + （ d（i j）i k）
i k ）= 1 + （ d（i j）=1=1＝である。ただし，下流に隣接点がない場合は，A（i k）｝である。

T（i k）をレベル i における k 番目の頂点から下流にある頂点の総数とする（k 番目の頂点も含む）と，以下を得る。
k−1d（−2i k）

Ti （ 1 +Σ−1 ）+ t ）+ 1（ d（i j）
Σtj=T（i k）+1=1=0L1（,i k ）=L ,i （ s）
Σ Ti （ s ）+sΣAi k
1 +1+1s∈ A（i k）

L2 （, i k ）= 2

∈ （ ）（ Σ Ti （ t ））L , i （ s ）Σ Ti （ s ）Ti （ t ）+ sΣ
Ai k s t Ai k+1+1+1∈ （ ） ≠∈ （ ）s < t∈A（i k）

L ,（L（ i ）=Σ L ,（i k） ，i k）
Σkk

L（=1 i）

122

出力値：
98

1+1

スケールフリーネットワーク評価のための平均距離の分析

L1 =L（ i ）
Σi（T）=L（ i ）Σi，

1L2 =2（2 L1 + L2 ）（n n − 1）

命題 4
頂点の位置づけに従う任意の木 T に対して，以下の式が成り立つ。
d（−2i k）

k−1

Ti （ 1 +Σ（ d（−1 ）+ t ）+ 1i j）
Σtj

T（=i k）+1=1=0L1 ,（=i k）

L , i （ s）
Σ Ti （s）+sΣ
Ai k+11s∈A（i k）

+1

∈ （ ）

（ Σ Ti （ t ））L , i （ s）
Σ Ti （ s ）Ti （ t ）+sΣ
Ai k s t Ai k

L2 ,（i k ）= 2+1s< t∈A（i k）+1+1∈ （ ） ≠∈ （ ）1 +1証明明らかに，d（−2i k）k−1（ d（Ti （ 1 +Σ−1 ）+ t ）+ 1i j）
Σtj

T（i k ）=+1=1=0

L1 ,（=i k）

L , i （s）
Σ Ti （s）+sΣAi ks∈A（i k）+1∈ （ ）

1 +1は成り立つ。木 T のレベル i における k 番目の頂点に対して，上述のように A（i k）を定義する。ここで，任意の s ∈ A（i k）に対して，f（r s）を頂点 s の下流かつレベル r（i＋1 ≤ r ≤ m）に位置する頂点の個数＝ 1 とし，レベル i + 1 上の s の場合も含む）。表記を簡潔にするため，A（とする（ただし，fi+（1 s）
i k）＝{1，2，…，α } とする。そして，レベル i における k 番目の頂点を内点とし，その最高レベルが li である道 P の長さの総和を L2,（i k）とする。まず，A（i k）に属す点 1 を固定し，任意の点 s（2 ≤ s ≤ α）に対して，1 と s を通る P の長さの総和を求めると，次のようになる（s はその範囲を動かす）。ただし，以下では形式上 m まで加算するが，頂点のないレベルでは，mmΣ
jf（＝0 とする。
r s）

fi +（=1 1 ）かつ L（j 1 ）= Ti +（1 i）

=1α

m

=2=1

Σ（ k−i）f k だから（L（i）は本稿 4 章による），
1k = i +1fi （1j ）（（ j + 1 ）Ti （ s ）+ L , i （ s ））ΣΣjs+α=mΣ（Σjs+1mΣ
jfi +（j 1 ）+=2（==11+1α

L , i （s）
Σs）

j f i +（1+ Ti+（j ） Ti +（1 s）
1 1）=11 +1=2ααTi （ s）+ Ti （1）L , i （ s）
Σ）Σss

2Ti +（1 1 ）+ L1 , i +（1 1）αΣs= 2=2=2+1+1α

=2+1α

Σs

Ti +（Ti +（1 s）
1 1 ）+

1=2L , i （ s）
Σs

Ti +（1 s ）L1 , i +（1 1）
1 1 ）+ Ti +（=21+1

同様の方法で，A（i k）に属す 1 つの点を固定して上記のような総和を求め，それらを加算する。1 つ99

『経済研究』（明治学院大学）第 145 号の道を 2 回数えるので，それを考慮すると以下を得る。

L2 ,（i k ）= 2

Σ Ti （s）Ti （ t ）+sΣ（ Σ Ti （ t ））L , i （s） □Ai k s t Ai ks < t ∈ A（i k）+1+1∈ （ ） ≠∈ （ ）

+1

1 +1

この命題に従えば，一般的な木の平均距離を簡潔に算出できる。

6．課題
本稿では木を対象としたが，より一般的な，すなわち閉路を持つグラフに対する理論の拡張が必要である。

参考文献
Li, L., Anderson, D., Doyle, J. and Willinger, W.（2005）. “Towards a Theory of Scale-Free Graphs: Deﬁnition,Properties and Implications”, Internet Math. 2: 4, 431-523
Caldarelli, G.（2007）. Scale-Free Networks: complex webs in nature and technology, Oxford UniversityPress
浜口（2010），スケールフリーネットワーク評価のための基準量の提案，明治学院大学経済研究100