本補遺について
この補遺では，まず，本書に収録しなかった 3 つの項目を説明する。
本書の該当箇所それぞれにおいて，本補遺を参照している。
最初の 2 つは，スケールフリー・ネットワークの 2 つのモデルに対するクラスター係数の計算である。これら 2 つのモデルは，生成されるネットワークがスモールワールドかつスケールフリーとなる例である。3 つ目は，ある
中心性指標の紹介であり，ネットワーク上のランダム・ウォークの応用例として位置づけられる。そこでは，線形代数や電気回路の知識が効果的に用いられている。
最後に，本書の [63] 番以降の文献について，論文名つきの文献リストを掲載する。
本補遺が本書の理解の一助となれば幸いである。
増田直紀，今野紀雄

目 次
1．頂点非活性化モデルのクラスター係数の計算 ･････････ 2
２．閾値モデルのクラスター係数の計算･･･････････････････ 5
３．ランダム・ウォーク媒介中心性 ････････････････････････ 8
論文名つきの文献リスト ････････････････････････････････ 13

1．頂点非活性化モデルのクラスター係数の計算
時刻 t でネットワークに加入した頂点 vt は，いずれ非活性化する。vt の各
隣接点もいずれ非活性化する。それ以降は，vt と vt の隣接点は新しい枝を受けとらないので，vt のクラスター係数は変化しなくなる。vt の最終的な次数を k(≥ m) とする。各点のクラスター係数は k だけで決まるので，k によって場合分けをする。
・ k = m ならば，図 S1（A）に示すように，vt は加入直後に非活性化

(A)

vt

vt

vt

vt

(v t = v’)
t

(B)

vt
v’
t

v’
t

vt
v’
t

vt+1

v’
t

vt+1

(C)

vt

vt
v’
t

v’
t

vt+1

vt+2
v’
t+1
vt+1

v’
t

v’
t

vt+1

vt+2
v’
t+1

vt

v’
t+1

vt

vt
v’
t

vt+1

図 S1 頂点非活性化モデルのクラスター係数の求め方 (m = 3)。
（A）k = m, （B）k = m + 1, （C）k = m + 2. 点線は実際には
ない枝

1

vt
v’
t

したことになる。 vt に隣接する 2 頂点 va ，vb をランダムにとってきて，vt , va , vb が三角形を成すかどうかを考える。va と vb は，新顔のvt から枝を受けとったので，時刻 t 以前から活性化状態である。va がvb より古株だとする。vb が加入したとき，va は活性化状態のはずである。その後 vt が加入したときも，va は活性化状態を保っているからである。したがって，va と vb の間には枝があり，vt , va , vb は三角形を成す。va と vb の選び方は任意なので，vt のクラスター係数，あるいは，
一般に k = m となる点のクラスター係数はC(k = m) = 1.

（S1）

・ k = m + 1 ならば，vt は時刻 t では活性化状態に留まって 1 本の枝を受けとり，時刻 t + 1 で非活性化する（図 S1（B））。時刻 t に非活性化した頂点を vt と書く。図 S1（B）に示すように，vt は，時刻 t + 1 で新しい頂点 vt+1 から枝を受けとらない。vt の隣接点 m + 1 個がなす対は (m + 1)m/2 組あり，そのうち vt+1 と vt の間にだけ枝がないので，

C(k = m + 1) =(m + 1)m/2 − 1.
(m + 1)m/2（S2）

・ k = m + 2 ならば，頂点 vt は時刻 t と t + 1 では活性化状態に留まって 2 本の枝を受けとり，時刻 t + 2 で非活性化する（図 S1（C））。vt の隣接点 m + 2 個の頂点対 (m + 2)(m + 1)/2 組の中で，枝がないのは
vt+1 と vt の間，vt+2 と vt の間，vt+2 と vt+1の間，の 3ヶ所なのでC(k = m + 2) =(m + 2)(m + 1)/2 − 3.
(m + 2)(m + 1)/2

（S3）・ 一般に，次数が k = m + k のときは，頂点対 (m + k )(m + k − 1)/2
組のうち


k


k (k + 1)
k =
2

k =1


2

（S4）

1．頂点非活性化モデルのクラスター係数の計算

本の枝が欠けているので，(m + k )(m + k − 1)/2 − k (k + 1)/2
C(k) =(m + k )(m + k − 1)/2
(k − m + 1)(k − m)=1−k(k − 1)(m − 1)(2k − m).
=k(k − 1)

（S5）

式（S5）より，k が大きいところで C(k) ∝ k−1 .
ネットワーク全体のクラスター係数は
 ∞C=C(k)p(k)dk.
m

例えば，a = m のときは C = 5/6 となる。

3

（S6）

2．閾値モデルのクラスター係数の計算
閾値モデルの C(k) を求めるには，次数が k である頂点 v を含む三角形の有無を知ればよい。図 S2 に示すように，v は 2 点 v  , v  と隣接しているとする。v  の重みを w  ，v  の重みを w  とすると，w + w ≥ θ, w + w  ≥ θ が必ず満たされている。このとき，v  と v  の間に枝があれば，v を含む三角形ができる。このような枝がある確率が，v のクラスター係数 C(k) である。
まず，ある頂点 v が重み w をもつとする。式 （7.19）（p.145）より，次数はk = N (1 − F (θ − w)) .

（S7）

隣接点 v  で重みが w  ，すなわち，次数がk = N 1 − F (θ − w )（S8）となるものの密度は，w  ≥ θ − w なら f (w ) でそれ以外なら 0 である。v  の重みが θ − w より小さいと枝 (v, v  ) 自体が存在しないからである。
枝 (v, v  ) はあるとして，v のもう１つの隣接点 v  （重み w  ）を考えると
きに，v  と v  の間に枝があるかどうかを調べる。まず，v  が v と隣接すると仮定して出発するので w + w  ≥ θ である。
場合 1w ≥ w のときはw + w ≥ w + w ≥ θ（S9）なので，v  と v  の間に必ず枝がある。この場合から三角形ができる確率は 1 である。

v"

?

v’

v
図 S2 閾値モデルのクラスター係数の求め方

42．閾値モデルのクラスター係数の計算場合 2

