next up previous
Next: ݻ Up: ģ Previous: Small World

Scale Free

Small Worldо֮ԽԽĿѧͶ뵽оȥҷʵҲкܴ ϵԺضĽṹܹϵScale FreeеһҪ档Scale FreeָĶȷֲʷֲ ȱһ߶ȶΪޱ硣Ƕ֪ͳѧٽԼ֯ٽԣSOCʾ λ[25]ֶȷֲޱǷҲ϶ѧģ͵أҲһĶѧʼܽᡣʵ֤о ֣ʵԱΪScale Free[1]2

42ʵScale FreeбаоʵʶNetworkСSize ƽֵ< k >Outʷֲָ $ \gamma_{{out}}^{}$Inʷֲָ $ \gamma_{{in}}^{}$ ƽ̾루l̾루lrandɼScale FreeһSmall World ˱[1]Ļռȷױ༭ɣлR. Albertṩ

Network Size $ \left\langle\vphantom{ k}\right.$k$ \left.\vphantom{ k}\right\rangle$ $ \gamma_{{out}}^{}$ $ \gamma_{{in}}^{}$ lreal lrand
WWW[50] 325, 729 4.51 2.45 2.1 11.2 8.32
WWW[29] 43, 107 7 2.38 2.1
WWW[27] 23, 108 7.5 2.72 2.1 16 8.85
WWW[30], site 260, 000 1.94
Internet[44], domain 3015 - 4389 3.42 - 3.76 2.1 - 2.2 .1 - 2.2 4 6.3
Internet[44], router 3888 2.57 2.48 2.48 12.15 .75
Internet[45], router 150, 000 2.66 2.4 2.4 11 12.8
Movie actors[18] 212, 250 28.78 2.3 2.3 4.54 3.65
Co-authors[66] , SPIRES 56, 627 173 1.2 1.2 4 2.12
Co-authors[67] , neuro. 209, 293 11.54 2.1 2.1 6 .01
Co-authors[67], math. 70, 975 3.9 2.5 2.5 9.5 8.2
Sexual contacts[47] 2, 810 3.4 3.4
Metabolic[51] , E. coli 778 7.4 2.2 2.2 3.2 3.32
Protein[48] , S. cerev.* 1, 870 2.39 2.4 2.4
Citation[65] 783, 339 8.57 3
Phone call[28] 533, 106 3.16 2.1 2.1
Words[49], co-occurrence* 460, 902 70.13 2.7 2.7

Scale FreeγɻơĿǰScale Free磬ձΪƫPreferential Attachment[18]һܺõ γScale FreeĻơģ¡ȡʼm0ӻȫӡÿһԭ G$ \left(\vphantom{t-1}\right.$t - 1$ \left.\vphantom{t-1}\right)$Ļϼ һµĶ㣬ͬʱϴӴ˶mߣγµ G$ \left(\vphantom{t}\right.$t$ \left.\vphantom{t}\right)$¼ӱߵһ˵㰴ڶķ

$\displaystyle \pi_{u}^{}$ = $\displaystyle {\frac{{d_u}}{{\sum_{v \in V} d_v}}}$ (13)
ѡȡظ¼ӵĹ㹻ಽγɵĸĶʷֲ p$ \left(\vphantom{k}\right.$k$ \left.\vphantom{k}\right)$ $ \sim$ k-$\scriptstyle \gamma$ͼ(3)ң ָ$ \gamma$ = 3ģ͵IJm0, m޹ءһֵģmȡijһΧڵʱָҲ䡣

Fig 3: ƫģĶȷֲ(a)ȷֲmm0ĸıı䣬 m0 = m ֱȡֵΪ1,3,5,7(b)ڲͬʱ̣N=100000,150000,200000ȡm0 = m = 5õĶȷֲȫ غϣСͼĶֵݻߣ뷽(\ref{ki})ͼȡ[21]

ʵָ$ \gamma$ = 3е߷չBarabásiAlbertԭʼƫģͣʹָģͲ ƫģУvĶֵkvΪĶôʱƣȥƷ֮⣬ Ķʱһ˶ʷģ[23]Ըıָ$ \gamma$Ŀɵģƻʷֲģ ͨǸһݻ̵õ

