An overview of the Small

An overview of the SmallWorld Phenomenon
Bernard Lamers
社会システムの性質:
small world(1)



社会システムは、物理学的なシステムと
違って、transivity of distancesを違反して
いる。
Transitive distanceの条件: 三角不等式が
成り立つこと。
三角不等式：ある空間の中の点a、点b、点
cを三角の頂点とすると、次の式が成り立
つ：
d(a,c) ≦ d(a, b) + d(b, c)
社会システムの性質:
small world(2)


人aは人bと、そして人bは人cと密接の関
係にいる。従って、d(a, b)とd(b, c)が割と
小さいと考えられる。ただし、人aと人cはお
互いの存在を知らないとすると、d(a, c)が
大きいということになる。
三角不等式が明らかに成り立っていない。
Small worldに関しての
今までの研究


1950年代： RapoportやSolomonoffが
randomly connected networkにおける拡
散の研究を開始。
仮定：



各connectionが他のconnectionから独立
各ノードのconnection数がほぼ同じ
問題：病気がどのように蔓延するか
病気の蔓延：単純なモデル(1)



最初は人口のP(0) (P(0)<<1)が感染して
いる。言い換えれば、人口の(1-P(0))分は
最初は感染していない。
各connectionが独立であるので、蔓延は
指数関数
各ステップではP(t)メンバーが新しく感染す
Tが大きく
る。前のステップで感染していない人口分
なると
P(t) = (1 – ΣP(i)) (1 – e
-kP(t-1)
1に近づく
)
ともに、
P(t-1)も
大きくなる。
病気の蔓延：単純なモデル(2)



tが十分大きくなると、感染している人口分
ηは次の式で表すことができる：
η=1-( 1-P(0) )e-kη
以上の式の特徴：


指数関数
P(0)とkが与えられているなら、ηが決まる。
現実主義に向けて（１）

単純なモデルに次の改良が付け加えられ
た。


connection先は人口の有限部分集合から選
択。
友人サークルが重なっている。つまり、
connectionは独立ではない。
現実主義に向けて(2)

biasの導入




Homophily: 自分らしい人を友達にする
Symmetry of edges: edgesはundirected（説明は
後述）。
Triad closure: 自分の友人・知り合いのなか、お
互いに知っている人が多い。
Social differentiation: 社会はいくつかの異質
のグループから成っている。グループ内の接
触はグループ外より多い。
その他の改良


Rapoport(1957):感染した人aがk人の人と
接触しても、そのk人の中にはすでに感染
している人もいる
有効効果κ(t).
κ(t)≦k.
Fararo and Sunshine(1964),
Skvoretz(1985): κ(t)=κ、定数κにはbias
が反映されている (p. 13, 式(2.3)).
p.13, 式(2.3)


Triad closure bias: 自分の友人・知り合
いのなか、お互いに知っている人が多い。
Strong ties/weak ties:



人a、人b
a、またはb、またはaとbの両方とつながりがあ
る人の集合。
aとbを両方知っている人の割合が大きくなれ
ばなるほど、aとbのつながりが強い。
Weak tiesは
strong tiesより大事(1)

ζ=ζs(1 - qS)
=ζs(1 - q(1 – ζw/ζs)))
=ζs(1 – q + q(ζw/ζs))
=ζs- qζs+qζw
=(1 - q)ζs +qζw
Weak tiesは
strong tiesより大事(2)

ζs =0.7, ζw= 0.2, q=0.7, k=10の場合：


ζ=0.35, κ=3.48
ζs =0.7, ζw= 0.2, q=0.9, k=10の場合：

ζ=0.21, κ=5.80
蔓延が早い。
Density（密度）

ネットワークの中にはtriadic closureが高
いところとtriadic closureが低いところがあ
る。
Densityとblock modellingの研
究方法

Barnes(1969):
ノードvと近所のノードとの間に実際にあるconnectionの数
Density=
vの近所に存在し、なおかつvとconnectionがありうるノード数

Density(local property)とネットワーク全
体のpropertyを関連させるモデル：block
model。 Block modelはlocal(e.g.density)
やnon-local(e.g.weak ties)の素性でネット
ワークを記述する。
ネットワークのもう一つの研究
方法：Multidimensional scaling




人口は有限の空間の中に存在する。
メンバーの座標でそのメンバーを識別でき
る。
観察者はメンバーの座標も空間の次元も
観察できない。観察できるのはメンバーの
間の距離。距離は接触の頻度、類似性な
どによる。
問題：空間の再構成
空間の再構成


Metric methods, 式2.4
Non-metric methods, 式2.5


Non-metric methodはmetricではあるが、
Euclidean metricではない。
空間の再構成はデータへの理解を高める
ために行う。空間の次元は4以上だと、理
解は高まらない。
研究方法の一覧




Block model系のアプローチ
空間の再構成
ネットワークの中のパスを統計分析するア
プローチ
ネットワークのrenormalisation:networks
are viewed as meta-networks of highly
clustered or equivalent subnetworks.
研究方法を発展させた
実証的研究


Milgram(1967):Nebraska州やKansas州
在住の協力者に郵便物をMassachusetts
州の方に送るよう頼んだ。条件：郵便物は
郵便ではなく、知り合い経由で送らなけれ
ばならない。
結果：届くまでに平均で５人の仲介人が必
要
順序づけられたネットワーク vs.
ランダムなネットワーク

統計的な性質を分析できるネットワークは