θ − w ≤ w < w (k < k) のときは，w + w ≥ θ が成立するときだけ v  と v  が隣接する。w  < θ − w ならば隣接しない。したがって，この場合から三角形ができる確率は∞
f (w )dw
1 − F (θ − w )
θ−w
∞
=
.
 )dw 
1
−
F
(θ
−
w)
f
(w
θ−w

（S10）

元の頂点 v に戻ろう。w > θ/2，すなわち k > N (1 − F (θ/2)) のときは，場合 1 と場合 2 の両方が起こりうる。このとき，w を k で書き表す途中計算を少し省略するが，

 w 1−F (θ−w )


1
×
f
(w
)dw
+
f (w )dww
θ−w 1−F (θ−w)
∞C(k) =.
 )dw f(w
θ−w
∞ θ−F −1 (1−k/N ) 


1
p(k
)dk
+
k p(k )dk−1k F −1 (1−k/N )θ−F (1−k/N )∞=.
 )dk p(k−1
F (1−k/N )
∞

（S11）

分子の最初の積分が場合 1，2 つめの積分が場合 2 に対応する。

w ≤ θ/2 のとき，すなわち，k ≤ N (1 − F (θ/2)) のとき，場合 2 (w < w)
からは三角形ができない。w + w < θ なので，v と v  がそもそも隣接しないからである。よって場合 1 だけを考慮してC(k) = 1.

（S12）

式（S11）と式（S12）から計算すると，重みが指数分布に従う，すなわち，

f (w) = λe−λw(w ≥ 0)

（S13）

のときは

C(k) ∝ k−2 .
重みがべき則に従う，すなわち，a  wmin a+1
f (w) =
wmin
w

（S14）

(w ≥ wmin )

（S15）

のときは，

C(k) ∝ k−1 .
5

（S16）

式（S16）は，階層的モデルの結果（6.8 節）と同じである。
最後に，ネットワーク全体のクラスター係数は
 ∞C=C(k)p(k)dk

（S17）

0

から求まる。例えば，f (w) が指数分布のとき，limN →∞ C > 0 となる。

6

3．ランダム・ウォーク媒介中心性

3．ランダム・ウォーク媒介中心性
媒介中心性は，最もよく使われる中心性の指標の 1 つである。しかし，情報の流れを媒介するという本来の目的に限っても，直観とずれる値を与えることがある。
図 S3 を見てみよう。最短路がたくさん通る頂点が大きな媒介中心性をもつから，v1 と v2 の媒介中心性は大きい。左コミュニティの頂点と右コミュニテ
ィの頂点を結ぶ最短路は，必ず v1 , v2 を通るからである。そのような最短路
は，決して v3 を通らない。v3 を通る迂回路は，最短路よりも 1 だけ距離が長いからである。よって，v3 の媒介中心性は小さい。ただ，v3 は，v1 や v2 に及ばないとしても他の大多数の頂点よりは重要そうに見える。
この違和感の由来は，9.2.4 節で与えられている。スモールワールド実験の場合と同様に，多くの実用においては最短路がわからないのである。よって，最短路より少しだけ長い経路も，それなりに情報伝達に役立っているはずだ。
そこで，最短路以外の経路上にいる頂点にも，それなりの得点を与えるように
媒介中心性を変更してみる。その極端な場合として，最短路を通るウォークの代わりに，単純ランダム・ウォークを考える。頂点がゴールや隣接点についての情報を全くもたない場合である。伝達効率が悪いランダム・ウォークを用いることによって，最短でない道の上にいる人にも中心性の部分点が与えられてちょうどよい。これがランダム・ウォーク中心性の考え方である［174, 178］。
枝に方向がないとする。媒介中心性の定義と同様に始点 vis とゴール vit を定める。有限ネットワークなので，ランダム・ウォーカーはいずれ vit に到達する（無限ネットワークで再帰的でない場合，そうとは限らない）。vis から vit

v3
v1
図 S3

v2

媒介中心性では， v3 の中心性はとても小さい

7

に着くまでに，同じ頂点を 2 回以上通ることもある。ともあれ，媒介中心性のときと同様に，ウォーカーが v を通る回数を数えて中心性の値を定義する。
もし vit を定めずにウォーカーが永久にネットワーク内を歩き続けると，ウォーカーが頂点 v を通る回数は次数に比例する（9.2.1 節）。ところが，ゴールありきのウォークを考えるので，長すぎるウォークの中心性への寄与は小さくなる。vit に到達せずにネットワークの中を長くさまようウォークは起こりにくいからである。一方，最短路だけを数えるわけではなく，最短路よりいくらか長い経路も，それなりに中心性の向上に寄与する。

vi のランダム・ウォーク（媒介）中心性を
brw
i ∝

N i
s −1


(vis から vit へ行くウォーカーが vi を本質的に通る平均回数)

is =1 it =1（S18）で定める［174］。本質的に通過する回数，の意味は後で説明する。実は，ネッ
トワーク上のランダム・ウォークは，ネットワーク上の電気回路とうまく対応
する［142］。そこで，遠回りになるようだが，電気回路に基づく中心性を先に考え，実はその中心性がランダム・ウォーク中心性に等しいことを確認する，という手順で考える。
ランダム・ウォークの始点 vis に電流 1 が入り，ゴール vit から電流 1 が出るとする。各枝にはコンダクタンス（抵抗の逆数）1 が乗っていて，大雑把には vis から vit に向かって電流が流れているとする。
頂点 vi の電位を Vi と書く。各点 vi におけるキルヒホッフの電流保存則よりNAij (Vi − Vj ) = δi,is − δi,it .

（S19）

j=1

Aij (Vi − Vj ) は，vi から vj に流れる電流である。(Aij ) は隣接行列なので，
式（S19）の左辺は，実質的には vi に隣接する vj についてのみの和である。
右辺は i = is , it である限り 0 となり，vis と vit を除いては，電流の出る量と入る量が釣り合っていることを表す。

8

3．ランダム・ウォーク媒介中心性N
Aij = ki

（S20）

j=1

より，式（S19）を行列とベクトルで書き直すと(D − A)V = I.

（S21）

ここで，D は，i 番目の対角成分は ki である N × N 対角行列である。D − A
はラプラシアン行列と呼ばれる。V = (V1 · · · VN ) は，各頂点の電位を並べた縦ベクトルであり（ は転置を表す），これを求めたい。I は N 次元縦ベ
クトルで

⎧
⎪
⎪
1,
⎪
⎪
⎨
I i = −1,
⎪
⎪
⎪
⎪
⎩0,

(i = is ),(i = it ),（S22）(i = is , it ).

各点の電位 V は，式（S21）に D − A の逆行列を左からかければ直ちに求まるかのように見える。しかし，D − A は正則でない。(1 1 · · · 1) が D − Aの固有値 0 に対応する固有ベクトルだからである。これは，電位が相対的な概念であることの現れである。つまり，ある 1 点の電位を例えば 0 と定義すると，そこから相対的に他の N − 1 点の電位が求まる。全ての点の電位に同一の定数を足してもよい。この任意性のために，式（S21）だけから V を一意的に定めることができない。
そこで，式（S21）から任意の 1 行 i0 を除去する。これは，Vi0 = 0 と置くことに対応する。D と A から第 i0 行と第 i0 列を除去し，その結果 D − A からできた (N − 1) × (N − 1) 行列を Di0 − Ai0 と置く。Vi0 を除去した V を

Vi0 , Ii0 を除去した I を I i0 と書く。式（S21）から 1 行を除去してできた(Di0 − Ai0 )Vi0 = I i0（S23）

は，N − 1 次元連立線形方程式である。ネットワークが連結である限り，行列9

Di0 − Ai0 は正則である。よって，
Vi0 = (Di0 − Ai0 )−1 I i0 .

（S24）

ここで，(Di0 − Ai0 )−1 にゼロで埋められた第 i0 行と第 i0 列を戻してできる

N × N 行列を T ，T の第 i 行第 j 列成分を Ti,j と書く。式（S22）を式（S24）に代入してVi = Ti,is − Ti,ie .

（S25）

式（S25）は Vi0 = 0 を満たすことに注意する。
頂点 vi を流れる総電流は
⎧ N
N
1
1
⎪
⎪
⎨
Aij |Vi − Vj | =Aij |Ti,is − Ti,it − Tj,is + Tj,it |,
2
2
j=1
j=1
Ii =
⎪
⎪
⎩1,

(i = is , it ),(i = is , it ).
（S26）

i = is , it のときの右辺を 2 で割るのは，同じ電流を vi に入る分と出る分で 2回数えているからである。
式（S26）は，特定の始点 vis とゴール vit に対する結果である。そこで，(i ,i )式（S26）の Ii を始点とゴールを明示して Ii s t と書き，頂点 vi のランダム・
ウォーク中心性を
N i
t −1


(i ,i )

Ii s ti =1 i =1

s
t
brw
i =
N (N − 1)/2

（S27）で定義する。電流が出入りしやすい頂点が中心，という基準である。
実は，式（S27）は，ランダム・ウォークが頂点に訪れる程度を表す。それを見るために，ランダム・ウォークに話を戻す。ランダム・ウォークの推移確率行
列は式 （9.4）（p.205）で与えられる。これはゴールがない場合である。ゴール vit がある場合に，vi にいるウォーカーが vj に移動する確率は
⎧
Aij
⎪
⎪
⎨ ki , (i = it ),

Bij
=
⎪
⎪
⎩δi ,j , (i = it ).
t

10

（S28）

3．ランダム・ウォーク媒介中心性

δit ,j は it = j なら 1, it = j なら 0 である。式（S28）は，ウォーカーがゴー
ル vit に到達したら，それ以降の時刻では vit に留まり続けることを表す。
行列で書くと，第 it 行以外については B  は D−1 A と等しい。そこで，B  ,D−1 , A のそれぞれから行 it と列 it を除くと，
Bit = Di−1
Ait
t

（S29）

となる。Bit , Dit , Ait は，それぞれ (N − 1) × (N − 1) 行列であり，Dit , Ait
は Di0 , Ai0 で i0 = it と選んだものである。B  の各行について，和が 1 より小さい場合は，残りの確率でウォーカーが vit に吸収されたと思えばよい。

vis から出発するランダム・ウォークを考える。ウォーカーが時刻 T で vi(i = it ) にいる確率は (Bit )T の第 is 行第 i 列の値である。さらに次の時刻で隣接点 vj へ行く確率は，これを ki で割ったものである。よって，ウォーカーが vi → vj の向きにこの枝を通る回数の期待値は，(N − 1) 次元単位行列 Eを用いて∞(Bi )T の第 is 行第 i 列
t

T =0

ki

[E − Bit ]−1 の第 is 行第 i 列=ki= I it (E − Di−1
Ait )−1 Di−1tt


= I it (Dit − Ait )−1の第 i 成分の第 i 成分. （S30）

Dit と Ait は対称行列なので，式（S30）の量は (I it (Dit − Ait )−1 ) = (Dit −Ait )−1 I it の第 i 行目の成分と同一である。よって，式（S24）より，式（S30）の量は，i0 として it を選んだときの電位 Vi に等しい。ここでランダム・ウ
ォークが電気回路と結びつくのである。式（S30）は vj によらないことに注意する。vi にいれば，次のステップでは任意の隣接点に確率 1/ki で移動する。
結局，vi を訪れやすいほど vi → vj の方向にこの枝を通りやすい。
ウォーカーが vis から vit に到達するまでに vi → vj と移動する「実質的な」回数，すなわち，vi → vj と移動する回数から vj → vi と移動する回数を引いたものは |Vi − Vj | である。後は，始点 vis とゴール vit について平均化すればよく，その部分は，式（S26）から式（S27）を導く部分と同一である。
注意として，ウォーカーが vi を通過する回数そのものは，式（S30）より，
11

ki Vi である（Vi は is と it に依存する）。brw
は，これとは等しくない。例
i
えば，vi → vj → vi → vj → vi → · · · といった動きは，ウォーカーが vi
や枝 (vi , vj ) を通る回数としては数えるが，ランダム・ウォーク中心性では，

vi → vj と vj → vi が打ち消しあうと見なして数えない。これにより brw
i と電気回路の対応づけが可能になっている。
最後に， 1 つの i に対する式（S27）の評価に O(M N )，逆行列の計算に

O(N 3 ) の計算時間がかかる。よって，全ての頂点の brwを計算するには，iO((M + N )N 2 ) の時間がかかる。平均次数が大きくないなら O(N 3 ) である。
いずれにせよ，速い方ではない。

12

論文名つきの文献リスト

論文名つきの文献リスト［63］ Albert, R., Jeong, H., Barabási, A. -L. : Error and attack toleranceof complex networks. Nature, Vol. 406, pp. 378–382 (2000).
［64］ Anderson, R. M., Medley, G. F., May, R. M., Johnson, A. M. : A

preliminary study of the transmission dynamics of the human immunodeﬁciency virus (HIV), the causative agent of AIDS. IMA Journalof Mathematics Applied in Medicine & Biology, Vol. 3, pp. 229–263(1986).
［65］ Arenas, A., Dı́az-Guimera, A., Pérez-Vicente, C. J. : Synchroniza-tion reveals topological scales in complex networks. Physical Review
Letters, Vol. 96, article No. 114102 (2006).
［66］ Axelrod, R. : Evolution of Cooperation, Basic Books (1984). R. ア
クセルロッド著（松田裕之訳）：『つきあい方の科学 — バクテリアから国際関係まで』，ミネルヴァ書房 (1998).
［67］ Ball, F., Mollison, D., Scalia-Tomba, G. : Epidemics with two levelsof mixing. Annals of Applied Probability, Vol. 7, pp. 46–89 (1997).
［68］ Barabási, A. -L., Albert, R. : Emergence of scaling in random net-

works. Science, Vol. 286, pp. 509–512 (1999).
［69］ Barabási, A. -L., Albert, R., Jeong, H. : Mean-ﬁeld theory for scale-free random networks. Physica A, Vol. 272, pp. 173–187 (1999).
［70］ Barabási, A. -L., Ravasz, E., Vicsek, T. : Deterministic scale-free

networks. Physica A, Vol. 299, pp. 559–564 (2001).
［71］ Barahona, M., Pecora, L. M. : Synchronization in small-world sys-tems. Physical Review Letters, Vol. 89, article No. 054101 (2002).
13

［72］ Barbour, A. D., Reinert, G. : Small worlds. Random Structures andAlgorithms, Vol. 19, pp. 54–74 (2001).
［73］ Barrat, A., Weigt, M. : On the properties of small-world networkmodels. European Physical Journal B, Vol. 13, pp. 547–560 (2000).
［74］ Barrat, A., Pastor-Satorras, R. : Rate equation approach for corre-

lations in growing network models. Physical Review E, Vol. 71, article
No. 036127 (2005).
［75］ Barthélemy, M., Barrat, A., Pastor-Satorras, R., Vespignani, A. :Velocity and hierarchical spread of epidemic outbreaks in scale-free
networks. Physical Review Letters, Vol. 92, article No. 178701 (2004).
［76］ Barthélemy, M., Barrat, A., Pastor-Satorras, R., Vespignani, A. :Dynamical patterns of epidemic outbreaks in complex heterogeneous
networks. Journal of Theoretical Biology, Vol. 235, pp. 275–288 (2005).
［77］ Benjamini, I., Kesten, H., Peres, Y., Schramm, O. : Geometry of

the uniform spanning forest: transitions in dimensions 4, 8, 12, . . .
Annals of Mathematcs, Vol. 160, pp. 465–491 (2004).
［78］ Bergeron, F., Flajolet, P., Salvy, B. : Varieties of increasing trees.

Lecture Notes in Computer Science, Vol. 581, pp. 24–48 (1992).
［79］ Bianconi, G., Barabási, A. -L. : Competition and multiscaling inevolving networks. Europhysics Letters, Vol. 54, pp. 436–442 (2001).
［80］ Bianconi, G., Barabási, A. -L. : Bose-Einstein condensation in com-plex networks. Physical Review Letters, Vol. 86, pp. 5632–5635 (2001).
［81］ Biskup, M. : On the scaling of the chemical distance in long-range

percolation models. Annals of Probability, Vol. 32, pp. 2938–2977(2004).
［82］ Boguñá, M., Pastor-Satorras, R. : Class of correlated random net-

works with hidden variables. Physical Review E, Vol. 68, article No.
036112 (2003).
［83］ Bollobás, B., Chung, F. R. K. : The diameter of a cycle plus a

random matching. SIAM Journal of Discrete Mathematics, Vol. 1, pp.
328–333 (1988).
14論文名つきの文献リスト［84］ Bollobás, B., Riordan, O. : The diameter of a scale-free randomgraph. Combinatorica, Vol. 24, pp. 5–34 (2004).
［85］ Bonacich, P. : Factoring and weighting approaches to status scoresand clique identiﬁcation. Journal of Mathematical Sociology, Vol. 2,
pp. 113–120 (1972).
［86］ Brandes, U. : A faster algorithm for betweenness centrality. Journalof Mathematical Sociology, Vol. 25, pp. 163–177 (2001).
［87］ Bullmore, E., Sporns, O. : Complex brain networks: graph theo-

retical analysis of structural and functional systems. Nature Reviews
Neuroscience, Vol. 10, pp. 186–198 (2009).
［88］ Caldarelli, G., Capocci, A., De Los Rios, P., Muñoz M. A. : Scale-free networks from varying vertex intrinsic ﬁtness. Physical Review
Letters, Vol. 89, article No. 258702 (2002).
［89］ Callaway, D. S., Newman, M. E. J., Strogatz, S. H., Watts, D. J.

: Network robustness and fragility: percolation on random graphs.
Physical Review Letters, Vol. 85, pp. 5468–5471 (2000).
［90］ Catanzaro, M., Pastor-Satorras, R. : Analytic solution of a static

scale-free network model. European Physical Journal B, Vol. 44, pp.
241–248 (2005).
［91］ Chung, F., Lu, L. : The average distances in random graphs withgiven expected degrees. Proceedings of the National Academy of Sciences of the United States of America, Vol. 99, pp. 15879–15882 (2002).
［92］ Chung, F., Lu, L., Vu, V. : Spectra of random graphs with given

expected degrees. Proceedings of the National Academy of Sciences of
the United States of America, Vol. 100, pp. 6313–6318 (2003).
［93］ Clauset, A., Newman, M. E. J., Moore, C. : Finding community

structure in very large networks. Physical Review E, Vol. 70, article
No. 066111 (2004).
［94］ Clauset, A., Shalizi, C. R., Newman, M. E. J. : Power-law distribu-

tions in empirical data. SIAM Review, Vol. 51, pp. 661–703 (2009).
［95］ Cohen, R., Erez, K., ben-Avraham, D., Havlin, S. : Resilience of15

the Internet to random breakdowns. Physical Review Letters, Vol. 85,
pp. 4626–4628 (2000).
［96］ Cohen, R., Erez, K., ben-Avraham, D., Havlin, S. : Breakdown of

the Internet under intentional attack. Physical Review Letters, Vol. 86,
pp. 3682–3685 (2001).
［97］ Cohen, R., ben-Avraham, D., Havlin, S. : Percolation critical ex-

ponents in scale-free networks. Physical Review E, Vol. 66, article No.
036113 (2002).
［98］ Cohen, R., Havlin, S. : Scale-free networks are ultrasmall. PhysicalReview Letters, Vol. 90, article No. 058701 (2003).
［99］ Cohen, R., Havlin, S., ben-Avraham, D. : Eﬃcient immunization

strategies for computer neteworks and populations. Physical Review
Letters, Vol. 91, article No. 247901 (2003).
［100］ Coppersmith, D., Gamarnik, D., Sviridenko, M. : The diameter ofa long-range percolation graph. Random Structures and Algorithms,
Vol. 21, pp. 1–13 (2002).
［101］ Donetti, L., Hurtado, P. I., Muñoz, M. A. : Entangled networks,

synchronization, and optimal network topology. Physical Review Letters, Vol. 95, article No. 188701 (2005).
［102］ Dorogovtsev, S. N., Mendes, J. F. F., Samukhin, A. N. : Structureof growing networks with preferential linking. Physical Review Letters,Vol. 85, pp. 4633–4636 (2000).
［103］ Dorogovtsev, S. N., Goltsev, A. V., Mendes, J. F. F. : Pseud-ofractal scale-free web. Physical Review E, Vol. 65, article No. 066122(2002).
［104］ Dorogovtsev, S. N., Goltsev, A. V., Mendes, J. F. F., Samukhin, A.

N. : Spectra of complex networks. Physical Review E, Vol. 68, article
No. 046109 (2003).
［105］ Draief, M., Ganesh, A. : Eﬃcient routing in poisson small-world

networks. Journal of Applied Probability, Vol. 43, pp. 678–686 (2006).
［106］ Durán, O., Mulet, R. : Evolutionary prisoner’s dilemma in random16論文名つきの文献リスト

graphs, Physica D, Vol. 208, pp. 257–265 (2005).
［107］ Ebel, H., Mielsch, L. -I., Bornholdt, S. : Scale-free topology ofe-mail networks. Physical Review E, Vol. 66, article No. 035103(R)(2002).
［108］ Eguı́luz, V. M., Klemm, K. : Epidemic threshold in structured

scale-free networks. Physical Review Letters, Vol. 89, article No.
108701 (2002).
［109］ Farkas, I. J., Derényi, I. Barabási, A. -L., Vicsek, T. : Spectra of“real-world” graphs: beyond the semicircle law. Physical Review E,
Vol. 64, article No. 026704 (2001).
［110］ Fortunato, S. : Community detection in graphs. Physics Reports,

Vol. 486, pp. 75–174 (2010).
［111］ Franceschetti, M., Meester, R. : Navigation in small-world net-

works: a scale-free continuum model. Journal of Applied Probability,
Vol. 43, pp. 1173–1180 (2006).
［112］ Franceschetti, M., Meester, R. : Random networks for communi-

cation — From statistical physics to information systems, Cambridge
University Press (2007).
［113］ Freeman, L. C. : Centrality in social networks conceptual clariﬁ-

cation. Social Networks, Vol. 1, pp. 215–239 (1979).
［114］ Galarreta, M., Hestrin, S. : Electrical synapses between GABA-

releasing interneurons. Nature Reviews Neuroscience, Vol. 2, pp. 425–
433 (2001).
［115］ Girvan, M., Newman, M. E. J. : Community structure in social andbiological networks. Proceedings of the National Academy of Sciencesof the United States of America, Vol. 99, pp. 7821–7826 (2002).
［116］ Goh, K. -I., Kahng, B., Kim, D. : Universal behavior of load distri-bution in scale-free networks. Physical Review Lettters, Vol. 87, article
No. 278701 (2001).
［117］ Goh, K. -I., Kahng, B., Kim, D. : Spectra and eigenvectors ofscale-free networks. Physical Review E, Vol. 64, article No. 051903
17

(2001).
［118］ Grassberger, P. : On the critical behavior of the general epidemic

process and dynamical percolation. Mathematical Biosciences, Vol. 63,
pp. 157–172 (1983).
［119］ Hethcote, H. W., Yorke, J. A. : Gonorrhea transmission dynam-

ics and control. Lecture Notes in Biomathematics, Vol. 56, pp. 1–105(1984).
［120］ Holme, P., Kim, B. J. : Growing scale-free networks with tunableclustering. Physical Review E, Vol. 65, article No. 026107 (2002).
［121］ Ichinomiya, T. : Frequency synchronization in a random oscillator

network. Physical Review E, Vol. 70, article No. 026116 (2004).
［122］ Ichinomiya, T. : Path-integral approach to dynamics in a sparse

random network. Physical Review E, Vol. 72, article No. 016109 (2005).
［123］ 稲水伸行，竹嶋斎：ネットワーク可視化の技法 — Pajek の使い方.
『赤門マネジメント・レビュー』，Vol. 4, pp. 281–302 (2005).
［124］ Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., Barabási, A. -L. :The large-scale organization of metabolic networks. Nature, Vol. 407,
pp. 651–654 (2000).
［125］ Jeong, H., Mason, S. P., Barabási, A. -L., Oltvai, Z. N. : Lethality

and centrality in protein networks. Nature, Vol. 411, pp. 41–42 (2001).
［126］ 香取眞理：『複雑系を解く確率モデル — こんな秩序が自然を操る』，
講談社 (1997).
［127］ Keeling, M. J., Eames, K. T. D. : Networks and epidemic models.

Journal of the Royal Society Interface, Vol. 2, pp. 295–307 (2005).
［128］ Kermack, W. O., McKendrick, A. G. : A contribution to the math-ematical theory of epidemics. Proceedings of the Royal Society of London A, Vol. 115, pp. 700–721 (1927).
［129］ Kleinberg, J. M. : Authoritative sources in a hyperlinked environ-ment. in Proceedings of the 9th ACM-SIAM Symposium on Discrete
Algorithms, pp. 668–677 (1998). （［130］は，この文献と同じ表題の拡張版）
18

論文名つきの文献リスト［130］ Kleinberg, J. M. : Authoritative sources in a hyperlinked environ-ment. Journal of the ACM, Vol. 46, pp. 604–632 (1999).
［131］ Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S.,

Tomkins, A. S. : The web as a graph: Measurements, models, andmethods. Lecture Notes in Computer Science, Vol. 1627, pp. 1–17
(1999).
［132］ Kleinberg, J. M. : Nagivation in a small world. Nature, Vol. 406,

pp. 845 (2000).
［133］ Kleinberg, J. : The small-world phenomenon: an algorithmic per-spective. in Proceedings of the 32nd ACM Symposium on Theory ofComputing, pp. 163–170 (2000).
［134］ Kleinberg, J. : Small-world phenomena and the dynamics of in-formation. in Advances in Neural Information Processing Systems(NIPS), Vol. 14, pp. 431–438 (2001).
［135］ Kleinberg, J. Complex networks and decentralized search algo-rithms. in Proceedings of the International Congress of Mathematics,
Vol. 3, pp. 1019–1044 (2006).
［136］ Klemm, K., Eguı́luz, V. M. : Highly clustered scale-free networks.

Physical Review E, Vol. 65, article No. 036123 (2002).
［137］ Klemm, K., Eguı́luz, V. M. : Growing scale-free networks withsmall-world behavior. Physical Review E, Vol. 65, article No. 057102(2002).
［138］ 今野紀雄：『無限粒子系の科学』，講談社 (2008).
［139］ Krapivsky, P. L., Redner, S., Leyvraz, F. : Connectivity of growing

random networks. Physical Review Letters, Vol. 85, pp. 4629–4632(2000).
［140］ Krapivsky, P. L., Redner, S. : Organization of growing random

networks. Physical Review E, Vol. 63, article No. 066123 (2001).
［141］ Krapivsky, P. L., Redner, S. : Network growth by copying. PhysicalReview E, Vol. 71, article No. 036118 (2005).
［142］ 熊谷隆：『確率論』，共立出版 (2003). の第 3 章
19［143］ Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D.,

Tomkins, A. S., Upfal, E. : Stochastic models for the web graph. inProceedings of the 41st Annual IEEE Symposium on the Foundationsof Computer Science, pp. 57–65 (2000).
［144］ Kuperman, M., Abramson, G. : Small world eﬀect in an epidemio-

logical model. Physical Review Letters, Vol. 86, pp. 2909–2912 (2001).
［145］ Kuramoto, Y. :Chemical oscillations, waves, and turbulence,

Springer-Verlag (1984). Dover Publications からも再版 (2003).
［146］ 蔵本由紀編：『リズム現象の世界』，東京大学出版会 (2005).
［147］ Langville, A. N., Meyer, C. D. : Google’s PageRank and beyond— The science of search engine rankings, Princeton University Press(2006).
［148］ Lee. D. -S. : Synchronization transition in scale-free networks:

clusters of synchrony. Physical Review E, Vol. 72, article No. 026208(2005).
［149］ Liggett, T. M. : Interacting particle systems, Springer (1985).
［150］ Liljeros, F., Edling, C. R., Amaral, L. A. N., Stanley, H. E., Åberg,

Y. : The web of human sexual contacts. Nature, Vol. 411, pp. 907–908(2001).
［151］ Mahmoud, H. M., Smythe, R. T., Szymański, J. : On the structureof random plane-oriented recursive trees and their branches. Random
Structures and Algorithms, Vol. 4, pp. 151–176 (1993).
［152］ Manrubia, S. C., Mikhailov, A. S., Zanette, D. H.: Emergence ofdynamical order — Synchronization phenomena in complex systems.
World Scientiﬁc (2004). の第 4 章［153］ Masuda, N., Miwa, H., Konno, N. : Analysis of scale-free networks

based on a threshold graph with intrinsic vertex weights. PhysicalReview E, Vol. 70, article No. 036124 (2004).
［154］ Masuda, N. : Participation costs dismiss the advantage of hetero-geneous networks in evolution of cooperation, Proceedings of the Royal
Society B: Biological Sciences, Vol. 274, pp. 1815–1821 (2007).
20

論文名つきの文献リスト［155］ Masuda, N., Ohtsuki, H. : Evolutionary dynamics and ﬁxation

probabilities in directed networks. New Journal of Physics, Vol. 11,
article No. 033012 (2009).
［156］ May, R. M., Anderson, R. M. : The transmission dynamics ofhuman immunodeﬁciency virus (HIV). Philosophical Transactions of
the Royal Society of London B, Vol. 321, pp. 565–607 (1988).
［157］ May, R. M., Lloyd, A. L. : Infection dynamics on scale-free net-

works. Physical Review E, Vol. 64, article No. 066112 (2001).
［158］ Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D.,

Alon, U. : Network motifs: simple building blocks of complex networks. Science, Vol. 298, pp. 824–827 (2002).
［159］ Milo, R., Itzkovitz, S., Kashtan, N., Levitt, R., Shen-Orr, S.,

Ayzenshtat, I., Sheﬀer, M., Alon, U. : Superfamilies of evolved anddesigned networks. Science, Vol. 303, pp. 1538–1542 (2004).
［160］ 宮下直，野田隆史：『群集生態学』，東京大学出版会 (2003). の第 5 章［161］ Moore, C., Newman, M. E. J. : Epidemics and percolation in small-world networks. Physical Review E, Vol. 61, pp. 5678–5682 (2000).
［162］ Moore, C., Newman, M. E. J. : Exact solution of site and bondpercolation on small-world networks. Physical Review E, Vol. 62, pp.
7059–7064 (2000).
［163］ Moreno, Y., Pastor-Satorras, R., Vespignani, A. : Epidemic out-

breaks in complex heterogeneous networks. European Physical Journal
B, Vol. 26, pp. 521–529 (2002).
［164］ Motter, A. E., Lai, Y. -C. : Cascade-based attacks on complex

networks. Physical Review E, Vol. 66, article No. 065102(R) (2002).
［165］ Motter, A. E. : Cascade control and defense in complex networks.

Physical Review Letters, Vol. 93, article No. 098701 (2004).
［166］ Motter, A. E., Zhou, C., Kurths, J. : Network synchronization,

diﬀusion, and the paradox of heterogeneity. Physical Review E, Vol.
71, article No. 016116 (2005).
［167］ Motter, A. E., Zhou, C. S., Kurths, J. : Enhancing complex21

network synchronization. Europhysics Letters, Vol. 69, pp. 334–340(2005).
［168］ Newman, M. E. J., Moore, C., Watts, D. J. : Mean-ﬁeld solutionof the small-world network model. Physical Review Letters, Vol. 84,
pp. 3201–3204 (2000).
［169］ Newman, M. E. J., Strogatz, S. H., Watts, D. J. : Random graphswith arbitrary degree distributions and their applications. PhysicalReview E, Vol. 64, article No. 026118 (2001).
［170］ Newman, M. E. J. : Assortative mixing in networks. Physical Re-

view Letters, Vol. 89, article No. 208701 (2002).
［171］ Newman, M. E. J. : Spread of epidemic disease on networks. Phys-

ical Review E, Vol. 66, article No. 016128 (2002).
［172］ Newman, M. E. J. : Fast algorithm for detecting community struc-ture in networks. Physical Review E, Vol. 69, article No. 066133 (2004).
［173］ Newman, M. E. J., Girvan, M. : Finding and evaluating community

structure in networks. Physical Review E, Vol. 69, article No. 026113(2004).
［174］ Newman, M. E. J. : A measure of betweenness centrality based on

random walks. Social Networks, Vol. 27, pp. 39–54 (2005).
［175］ Newman, M. E. J. : Finding community structure in networks

using the eigenvectors of matrices. Physical Review E, Vol. 74, article
No. 036104 (2006).
［176］ Nishikawa, T., Motter, A. E., Lai, Y. -C., Hoppensteadt, F. C. :Heterogeneity in oscillator networks: are smaller worlds easier to synchronize? Physical Review Letters, Vol. 91, article No. 014101 (2003).
［177］ Nishikawa, T., Motter, A. E. : Maximum performance at minimum

cost in network synchronization. Physica D, Vol. 224, pp. 77–89 (2006).
［178］ Noh, J. D., Rieger, H. : Random walks on complex networks. Phys-

ical Review Letters, Vol. 92, article No. 118701 (2004).
［179］ de Nooy, W., Mrvar, A., Batagelj, V. : Exploratory social network

analysis with Pajek, Cambridge University Press (2005). ウオウター・22論文名つきの文献リスト

デノーイ，アンドレイ・ムルヴァル，ヴラディミール・バタゲーリ（安田雪監訳）：『Pajek を活用した社会ネットワーク分析』，東京電機大学出版
局 (2009).
［180］ Nowak, M. A., May, R. M. : Evolutionary games and spatial chaos.

Nature, Vol. 359, pp. 826–829 (1992).
［181］ Nowak, M. A. : Evolutionary dynamics — Exploring the equationsof life, The Belknap Press of Harvard University Press (2006). 中岡慎治，巌佐庸，竹内康博，佐藤一憲訳：『進化のダイナミクス — 生命の謎を解き明かす方程式』，共立出版 (2008).
［182］ 小田垣孝：『パーコレーションの科学』，裳華房 (1993).
［183］ 小田垣孝：『つながりの科学 — パーコレーション』，裳華房 (2000).
［184］ 大串隆之，近藤倫生，難波利幸編：『生物間ネットワークを紐とく』，
京都大学学術出版会 (2009).
［185］ Ohtsuki, H., Hauert, C., Lieberman, E., Nowak, M. A. : A simple

rule for the evolution of cooperation on graphs and social networks.
Nature, Vol. 441, pp. 502–505 (2006).
［186］ 大浦宏邦：『社会科学者のための進化ゲーム理論 — 基礎から応用まで』，勁草書房 (2008).
［187］ Onnela, J. -P., Saramäki, J., Hyvönen, J., Szabó, G., Lazer, D.,

Kaski, K., Kertész, J., Barabási, A. -L. : Structure and tie strengths inmobile communication networks. Proceedings of the National Academyof Sciences of the United States of America, Vol. 104, pp. 7332–7336(2007).
［188］ Palla, G., Derényi, I., Farkas, I., Vicsek, T. : Uncovering the over-lapping community structure of complex networks in nature and society. Nature, Vol. 435, pp. 814–818 (2005).
［189］ Pastor-Satorras, R., Vespignani, A. : Epidemic spreading in scale-free networks. Physical Review Letters, Vol. 86, pp. 3200–3203 (2001).
［190］ Pastor-Satorras, R., Vespignani, A. : Immunization of complex

networks. Physical Review E, Vol. 65, article No. 036104 (2002).
［191］ Pecora, L. M. : Synchronization of oscillators in complex networks.
23

Pramana Journal of Physics, Vol. 70, pp. 1175–1198 (2008).
［192］ Pittel, B. : Note on the heights of random recursive trees andrandom m-ary search trees. Random Structures and Algorithms, Vol.
5, pp. 337–347 (1994).
［193］ de Solla Price, D. : A general theory of bibliometric and othercumulative advantage processes. Journal of the American Society for
Information Science, Vol. 27, pp. 292–306 (1976).
［194］ Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., Barabási,

A. -L. : Hierarchical organization of modularity in metabolic networks.
Science, Vol. 297, pp. 1551–1555 (2002).
［195］ Ravasz, E., Barabási, A. -L. : Hierarchical organization in complex

networks. Physical Review E, Vol. 67, article No. 026112 (2003).
［196］ Reichardt, J., Bornholdt, S. : Detecting fuzzy community struc-tures in complex networks with a Potts model. Physical Review Letters, Vol. 93, article No. 218701 (2004).
［197］ Reichardt, J. : Structure in complex networks, (Lecture Notes inPhysics 766), Springer (2009).
［198］ Restrepo, J. G., Ott, E., Hunt, B. R. : Onset of synchronizationin large networks of coupled oscillators. Physical Review E, Vol. 71,
article No. 036151 (2005).
［199］ Rodgers, G. J., Austin, K., Kahng, B., Kim, D. : Eigenvalue spec-

tra of complex networks. Journal of Physics A, Vol. 38, pp. 9431–9437(2005).
［200］ Rosvall, M., Bergstrom, C. T. : Maps of random walks on com-plex networks reveal community structure. Proceedings of the National
Academy of Sciences of the United States of America, Vol. 105, pp.
1118–1123 (2008).
［201］ Rozenfeld, H. D., ben-Avraham, D. : Designer nets from local

strategies. Physical Review E, Vol. 70, article No. 056107 (2004).
［202］ Rozenfeld, H. D., Havlin, S., ben-Avraham, D. : Fractal and trans-

fractal recursive scale-free nets. New Journal of Physics, Vol. 9, article24論文名つきの文献リスト

No. 175 (2007).
［203］ 斉藤和巳：『ウェブサイエンス入門 — インターネットの構造を解き明かす』，NTT 出版 (2007).
［204］ Sakaguchi, H., Shinomoto, S., Kuramoto, Y. : Local and global

self-entrainments in oscillator lattices. Progress of Theoretical Physics,
Vol. 77, pp. 1005–1010 (1987).
［205］ Sakaguchi, H., Shinomoto, S., Kuramoto, Y. : Mutual entrainment

in oscillator lattices with nonvariational type interaction. Progress ofTheoretical Physics, Vol. 79, pp. 1069–1079 (1988).
［206］ Santos, F. C., Pacheco, J. M. : Scale-free networks provide a uni-fying framework for the emergence of cooperation. Physical Review
Letters, Vol. 95, article No. 098104 (2005)［207］ Santos, F. C., Pacheco, J. M. : A new route to the evolution ofcooperation. Journal of Evolutionary Biology, Vol. 19, pp. 726–733(2006).
［208］ Shen-Orr, S. S., Milo, R., Mangan, S., Alon, U. : Network motifs

in the transcriptional regulation network of Escherichia coli. Nature
Genetics, Vol. 31, pp. 64–68 (2002).
［209］ Söderberg, B. : General formalism for inhomogeneous randomgraphs. Physical Review E, Vol. 66, article No. 066121 (2002).
［210］ Solé, R. V., Pastor-Satorras, R., Smith, E., Kepler, T. B. : A modelof large-scale proteome evolution. Advances in Complex Systems, Vol.
5, pp. 43–54 (2002).
［211］ Song, C., Havlin, S., Makse, H. A. : Self-similarity of complex

networks. Nature, Vol. 433, pp. 392–395 (2005).
［212］ Song, C., Havlin, S., Makse, H. A. : Origins of fractality in thegrowth of complex networks. Nature Physics, Vol. 2, pp. 275–281(2006).
［213］ Stauﬀer, D., Aharony, A. : Introduction to percolation theory (Re-vised second edition), Taylor & Francis (1994). D. スタウファー，A.
アハロニー（小田垣孝訳）：『パーコレーションの基本原理』，吉岡書店
25

(2001).
［214］ Szymański, J. : On a nonuniform random recursive tree. Annals of

Discrete Mathematics, Vol. 33, pp. 297–306 (1987).
［215］ Szymański, J. : On the maximum degree and the height of a ran-

dom recursive tree. in Proceedings of Random Graphs ’87, pp. 313–324(1990).
［216］ Tomassini, M., Pestelacci, E., Luthi, L. : Social dilemmas andcooperation in complex networks. International Journal of Modern
Physics C, Vol. 18, pp. 1173–1185 (2007).
［217］ Vázquez, A., Boguñá, M., Moreno, Y., Pastor-Satorras, R., Vespig-

nani, A. : Topology and correlations in structured scale-free networks.
Physical Review E, Vol. 67, article No. 046111 (2003).
［218］ Vázquez, A., Flammini, A., Maritan, A., Vespignani, A. : Modelingof protein interaction networks. ComPlexUs, Vol. 1, pp. 38–44 (2003).
［219］ Watts, D. J., Strogatz, S. H. : Collective dynamics of ‘small-world’

networks. Nature, Vol. 393, pp. 440–442 (1998).
［220］ Watts, D. J., Dodds, P. S., Newman, M. E. J. : Identity and searchin social networks. Science, Vol. 296, pp. 1302–1305 (2002).
［221］ Yoon, I., Williams, R., Levine, E., Yoon, S., Dunne, J., Martinez,

N. : Webs on the Web (WOW): 3D visualization of ecological networks
on the WWW for collaborative research and education. in Proceedingsof the IS&T/SPIE Symposium on Electronic Imaging, Visualization
and Data Analysis Section, Vol. 5295, pp. 124–132 (2004).
［222］ Zachary, W. W. : An information ﬂow model for conﬂict and ﬁssion

in small groups. Journal of Anthropological Research, Vol. 33, pp. 452–
473 (1977)

26

■本補遺の著作権は著者に属しますが，無償でダウンロード可能です。内容を引用するときは引用箇所に，「 複 雑 ネ ッ ト ワ ー ク 補 遺 （ PDF 版 ） ／ ©2010 Naoki
Masuda & Norio Konno／近代科学社刊」と記してください。

複雑ネットワーク 補遺（PDF 版）©2010 Naoki Masuda & Norio Konno
2010 年 4 月 30 日発行

著 者

増 田 直 紀今 野 紀 雄発行者

千 葉 秀 一

発行所(株)近代科学社〒162-0843 東京都新宿区市谷田町 2-7-15
電話 03(3260)6161 http://www.kindaikagaku.co.jp

本書は近代科学社刊『複雑ネットワーク（ISBN 978-4-7649-0363-0）』の付録です。