һҪĶƫģ͵ҪƫģͲܸеΪScale Freeľ̬ڴʵScale Free չֵSmall World ģ͸˽ϺõĽģ͵ĶȶΪ㣬ʵдڵƥģʽ[16]Ĺ ʵģ͵ĶԱȣԼڶԱȻ϶ģ͵޸ĹкֵܶĵطGoh OhȸģϵĽķֲ [17]Ǹ㷺ʵ֤ȻдɡЩĻ߲󶼸ģƹ޸ĵķ

Ϊһһݻ ĿЩǿԽģǵأһһݻ󣺼ӵ㡢ӱߡȥߡȥ㡣νӵtʱ ͼ G$ \left(\vphantom{t-1}\right.$t - 1$ \left.\vphantom{t-1}\right)$ϼµĶ㣬ҼɴӴ˶ıߣӱָtʱ G$ \left(\vphantom{t-1}\right.$t - 1$ \left.\vphantom{t-1}\right)$ԭж֮ ӣȥȥϹ̵棻ȥߺӱߺֻеӱߺȥ߷ͬһϵʱŸպ Լ¼ļпܴȥߺͼӱ߷֮˻԰ĿǰݻģͶ ¼ķΧۡ

һǿƫģֻ˼ӵΪֻǶڼӵԺĴ¼ӵƫԼٶ BarabásiAlbertģԺ˴ģ͵ıDorogovtsevMendesSamukhinģ[19]¼ӵ֮ m¼ӱ߿ԲӴ˵ģͣάƫԲ䡣ģͻInOutߣһInĸΪv Av = A + kinvģҲܳʵĶȷֲָɵ $ \gamma$ = 2 + $ {\frac{{A}}{{m}}}$ʵǿԿʵϣ ģ൱ڿ˼ӵͼӱ飬ֻ¼ӵı߲һȷڲԭе֮¼ӱҲȷȻ άƫԡֻInȷֲʱ򣬿Ժ¼ӱOut˵ѡֻIn˵ƫԡ

ּ̽ӵƫģеIJͬλһֻǼӵ㣬ǴµıߵĶ˵ѡƫԣ ѡȡģ͸ָ˥ķֲ[18]һֻǼӱߡһdzϡ NMߵ翪ʼÿһѡһ㣬Ȼƫѡһ㣬ӵıߣ֮ ͬʱǻƫƫãһ˵ѡ͵ڶ˵ѡ񶼰ƫʽȻ ظĴӣģͽȫ磬ģ͵̬ȻʷֲġǣǷһݻ䣬ڴ˷Χڣ ʷֲأ֪˵㶼ѡģͣĶȷϲɷֲôƫ÷ʽѡģ أһʱγʷֲĻ˵ƫأν¼ӵֻʹȡijƽ⣬ڷչΪ ȫѡBarabási˾оһģ[21]ݻijȷʵʽĶֲֵʱ ݻ𽥹ɵ˹ֲ˵ƫScale FreeĺĻƣ¼ӵҲɻȱ

AlbertBarabásiĵڶScale FreeĻģ[32]˼ӵ㡢ӱߡ¼ÿһʱֱijһ $ \left(\vphantom{1-p-q, p, q}\right.$1 - p - q, p, q$ \left.\vphantom{1-p-q, p, q}\right)$κһ¼ѭƫԡ۷ģĽʷֲֲָг֣ȡ p, qֵ--q < qmaxΪʽĶȷֲΪָʽȻĽ϶DzȫģΪp $ \gg$ 0.5ʱ򣬼ӱ ռͳελȻʹȫͼԹpҲijһֵ