完全に順序づけられたネットワーク
完全にランダムなネットワーク
である。以上の種類のネットワークでは
localな構造が全体的な構造に反映されて
いる。残念ながら、社会のネットワークがそ
の性質を持っていない
スペクトル
のどこにあるか？
社会ネットワークに関する
三つの大事な問題点



社会のネットワークがbridgesのような完全に
non-localな要素を含んでいるので、localの分析
でネットワーク全体を記述できない。
ネットワークのサイズが増えるとともに、分析の
問題が複雑になる。サイズが大きいが、
connection数が小さいネットワークを対象にした
研究があまりない。
スペクトルの中のネットワークの性質に迫る方法
として連続ネットワークの研究が考えられる。た
だし、その研究が数少ない。
四番目の問題点：
社会的な距離の定義



距離の基準として接触の頻度、興味の一
致などが考えられる。
ただし、これらの基準は三角不等式を違反
している。
三角不等式が成り立っていないことは


距離の基準が間違っているまたは
空間はmetricの空間ではない
と意味している。
社会的な距離


理論：社会的な距離は何を意味している?
その概念にどの要因がかかわっている?
概念がわかっているとしても、社会的な距
離は(1)観察者のbias(2)問われた質問(3)
ネットワークのメンバーによるので、社会的
な距離を客観的にどう計れるかという問題
にも取り込まなければならない。
Network distance

ネットワークの場合、距離をconnectionに
基づいて定義できる
network
distance。



ノードaとその唯一の隣のノードb: n.d. 1
ノードaとノードbの隣のノードc: n.d. 2
Network distanceを採用することで、
nonmetric, non-Euclidianの問題を防ぐこ
とができる。
問題の一般化


いままでは社会のネットワーク
ただし、私たちが扱いたい問題はsmall
world現象を示すシステムの性質は最も一
般に言えば、どの特徴を持っているか。そ
してその性質はネットワークを作るために
使われたモデルに依存しているかどうかで

ある。
答えるためにグラフ理論の知識が必要
グラフ理論：基本の定義




グラフの基本定義：Definition 2.2.1
(p.25)
グラフのorder: |V(G)|
グラフのsize: |E(G)|
Edgeは二つのverticesがどの関係にある
かを表す。
この研究で対象にする
グラフの性質(1)

研究の対象を絞るため、グラフに次の制約
を設ける



Undirected: edgeには子-親、学生-先生など
の関係に現れる方向性を認めない。
Unweighted:edgeには重みをつけない。
Simple:同じ対を結ぶ複数のedges、またはあ
るvertexをその同じvertexと結ぶedgeを許さ
ない。
この研究で対象にする
グラフの性質(2)


Sparse:undirected(and simple?)グラフの最
高のサイズMはn(n-1)/2になる。Sparseness
はグラフの実際のサイズは<<n(n-1)/2の制
約である。
Connected:グラフの中のどのvertexにも他の
vertexから有限のパスで到着できる。
Adjacency matrix/
adjacency list


Adjacency matrix: n x nのmatrix. Mi,jはi
とjを結ぶedgeの数（私たちの場合1または
0)
Adjacency list:すべてのverticesのリスト。
各vertexの隣にそのvertexと結ばれている
verticesのリストが登録されている。
Degree of a vertex/
average degree



Vertex vと結ばれているedgeの数:degree
of v、記法: kv
グラフのすべてのverticesの平均の
degree: average degree
すべてのverticesが同じdegreeを持ってい
るグラフはk-regularまたは単にregularと
いう。
Characteristic path length



Characteristic path length L(G):各vertex
から残りの各vertexまでの最短な距離の
平均
距離:network distance
Characteristic path lengthを正確に得ら
れる式がまだ存在しない。
Characteristic path length
の推測(1)



Characteristic path lengthは各d(i, j)の平
均として取れない。nが大きくなると、この
方法を実際に行うのは困難。
Random samplingを使い、平均に近づく。
実は平均よりmedian shortest pathの方
が取りやすい。相称的な分布の場合、平
均とmedianがほぼ同じ。
Characteristic path length
の推測(2)


Medianの欠点:整数。
Verticesの数nを増やすと、characteristic
path lengthがどう変わるかが大事な問題。
ただし、nをseveral orders of magnitude
増やしても、characteristic path lengthの
orderが変わらないときがあるので、整数
のc.p.l.は情報が足りない
Def. 2.2.2
Scaling


Scaling: nまたはkが変わるとc.p.l.はどう
変わる?
Scalingはグラフのトポロジー（ネットワーク
のedgeの形状）に迫るには大事
Scalingの例





One-parameter family of graphs（３章）,
parametrized by some parameter p.
パラメータpがグラフの無限集合を定義
1≦c.p.l.≦∞
Scaling propertiesは集合全体は同じ
pが小さいグラフの特性を計算し、scaling
を使って,pが大きいグラフの性質に迫る。
Neighbourhoods and
distribution sequences


Neighbourhood and distribution
sequencesは情報がどのペースでネット
ワークの中で広がるかを形式化する概念
である。
定義は2.2.5(p.31)-2.2.9(p.32)
Clustering



Clustering coefficient: Γ(v)の中にある二
つのverticesが結ばれている確率
定義:2.2.10 (p.33)
今まで紹介した概念でlattice graphs(dlattices)とrandom graphsの基本研究が
可能。
Lattice graphs (d-Lattices)




定義:2.2.12
例：figure 2.3、 2.4、 2.5
D-latticesはlength-scalingとclusteringの
特性で特徴付けられる。
1-latticeの場合


L scales linearly with respect to n and
inversely with respect to k
γ is independent of n, and –for large kalso independent of k.

Download Report