barabási-albertモデ - prof. tadaki's home...
TRANSCRIPT
![Page 1: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/1.jpg)
Barabási-Albertモデルモデリングとシミュレーション2018年度
![Page 2: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/2.jpg)
scale-free network
現実のネットワークの次数分布べき則:𝑃𝑃 𝑘𝑘 ∼ 𝑘𝑘−𝛾𝛾
べき則 (power-law)特徴的長さが無い:scale-free単位を変えても同じ関数形
スケール変換に対して不変
( ) ( )ak a kP Pγ−=
2
![Page 3: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/3.jpg)
例1:論文の引用
新しい論文が書かれると、他の論文を引用する。
論文は日々生産される。非平衡ネットワークを形成する。良く引用される論文は、多くの人に読まれ、さらに引用される。
引用ネットワークでは、引用の多い論文ほど、多くの引用を引き寄せる
3
![Page 4: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/4.jpg)
S. Rednerによる研究 Eur. Phys. J. B 4 (1998)
131.
ISI (Institute for Scientific Information)のデータ
Physical Review D のデータ
引用回数x である論文数の分布
3~( )N x x−
4
![Page 5: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/5.jpg)
例2:WWW
新しいページを作る他へのリンクを含む他のページからリンクされる新しい内容に更新される
検索サイトに掲載されると、アクセスが増える
5
![Page 6: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/6.jpg)
R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130.
In-degree もout-degreeも べき則分布(図a,b)
平均の最短距離は総頂点数の対数に比例して増大
10= 0.35 + 2 log.06 d N
out in~ ~ 2.45, ( ) ~ 2.1p k k γ γ γ−
6
![Page 7: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/7.jpg)
InternetのAS(Autonomous Systems)間の接続
R. Pastor-Satorras, A. Vázquez and A. Vespignani, Phys. Rev. Lett. 87 (2001) 258701.
( ) , ~ ~ 2.2P k k γ γ−
7
![Page 8: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/8.jpg)
英単語の連結
R. Ferrer i Cancho and R. Solé, Proc. R. Soc. B 268 (2001) 2261.
~ 2.6d1.5( ) ~ kP k −
8
![Page 9: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/9.jpg)
成長するネットワーク
実際のネットワークは成長し続けているインターネットWebページのリンク
新しくできた頂点は、既存の節へ辺を生成する既存の頂点の性質に依存せずにランダムに対象を選択
既存の頂点の次数などの性質に依存してランダムに対象を選択
9
![Page 10: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/10.jpg)
成長するランダムネットワーク
多重接続を許す無向ネットワーク初期時刻(𝑡𝑡 = 2)で、二個の頂点を二本の辺で接続
10
1 2
![Page 11: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/11.jpg)
各時刻で、一つの頂点を追加し、既存の頂点を次数に比例する確率でランダムに選択して接続次数𝑘𝑘の頂点が選ばれる確率:𝑘𝑘/(2𝑡𝑡)次数の総和が2𝑡𝑡であることに注意
各時刻𝑡𝑡で、𝑡𝑡個の頂点と𝑡𝑡本の辺各頂点に、その頂点ができた時刻の番号𝑠𝑠を付ける
11
![Page 12: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/12.jpg)
12
1 2
3
3t =
1 2
3
4t =
4
1 2
3
5t =
4
5
![Page 13: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/13.jpg)
13
![Page 14: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/14.jpg)
頂点𝑠𝑠に𝑘𝑘本の辺がある確率
時刻𝑡𝑡に存在する頂点数は𝑡𝑡時刻𝑡𝑡 + 1で頂点𝑠𝑠の次数が𝑘𝑘になるには時刻𝑡𝑡で、次数が𝑘𝑘 − 1であり、新しく生成された頂点から、選ばれ、辺が生成される:確率(k − 1)/(2𝑡𝑡)
時刻𝑡𝑡で、次数が𝑘𝑘であり、新しく生成された頂点から、選ばれず、辺が生成されない:確率1 − 𝑘𝑘/(2𝑡𝑡)
( ) ( ) ( )1, , 1 1, , 1 , ,2 2
k kk s t p k s t p k s tpt t− + = − + −
14
![Page 15: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/15.jpg)
初期条件初期の二つの頂点の次数は2
新しい頂点の次数は1
ある時刻で存在する頂点に関する平均
{ }( ) ,2, 1, 2 , 2 kp k s t δ= = =
( ) ,1, , 2 kp k s t t δ= > =
( ) ( )1
1 , ,,t
sp k sP t t
tk
=
= ∑
15
![Page 16: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/16.jpg)
( ) ( ) ( )
( ) ( ) ( ),
1 1 1
1
1 1 11
1, , 1 1, , 1 , ,2 2
1, , 1 1, , 1 , ,2 2
t t t
s s s
t t
sk
t
s s
k kk s t k s t k s tt t
k kk s t k s t k s
p p p
p p tt
pt
δ
= = =
+
= = =
− + − + −
− + − + −
−
=
=
∑ ∑ ∑
∑ ∑ ∑
左辺の計算に注意• 時刻が𝑡𝑡 + 1であること• 和の上限
16
![Page 17: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/17.jpg)
Master方程式の両辺の平均をとる
( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( )
,1
,1
,1
1, 1 1, 1 ,2 2
11 , 1 , 1 1,
1
1
, 1
,2
11 1, ,2
, ,
k
k
k
k kk t P k t t P k tt
t
P
P k t tP k t k
t P
t P k t P k t t
P k t kP k t
k P k t kP kk t
δ
δ
δ
− + − = − + −
+ + − = − − − +
− − − +
+
+ − + + =
17
![Page 18: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/18.jpg)
平衡解
長時間後に確率分布が一定になるとする
平衡解に対する方程式
( ) ( ), t Pk t kP →∞→
( ) ( ) ( ) ( ) ,12 1 1 2 kk P k k P k δ+ − − − =
18
![Page 19: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/19.jpg)
平衡解
べき関数分布
( ) ( )
( )
1 1 for 12
213
kP k P k kk
P
−= − >
+
=
( ) ( )( )
( )3 231
42 1
4
P
O
k
k
k
kk
kk
− − − +
=+ +
=
19
![Page 20: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/20.jpg)
規格化されているか確認
20
( )( ) ( ) ( )( )
( ) ( )( )
( )( )
( )( ) ( )( )
1 1
1 1
1 1
1 2 1 1 2
1 1 2
4 1 12
1 12 2
1 121 2
lim1 2
2
41 24 1
N N
k k
N N
k
N
k
N
k k
k k k k k
k k k
N
k k
k
N
k k k kk k
= =
= =
= =
∞
→∞
+ + + + +
+ + +
+ +
+
= −
= −
+ +
= −
=+
=
∑ ∑
∑ ∑
∑ ∑
![Page 21: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/21.jpg)
21
頂点数100000
![Page 22: Barabási-Albertモデ - Prof. Tadaki's Home Pageaoba.cc.saga-u.ac.jp/lecture/ModelingAndSimulation/PDF...R. Albert, H. Jeong & A.-L. Barabási, Nature 401, (1999) 130. In-degree もout-degreeも](https://reader033.vdocumento.com/reader033/viewer/2022043013/5fad91fd72446e003b16a64d/html5/thumbnails/22.jpg)
22
1( ) 1 ( )
k
jS k P j
=
= −∑