ģ͵һȽȫ̽CooperFriezeɵ[34]ǿ˼ӱߺͼӵ飬̽ƫԶģ͵Ӱ졣 ݻ£һʱt$ \alpha$ļʼӱ߷ͼ G$ \left(\vphantom{t-1}\right.$t - 1$ \left.\vphantom{t-1}\right)$ԭ֮䣬1 - $ \alpha$ļʼ¶㡣 ¶㣬ijһֲpiһiʾӴ˶ıȻ$ \beta$ļԭѡһ ˵㣬1 - $ \beta$ļʰƫѡһ˵㡣ԭмӱߣijһֲqiһiʾ¼ӵı Ȼ$ \delta$ļԭоѡһ˵㣬1 - $ \delta$ļʰƫѡһ˵㣬$ \gamma$ļԭ оѡڶ˵㣬1 - $ \gamma$ļʰƫѡڶ˵㡣¶ڸģ͵Ӱ춼۷ֲʽ ʽ½

ȥ붥ʷģ[23]ǷֿΪǻĹϵ൱һ̶ϿȥȥߵΪ һؼԻͻ̶ϸؼʣһݻĻģͣScale Freeģ͵ ĿꡣƫΪһģ֮⣬һȷScale Free--ȼṹ磬Barabási˵ [8]ʵ֤оԣһ̬ͳܹܺõģ--㼯۳̶ȵķֲ p$ \left(\vphantom{c_{v}}\right.$cv$ \left.\vphantom{c_{v}}\right)$

ĽǶƫģͿΪֻInʷֲOutΪ $ \delta$$ \left(\vphantom{d^{out}-m}\right.$dout - m$ \left.\vphantom{d^{out}-m}\right)$ֲ ijƽӹֲݻģ͡Ȼʵ֤о˫ձԣôģ͵оҪԴش ˫ʷֲģͣڵʷֲģ͵Ļϰеĵ߶˫ߣ Ȼ˫ʷֲ˫--˫ռбߵı˵һҪ̬

һʵ˫ ģ͵ķʽǶعInOutߵĻƣڰƫԽInߵķƣҲɽOutߵķơ Tadicģ[33]m0Mߵ翪ʼtʱ̣$ \alpha$ļʼһµĶ㣬Ӵ˶ mߣ1 - $ \alpha$ļʴԭĶڲmߡ¼Ӷıߵյ㰴ƫѡ񣬼

$\displaystyle \pi^{{in}}_{}$$\displaystyle \left(\vphantom{u}\right.$u$\displaystyle \left.\vphantom{u}\right)$ = $\displaystyle {\frac{{A^{in}+k^{in}_u}}{{\sum_{v \in V}\left(A^{in}+k^{in}_v\right)}}}$ (14)
ԭжı߰Outȵƫѡ㣬

$\displaystyle \pi^{{out}}_{}$$\displaystyle \left(\vphantom{u}\right.$u$\displaystyle \left.\vphantom{u}\right)$ = $\displaystyle {\frac{{A^{out}+k^{out}_u}}{{\sum_{v \in V}\left(A^{out}+k^{out}_v\right)}}}$, (15)
Ȼٰ $ \pi^{{in}}_{}$$ \left(\vphantom{u}\right.$u$ \left.\vphantom{u}\right)$ѡյ㡣ȻģͿ϶չ˫ʷֲ

һҲڵʵĻϲ˫--InOutȵĸ߶ԡÿһ $ \left(\vphantom{d^{in}, d^{out}}\right.$din, dout$ \left.\vphantom{d^{in}, d^{out}}\right)$ ֮ԣڸ߶˵ϵԾOutĶҲǻϵࣨInĶ㡣ǣȻҲԵõ˫ ʷֲˡ

ôʵ˫ʽṹǷܹЩأдʵ֤شǹڶԵʵ֤ ģ͵ĶԱһжϾҪֵضܹʵ˫ʽṹγɻƵĻôо߾Ͳò һϷƵģˣ磬In߿ͬʱInȺOutȵķӰ죬OutҲˡ

̸̸ȨĻģ͡ڼȨľ̬붯ѧûеõ㷺оҲͺѶγɻƽ ̽ˡӻģ͵ĽǶȨݻȰӵݻְȨصݻ߿໥Ӱ죬Ҫӵöˡ

next up previous
Next: ݻ Up: ģ Previous: Small World
wwwwjs 2004-01-04