Eötvös Loránd Tudományegyetem Természettudományi Kar
Bóra Eszter
Véletlen gráfok és társadalmi hálózatok BSc Szakdolgozat Matematika BSc, alkalmazott matematikus szakirány
Témavezet®: Backhausz Ágnes
Valószín¶ségelméleti és Statisztika Tanszék
Budapest, 2013
Köszönetnyilvánítás Köszönöm témavezet®mnek, barátaimnak és családomnak a sok segítséget.
2
Tartalomjegyzék 1. Bevezet®
4
2. A közvélemény alakulásának egy modellje
6
2.1.
A közvélemény alakulásának egy modellje
. . . . . . . . . . . . . . . . . .
2.2.
Modellezés irányítatlan, összefügg® multigráfból
2.3.
Két makacs és egy átlagos ember modellje
7
. . . . . . . . . . . . . . .
9
. . . . . . . . . . . . . . . . . .
10
3. Választó modell, mint speciális eset
12
3.1.
Érintkezéses modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2.
Választási modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4. Hálózatok uiditása 4.1.
16
A hálózatok uiditásának de níciója
. . . . . . . . . . . . . . . . . . . . .
5. Véletlen gráfokkal modellezett hálózatok alaptulajdonságai
16
18
5.1.
Hálózatok skálafüggetlensége . . . . . . . . . . . . . . . . . . . . . . . . . .
18
5.2.
Small-world
19
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6. Néhány véletlen gráfmodell
22
6.1.
Erd®s-Rényi véletlen gráf . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
6.2.
Kon gurációs modell
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
6.3.
Barabási-Albert modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
6.4.
Watts és Strogatz small-world modellje . . . . . . . . . . . . . . . . . . . .
25
7. Összefoglalás
26
3
1. fejezet Bevezet® Egy társadalomban hogy terjednek a különböz® vélemények, hiedelmek? A pszichológusok és matematikusok az érem két oldalát vizsgálják. Míg a pszichológusok elmélyednek, abban, hogy milyen tulajdonságú hiedelmek terjednek el jobban, addig a matematikusok komplex rendszereket képzelnek el, amelyben minden egyes ember véleménye függ a többi, vele kapcsolatban álló ember véleményén. A pszichológusok körében többfajta elmélet van arról, hogy bizonyos hiedelmek, vélemények miért terjednek el inkább, mint mások. A tudósok egy része szerint a hiedelmek emocionális, illetve információs tartalmuk alapján terjednek el. ([8]) A pszichológiai kutatások egy másik része azt is igyekszik megmagyarázni, hogy különböz® téves nézetek mi alapján terjednek el? Vegyük például a Mozart-eektus jelenségét. Elterjedt és népszer¶ közhiedelem, hogy a komoly zene hallgatása fejleszti a mentális képességeket. A hiedelem alapja egy felkapott tudományos eredmény, aminek validitása mára már régen megkérd®jelez®dött. A pszichológusok szerint a téves hiedelem sikeres elterjedésének oka a mentális teljesítmény miatti szorongás, a média által felkapott hitelesnek t¶n® történet megragadta az emberek fantáziáját és közhiedelemmé vált. ([2]) Ezzel szemben mit vizsgálnak a matematikusok? A matematikus azt vizsgálja, hogy vajon a társadalom konszenzusra jut-e, vagy pedig megmaradnak az ellentétes vélemények? A legtöbb szakirodalomban található modellben konszenzus alakul ki, ha a társadalom tagjai között elég sok a kapcsolat és rendszeresen változtatják véleményüket, aszerint, hogy ismer®seik milyen véleménnyel rendelkeznek. Vajon megadható-e egy olyan modell, amely jobban jellemzi a valóságot? A következ®kben egy újabb fajta modellt mutatunk be, amely a szakirodalomban ismert választó modell egy nomításának is tekinthet®. A modell különlegessége, hogy a társadalomnak van egy kisszámú szelete, aki sohasem vál-
4
toztatja meg véleményét. Ezekre az emberekre gondolhatunk úgy is, mint véleményformáló emberekre. Vajon ezeknek a véleményformáló (hívhatjuk ®ket makacsnak is) embereknek milyen hatása van a társadalom többi részére, mindenkire egyformán tudnak hatni, vagy klikkesedni fog a rendszer? Ehhez a kérdéshez bevezetjük a uiditás fogalmát. Végül, néhány konkrét példát, véletlen gráfmodelleket vizsgálunk meg, egyrészt alaptulajdonságaikat, másrészt a uiditás szerinti viselkedésüket. A dolgozat tehát két részre bontható. El®ször a közvélemények alakulásának egy modelljét mutatjuk be (2. fejezet). A modell el®zményét a választó modellt és az érintkezéses modellt megvizsgáljuk, mint a közvélemények alakulásának modelljének speciális esetét (3. fejezet), melyhez kapcsolódóan bevezetjük a
uiditás
fogalmát.
A második részben véletlen gráfokról lesz szó. Az 5. fejezetben a valós hálózatok jellemz®iként számon tartott néhány alaptulajdonságot ismertetünk, úgy mint a
skálafüggetlenség
és a
small world
ritkaság, a
tulajdonság. A 6. fejezetben néhány híres véletlen gráf
modellt mutatunk be, megvizsgálva a uiditás szempontjából is.
5
2. fejezet A közvélemény alakulásának egy modellje A következ®kben azt szeretnénk modellezni, hogy egy társadalomban miként alakulnak egy bizonyos kérdésr®l a vélemények, a modellt a [1] cikk alapján mutatom be. A most bemutatandó modellt az motiválta, hogy a szakirodalomban mostanáig leírt modellekben, amelyekben a társadalom tudásátadásának rendszerét vagy kommunikációs folyamatát vizsgálták, rendszerint konszenzus alakult ki. A valóság azonban korán sem ilyen rózsás, a mindennapokban meg gyelhetjük az állandóan fennálló nézeteltéréseket. Hogyan lehetne megragadni az ellentmondó vélemények fennmaradását egy olyan rendszerben, amelyben rendszeresen frissülnek a vélemények. Azaz egy ember véleményére hatnak ismer®sei véleményei. De vajon akármilyen ismer®s véleménye is egyformán hat? Kire hallgatunk jobban barátainkra vagy ellenségeinkre? A szerz®k feltételezik, hogy az emberekre jellemz® a hasonlóság szeretete. Hasonló vélemény¶ emberekkel gyakrabban beszélnek, azok véleményére jobban hallgatnak. Feltesszük tehát, hogy az emberek többségének véleményét befolyásolja az, hogy barátai, ismer®sei mit gondolnak ugyanarról a kérdésr®l. Továbbá feltesszük azt is, hogy vannak olyan emberek is, gondolhatunk rájuk, úgy is mint véleményformálókra, akik ragaszkodnak a saját véleményükhöz.
6
2.1. A közvélemény alakulásának egy modellje A modellhez a következ® jelöléseket, de níciókat vezetjük be. Írjunk le egy
n
f®b®l álló
társadalmat, úgy mint egyszer¶ irányított gráfot, vagyis nincsenek többszörös és hurokélek. Jelöljük
→ − − G = (V, → ε ),
elég nagynak választjuk, és
ahol
V
a gráf csúcsainak halmazát jelöli,
→ − ε ⊆ V × V \ {(v, v) : v ∈ V}
|V| = n-t
általában
az emberek közötti kapcsolatot
jelöli, (pl.: az ismeretséget). Jelölje
t ≥ 0 id®pillanatra Xv (t) ∈ R egy v ∈ V
ember véleményét valamilyen állításról.
2.1.1. de níció. Legyen X(t) az a vektor, amely t id®pillanatra az összes véleményt tartalmazza, azaz X(t) = {Xv (t) : v ∈ V} . Nevezzük X(t)-t a társadalom t id®pontban meg gyelt véleményvektorának. Meg fogunk különböztetni kétfajta viselkedési módot: Az
átlagos
makacs
és
átlagos
viselkedést.
viselkedés¶ emberek rendszeresen átgondolják, megváltoztatják véleményüket,
aszerint, hogy a gráfban a szomszédos csúcsoknak milyen véleményük van.
→ −
2.1.2. de níció. A G gráfban azokat nevezzük átlagosnak, akiknek van ki-csúcsa. Az
átlagosak
halmazát jelöljük
A-val.
A
makacs
viselkedés¶ emberek ragaszkodnak a
véleményükhöz, nem változtatják meg.
→ −
2.1.3. de níció. A G gráfban azokat nevezzük makacsnak, akinek nincsen ki-csúcsa. Ezek halmazát jelöljük
S -sel.
Tehát
A∪S = V
folyamat szerint változnak. Kezdetben, kezdeti
Xv (0)
véleménye. A
makacs
t=0
A vélemények a következ® sztochasztikus
id®pillanatban minden
v ∈ V -nek
van egy
emberek véleménye nem változik, konstans marad az
id® múlásával is.
xs := Xs (t) = Xs (0) Egy adott Minden
(a, v)
s ∈ S, t ≥ 0
átlagos a ∈ A ember véleményének változását a következ®képp modellezzük. ki-élre (v
∈V
) képzeljünk el egy órát, ami id®nként csörög egyet-egyet.
A csörgések id®pontjait modellezze egy Poisson-folyamat azaz a csörgések között eltelt id®k független
ra,v
rav > 0 intenzitás paraméterrel,
paraméter¶ Poisson-eloszlásúak. Ha egy
(a, v)-n ül® óra megcsörren, az azt jelenti, hogy a találkozik v -vel. Az rav jelenti, hogy
szemléletesen azt
a és v milyen gyakran találkoznak. Azok akik nincsenek összekötve éllel, azok
soha nem fognak találkozni, így véleményük nem fog egymásra hatni. Így
a
a következ®
egyenlettel leírható módon változtatja meg a véleményét:
Xa (t) = (1 − θav )Xa (t− ) + θav Xv (t− ). 7
(2.1)
Ahol
Xa (t− ) = limu→t+ Xv (u), θav ∈ (0, 1]
paraméter azt fejezi ki, hogy találkoznak, akkor valószín¶bb, hogy
v a
a v
bizalmi
mennyire bízik
mennyire gy®zi meg
elfogadja
a
a-t.
v
paraméter
a
és
v
között. A
bizalmi
véleményének helyességében. Tehát, ha
Ha
θ
nagy, azaz közel van
1-hez,
akkor
véleményét.
2.1.4. megjegyzés. A szokásos hálózat modellezésekhez képest ez a modell azért több, mert a pontok közötti kapcsolatot további paraméterekkel lehet nomítani. Ahogy a 2.2 részben látni fogjuk, a szokásos modellezéseket is beleágyazhatjuk az itt tárgyalt modellbe. Tekinthetjük
→ − G -t
úgy is mint teljes irányított egyszer¶ gráfot, az olyan élekhez pe-
rvv0 = 0-t
dig, amelyek az eredeti gráfban nem voltak benne,
és
θvv0 = 0-t
rendelünk
− (v, v 0 ) ∈ /→ ε ). Jelöljük egy v ∈ V személy összesített intenzitás paraméterét P rv -vel, ahol rv := rvv0 Továbbá, jelöljük r-rel minden ember összes intenzitásparamév 0 ∈V P terének összegét, azaz r := v∈V rv . Számláljuk N (t)-vel a t ≥ 0 id®pillanatig megtörtént (v, v
0
∈ V,
és
találkozások számát a különböz® emberek között, ami pont egy Poisson-folyamat szerinti beérkezések száma. Legyen
T(k)
a
k.
r
intenzitásparaméter¶
találkozás id®pontja, azaz
T(k) := inf{t ≥: N (t) ≥ k}. Minden
a ∈ A átlagos
emberek halmazát, akik
a
emberekhez de niáljuk a
Sa ⊆ S
halmazt, mint azon
makacs
ismeretségein keresztül elérhet®k.
2.1.5. de níció. Sa legyen azon s ∈ S makacs emberek halmaza, akik irányított úton → − elérhet®ek a-ból a G gráfban. Tehát Sa -t nevezzük az a-ra ható makacs emberek halmazának. Az
Sa
azon
makacs
niálhatjuk minden
emberek halmaza, akik befolyásolják
s ∈ S makacs
közvetlen, vagy közvetett módon
emberhez az
átlagos
a
véleményét. Hasonlóan, de-
emberek egy halmazát, akiket
befolyásol s.
2.1.6. de níció. Legyen As := {s, s ∈ Sa } ⊆ A, s ∈ S az s-t®l tanuló átlagos emberek halmaza. Az eddigi jelölések, de níciók felhasználásával fogjuk modellezni a vélemények alakulását egy társadalmi hálózatban.
2.1.7. de níció. Nevezzük a következ® hármast társadalmi hálózatnak: → − N = ( G , {θe }, {re }), 8
− e∈→ ε
Ahhoz, hogy elkezdhessünk vizsgálódni egy adott társadalmi hálózattal, még meg kell adni a kiinduló
X(0)
vélemény vektort is.
→ −
2.1.8. de níció. Egy N = ( G , {θe }, {re }) társadalmi hálózatot, a kiinduló X(0) vektorral együtt társadalomnak hívunk, és L(X(0))-val jelöljük. Egy
→ − N = ( G , {θe }, {re })
társadalmi hálózathoz de niáljuk a következ®
Q ∈ RV×V
mátrixot.
X
Qvv = −
Qvv0 := θvv0 rvv0
Qvv0 ,
v 6= v 0 ∈ V
v 0 6=v Feltételezzük, hogy minden
a ∈ A átlagos
emberre hat legalább egy
s ∈ S
makacs
vélemény.
2.1.9. feltételezés. Minden a ∈ A-re, Sa 6= ∅. A (2.1.9) feltételezést nélkülöz® esetet könnyen visszavezethetjük a feltételezést fenntartó esetre. Hiszen legyen milyen
s ∈ S makacs
többi részébe
V \R
R átlagos
vélemény. Az
nem fog
R-b®l
emberek egy olyan halmaza, akikre nem hat sem-
R
egy olyan részgráfja lesz a
futni él. Így majd elég lesz csak
→ − G -nek,
R
és
hogy a gráf
V \R
diszjunkt
részgráfokra alkalmazni az eredményeket.
2.2. Modellezés irányítatlan, összefügg® multigráfból A következ®kben bemutatjuk, hogyan lehet a fenti modellbe ágyazni, ha a társadalom tagjaira és a köztük lév® kapcsolatokra adott egy irányítatlan összefügg® multigráf. Azaz a kapcsolatok leírja egy irányítatlan, összefügg® multigráf, hogy ki kit mennyire jól ismer. Ha két csúcs többszörösen is össze van kötve, akkor feltételezzük, hogy ®k jobban ismerik egymást, mint azok, akik csak egyszeresen, vagy kevesebb éllel vannak összekötve.
G = (V, ε) összefügg® irányítatlan multigráf. Ebb®l szeretnék elkészíteni → − N = ( G , {θe }, {re }) társadalmi hálózatot. Az éleket úgy irányítjuk, hogy két átlagos
Legyen adott egy
ember között oda-vissza legyen egy-egy irányított él, multiplicitás nélkül. Egy és egy
átlagos
között csak egyirányú él legyen, az
Ha az eredeti gráfban volt két
makacs
átlagostól
a
makacs
makacs
felé irányítva.
között él, akkor az irányítottban sincs. Legyen
→ − − − − G = (V, → ε ), ahol → ε legyen a következ®képp de niálva: (a, v) ∈ → ε , akkor és csak akkor, ha a ∈ A, v ∈ V \ {a}, (a, v) ∈ ε). A következ®képp fogjuk de niálni a bizalmi 9
paramétereket
és az
intenzitásparamétereket.
Tekintsük most a
bizalmi
paramétert konstansnak, mivel
az eredetileg megadott gráfban nincsen megadva err®l információ. Azaz minden
− (a, v) ∈ → ε -re.
Az
intenzitásparaméterhez
θa,v = θ ∈ (0; 1],
azt az információt is felhasználjuk,
hogy az eredeti, irányítatlan gráfban mekkora multiplicitással szerepelt egy él. Jelöljük az eredeti, irányítatlan gráfban egy kétszer számolunk bele. Egy szeretnénk de niálni az
v ∈ G
(v, v 0 ) ∈ ε
κv,v0 -vel, P dv = v0 ∈G κvv0
él multiplicitását
csúcs fokszámára így
egy hurokélt adódik. Úgy
intenzitásparamétert, hogy a nagyobb multiplicitással szerepl®
élek a generált gráfban arányosan többször aktiválódjanak.
ra,v =
1 κa,v 1V\{a} (v) da
a ∈ A, v ∈ V.
2.2.1. megjegyzés. Az 1H (h)-n egy olyan függvényt értünk, ami egyenl® 1-gyel, ha h ∈ H, egyébként értéke 0 lesz. → − N = ( G , {θe }, {re })
A fentiekben de niált
Q
hármashoz a következ®képp de niáljuk a
mátrixot:
Qav0 :=
θκav0 da
Qaa = −
X
Qav0 ,
A 3 a 6= v 0 ∈ V.
v 0 6=v
2.2.2. megjegyzés. Egyszer¶, irányítatlan gráf esetén, mivel nem tartalmaz sem hurokélt, sem többszörös élt, ezért κav0 = 1, ha a ∈ A, v0 ∈ G és 0 egyébként. Azaz κav0 = 1ε ({a, v 0 })
2.2.3. megjegyzés. Azzal, hogy feltettük, hogy a gráf összefügg®, az abból képzett irányított gráfra teljesülni fog a (2.1.9) feltételezés.
2.3. Két makacs és egy átlagos ember modellje A közvélemény alakulásának modelljének nézzük meg egy egyszer¶ esetét. A társadalomban legyen két Továbbá legyen
makacs
ember,
{a} = A
S = {s1 , s2 }
az egyetlen
átlagos
különböz® véleményekkel,
xs0 = 0, xs1 = 1.
viselkedés¶ ember. Lásd 2.1 ábra.
Tegyük föl, hogy mindkét véleménnyel ugyanolyan gyakran találkozik, és ugyanannyira plauzibilisnek tartja, azaz kezdeti
ras0 = ras1 =
1 , ill. 2
θas0 = θas1 =
1 . Legyen az 2
átlagos
ember
(t = 0) véleménye Xa (0) = 0. Írjuk fel az (2.1) egyenlet alapján, hogy emberünknek
az els® találkozás után mi lesz a véleménye.
1 − − Xa (T(1) ) = (1 − θ)Xa (T(1) ) + θXB(1) (T(1) ) = B(1), 2 10
2.1. ábra. Két makacs és egy átlagos ember modellje
ahol
{B(k) : k ∈ N}
Bk 1/2
eséllyel 1,
Bernoulli((1/2)) eloszlású valószín¶ségi változók egy sorozata, azaz
1/2
eséllyel 0 a valószín¶ségi változó értéke. A
B(k)
gondolhatunk úgy is, mint arra a sorozatra, amilyen sorrendben egyik, hol a másik véleményformálóval. Általános
a
t≥0
a
véletlen sorozatra találkozott hol az
esetén a következ® képlet adódik,
véleményére:
Xa (t) =
1 N (k)−k+1 ( B(k) 2
X
1≤k≤N (t) Mivel a
B(k)
sorozatban tetsz®leges hosszú csupa egyes, illetve csupa nulla sorozatok is
el®fordulhatnak:
lim inf Xa (t) = 0,
lim sup Xa (t) = 1.
t→∞
Tehát az
t→∞
Xa (t) nem fog konvergálni, tehát a végtelen sokszor megváltoztatja a véleményét.
Az elemzéseket úgy is általánosíthatjuk, hogy a közös
θ-val
helyettesítjük. Azaz,
bizalmi
θas0 = θas1 = θ ∈ (0, 1).
paramétert
1 helyett valami 2
Ekkor az eddigi egyenletek az
alábbiak szerint módosulnak. Az els® találkozás után a következ® lesz
a
véleménye:
− − Xa (T(1) ) = (1 − θ)Xa (T(1) ) + θXB(1) (T(1) ) = θB(1), A második találkozás után:
− − Xa (T(2) ) = (1 − θ)Xa (T(1) ) + θav Xv (T(1) ) = (1 − θ)θB(1) + θB(2) = (1 − θ)θB(1), Általánosan, indukcióval következik,
t≥0
Xa (t) = θ
X
id®pillanatban,
a
véleménye.
(1 − θ)N (t)−k B(k)
1≤k≤N (t)
11
3. fejezet Választó modell, mint speciális eset A következ®kben a választó modellr®l lesz szó. A választó modell (vagy, ahogy az idegennyelv¶ szakirodalomban említik,
voter modell) népszer¶ modell f®leg a részecske ziká-
ban és a matematikai zikában. Miért is fontos a választó modell tárgyalása itt? Egyrészt azért fontos, mert évtizedes modellje, el®zményével az érintkezéses modellel együtt, bizonyos társadalmi jelenségeknek, mint például a betegségek, pletykák terjedésének, vagy két faj versengésének ugyanazért a területért. Másrészt, a választó modell tekinthet® úgy, mint a fent leírt modell el®zménye, így segítséget nyújt a fogalmak, koncepciók megértésében. A következ®kben látni fogjuk, hogy a választó modellre tekinthetünk úgy is, mint a közvélemények alakulásának egy speciális esetére. Maga a választó modell egy sztochasztikus folyamat, amely részecskék láncszer¶ interakcióinak rendszerét írja le.
3.1. Érintkezéses modell Maga a választó modell egy sztochasztikus folyamat, amely részecskék láncszer¶ kölcsön-
érintkezéses modell (vagy ahogy az idegennyelv¶ szakirodalomban hívják contact process). Legyen G egy véges gráf, amelynek hatásainak rendszerét írja le. Nagyon hasonló az
minden egyes
v∈V
csúcsára 1-es, vagy 0-ast írunk, azaz
tálhatjuk úgy is, hogy egy adott
H := {v : v(t) = 0},
t≥0
{0, 1}V .
Az eddigieket interpre-
v∈V
terület vagy egészséges:
id®pillanatban egy
vagy pedig fert®zött:
I := {v : v(t) = 1}.
A fert®zött terület
bizonyos, rögzített id® elteltével felépül. Ezzel szemben, egészséges területek megbetegedhetnek, attól függ®en, hogy hány fert®zött szomszédjuk van. Természetesen a modellnek létezik egy úgynevezett többtípusú érintkezéses változata is, ahol a gráf csúcsaira nem csak az
1
ill.
0
számokat írhatunk, hanem
12
0, 1, 2 . . . , k
vala-
melyikét, azaz
{0, 1, 2, . . . k}V
eseménytérr®l van szó. Ebben az esetben szemléletesen úgy
képzelhetjük el a modellt, mint ha
{1, 2, . . . k}
típusú fert®zések versengenének egyszerre
ugyanazért a területért. Magát az egy fert®zéstípusos esetet a következ®képpen írhatjuk le. Ha van egy fert®zött csúcs,
v ∈ H, akkor feltételezhetjük, hogy az egy rv∈H = 1 intenzitás paraméter¶ Poisson-
folyamattal leírhatóan fog felépülni. Azaz egy fert®zött csúcs gyógyulásához szükséges id®
1
paraméter¶ exponenciális eloszlású. Ha van egy egészséges csúcs.
v ∈ I,
akkor
t ≥ 0 id®pillanatban, szintén Poisson-folyamattal leírhatóan megfert®z®dhet az intenzitási paramétere, ebben az esetben a következ® lesz (λ el®re rögzített) :
X
rv(t)∈I = λ
v 0 (t)
v 0 :vv 0 ∈ε A
λ
P
v 0 :vv 0 ∈ε
v 0 (t) összeg pont a beteg szomszédok száma. Ennyi élen jöhet be a fert®zés
paraméter¶ exponenciális eloszlással, hiszen a betegek
szerint fert®znek. Akkor fert®z®dik meg egy adott
v∈V
λ
paraméter¶ Poisson-folyamat
csúcs, amikor a beteg szomszédai
közül az els®nél cseng az óra. Azaz független (ebben az esetben, ráadásul azonos paraméter¶) exponenciális eloszlású valószín¶ségi változók minimuma szintén exponenciális lesz, és a paramétere a paraméterek összege lesz. Könnyen látszik, hogy minden
G
gráfhoz létezik a következ®
λc
kritikus érték. Ha
λc ≥ λ esetben a fert®zés nem hal el pozitív valószín¶séggel. Azaz, ha λc ≥ λ, akkor akkor minden
t ≥ 0 id®pillanatban lesz legalább egy olyan v ∈ V csúcs, melyre v(t) = 1, ha volt
a kezdeti id®pillanatban
λc ≥ λ,
t=0
fert®zött csúcs, azaz
v 0 (0) = 1, v 0 ∈ V .
Ezzel szemben, ha
a fert®zés elt¶nik. Érdekes, és nehéz kérdés, hogy mi történik a
λc = λ
esetben,
a választ a kérdésre csak 1990-ben adott Bezuidenhout és Grimmett, ebben az esetben is elt¶nik a fert®zés.
3.2. Választási modell Ahogy az eddigiekben is, a választó modellben is részecskék interakcióját modellezzük. Képzeljünk egy
G
tetsz®leges, összefügg® gráfot. A csúcsokat képzelhetjük, mint választó-
kat, akiket befolyásol az, hogy barátaik, ismer®seik milyen választói véleménnyel vannak. Ezeket a kapcsolatokat a gráf csúcsai között futó élekkel fejezzük ki. Az alapmodellben minden választónak két párt közül az egyik a véleménye, azaz minden natban
Xv (t) = 0,
vagy
1 (v ∈ V ).
t ≥ 0
id®pilla-
A választók a következ®képp változtatják választói
13
preferenciájukat. Egy valamilyen id®pillanatokban
a
találkozik
r
intenzitás paraméter¶ Poisson-folyamat szerint érkez®
v -vel.
szomszéddal egy adott nagyságú
pav
A
v
választó
a
szomszédjai közül kerül ki, minden
valószín¶séggel találkozhat
d
G=Z
A modell legintenzívebben vizsgált változata, amikor
a,
ahol
P
(a,v)∈ε
pav ≤ 1
, azaz a végtelen négyzet-
rács. Csak az utóbbi id®ben kezdtek el foglalkozni olyan változatokkal is, amelyben teljes gráfokat vizsgálnak úgy, hogy van ügynököket
fanatikusoknak
makacs
ügynökök is. A választási modellben a makacs
(idegennyelv¶ szakirodalomban
zealots ) nevezik, lásd ).
A következ®kben az alapmodellnél összetettebb modellt vizsgálunk. Egyrészt, nem szorítjuk meg a választók véleményét
v ∈ V
Xv (t) ∈ R.
véleménye,
{0, 1}-re,
hanem adott
t ≥ 0
id®pillanatban egy
A választói vélemény nem az el®bb leírt valószín¶ségek
szerint fog frissülni, hanem a 2.1 részben leírtak szerint, azaz minden élen ketyeg egy intenzitás paraméter¶ Poission óra ((a, v)
rav
∈ ε).
Az el®z® fejezetben (2.2) láttuk, hogy egy irányítatlan összefügg® gráfot, hogyan lehet a vélemények alakulásának modelljével modellezni. Legyen
→ − G
egy tetsz®leges irányított,
összefügg® gráf. Azzal a fontos különbséggel, hogy egy találkozásnál, azaz egy él aktiválódásánál
bizalmi
a
választó átveszi
v
− (a, v) ∈ → ε
választási preferenciáját. Vegyük észre, hogy ezt a
paraméterekkel kifejezve azt jelenti, hogy minden
(a, v) ∈ ε
élre,
θa,v = 1.
Fontos észrevétel, hogy egy adott ember aktuális véleményének forrását folyamatosan vissza tudjuk következtetni. Tehát legyen adva ménye azért
Xa (t).
Xa (t)
Az
Xa (t)
a
t
legutóbbi,
v1 t − U1
id®pillanatban
a
a
véle-
csúcsnak
el®tti találkozásnál egy
id®pontbeli véleménye. Ugyanígy
beli véleménye is visszakövetkeztethet® egy
− U2 ∈ [t − U1 ]).
t≥0
v1 ∈ V
Xv1 (t − U1 ) = Xa (t) véleménnyel, ahol t − U1 ∈ [0, t]. Tehát az Xa (t)
érték¶ vélemény eredete
(t
csúcs,
érték¶ véleményt vissza tudjuk követni az id®ben. Az
érték¶ a véleménye, mivel az
emberrel találkozott
a∈V
v2
Tehát van egy lánc, egészen
ember
t=0
t − U2
v1 t − U1
id®pont-
id®pontbeli véleményéhez
id®pontig :
Xa (t) = Xv1 (t − U1 ) = Xv2 (t − U2 ) = · · · = Xvn (0) Tehát értelmezhetünk egy Markov-láncot (Markov-láncokról az ismereteket a [10] forrásból használtam fel), maza, azaz
V.
U1
amelynek állapothalmaza legyen a gráf csúcsainak hal-
A kiinduló állapota legyen
haladnánk, legyen csúcsra
Va (u)-t,
Va
értéke
id® múlva, azaz
a,
Va (0) = a.
és az is marad a
Majd, mintha id®ben visszafelé
[0, U1 )
intervallumon, majd átlép a
v1
Va (U1 ) = v1 .
A Markov-lánc átmeneti mátrixa, éppen a gráf élein ül® Poisson-folyamatok intenzitás paraméterei lesznek. Ez pont a 2.1 részben de niált
14
Q
mátrix lesz. Ne feledjük el, hogy
a Markov-lánc elnyel® állapotai a
makacs
csúcsokban lesznek (s
∈ S),
hiszen
s
csúcsból
nem indul kifelé él, hiszen, a makacs vélemények sohasem frissülnek. A Markov-lánc tehát valamilyen
s∈S
elérése esetén fog megállni. Tehát, ha az összes csúcs vélemény-változását
szeretnénk meg gyelni, akkor azt modellezhetjük úgy is mint
{Va (t) : a ∈ A}.
A láncok kiindulása, tehát
Va (0) = a, a ∈ A.
n − |S|
db Markov-láncot:
Mindegyik Markov-láncnak
Q lesz az átmeneti mátrixa. A Markov-láncok szimultán, függetlenül futnak a V
csúcsokon
egészen addig, amíg vagy össze nem találkoznak, ekkor együtt mozognak tovább, vagy pedig el nem érnek egy láncoknak folyamata, hívják:
coalescing
S
s∈S
egyesül®
csúcsot, és megállnak. Ez a folyamat az
Markov-
elnyel® halmazzal (vagy ahogy az idegennyelv¶ szakirodalomban
Markov-láncok).
Tehát az olyan választási modell, amelyben vannak
makacs csúcsok (vagy fanatikusok),
leírható úgy, mint egyesül® Markov-láncok, amelynek elnyel® halmaza pont a
makacs
csúcsok halmaza:
L({Xa (t) : a ∈ A}) = L({XVa (t) (0) : a ∈ A}) Ha a 2.1.9 feltételezés igaz egy gráfra, azaz minden
s∈S
makacs vélemény, akkor a
Va (u)
Markov-láncok
halmazban, valamilyen véges, véletlenszer¶ vektor, ahogy
u
n®, úgy tart eloszlásban egy
TSa
1
a ∈ A
emberre hat valamilyen
valószín¶séggel megállnak az
id® elteltével. Azaz a
{Va (TSa )} ∈ S A
S
{Va (u) : a ∈ A}
vektorhoz.
Mivel a választási modellt megfeleltettük az egyesül® Markov-láncoknak, ebb®l következik, hogy
Xt eloszlásban konvergál egy X
vektorhoz, ahol
15
Xs = xs , s ∈ S , és XVa (TSa ),a∈A .
4. fejezet Hálózatok uiditása A
uiditás
a hálózatok olyan tulajdonsága, ami a hálózat geometriai tulajdonságától és
a makacs vélemények nagyságától függ. Bizonyított ([1], 4. Tétel), hogy magas uiditású hálózatok estén a makacs vélemények hatása homogén, azaz a stacionárius eloszlásban az átlagos emberek véleménye a saját várható értékéhez van közel, így egyben az átlagos emberek véleménye egymáséhoz is hasonló lesz. Másképpen fogalmazva a különböz®
makacs
vélemények minden átlagos emberhez azonos módon eljutnak. A uiditást a [1] cikk
6-ossal
számozott része alapján vezetem be.
4.1. A hálózatok uiditásának de níciója Emlékeztet®ül idézzük fel, hogy egy de niáltuk a következ®
Q ∈ RV×V
Qvv0 := θvv0 rvv0
→ − N = ( G , {θe }, {re })
társadalmi hálózathoz hogyan
mátrixot: (lásd 2.1 szakasz)
Qvv = −
X
Qvv0 ,
v 6= v 0 ∈ V
v 0 6=v
P ∈ RV×V
legyen a következ® irreducibilis, nem periodikus sztochasztikus mátrixok
(azaz minden eleme nemnegatív, és egy sorban az elemek összege 1) halmaza. Minden
P ∈ P -re: Pav = αa Qav , valamilyen Legyen
αa ≥ 0-val. Azaz P W (k)
∀a ∈ A, v ∈ V, a 6= v,
mátrix sorai
Markov-lánc olyan, hogy
(4.1)
Q mátrix sorainak lineáris kombinációja lesz.
v∈V
rixszal.
16
legyenek az állapotai,
P
átmeneti mát-
Mivel
P ∈P
irreducibilis és nem periodikus, ezért létezik pontosan egy stacionárius
eloszlás. Jelöljük a következ®képp a
k
lépéses átmenetvalószín¶ségeket
pvw (k) := Pv (W (k) = w),
pv (k) := {pvw (k) : w ∈ V},
(4.2)
→ −
4.1.1. de níció. Legyen N = ( G , {θe }, {re }) társadalmi hálózat, amelyre teljesül a 2.1.9 feltételezés. Ekkor P ∈ P -re: π = P 0 π legyen a stacionárius eloszlás. Legyen π(S) :=
X
πs ,
π∗ := min πv .
Jelöljük
τ -val
(4.3)
v∈V
s∈S
a következ®képpen de niált keverési id®t:
τ := inf{k ≥ 0 : max kpv (k) − πkT V ≤ v∈V
1 }. 2e
(4.4)
A keverési id® lényegében azt fejezi ki, hogy milyen gyorsan, hány lépés után közelíti meg a folyamat a stacionárius eloszlást.
→ −
4.1.2. de níció. Legyen N = ( G , {θe }, {re }) társadalmi hálózat, amelyre teljesül a 2.1.9 feltételezés. Minden P ∈ P -re: ψ(P ) :=
nπ∗ . e2 τ π(S) ln( τ π(S) )
Ekkor a hálózat uiditása: Ψ := sup{ψ(P ) : P ∈ P.} Gondoljunk bele hogy mi történik a fenti képlettel, ha
(4.5)
τ -t változtatjuk. Ha τ
növekszik,
akkor a uiditás csökken. Ez egyezik az intuitív képünkkel, hiszen ha a keverési id® nagy, az szemléletesen azt jelenti, hogy a folyamat nehezen jut el a stacionárius állapotba, azaz a különböz® vélemények nehezen jutnak el az egyes emberekhez. Hasonlóan, mi történik ha csökken. Hiszen ha
P
s∈S
πs
π(S)-t
változtatjuk? Ha
π(S)
n®, akkor a uiditás szintén
nagy, akkor ez szemléletesen azt jelenti, hogy a különböz®
makacs vélemények nem igazán hagyják el a makacsok halmazát. Most vizsgáljuk meg
π∗ -t! Ha sokkal kisebb, mint a többi πv , v ∈ V
az azt jelenti, hogy
abban a csúcsban jóval ritkábban frissül a vélemény, kevésbé jutnak el hozzá a különböz® vélemények. Azaz alacsonyabb
π∗
esetén alacsonyabb uiditás várható.
17
5. fejezet Véletlen gráfokkal modellezett hálózatok alaptulajdonságai A valóságban létez® hálózatoknak van néhány tipikus tulajdonsága. A hálózat csúcsainak fokszáma meglep®en alacsony a maximális gráf
n−1 csúcshoz képest. Másképpen fogalmazva a
ritka . Sok valódi hálózatnál meg gyelhet® az úgy nevezett small world tulajdonság,
skálafüggetlensége, er®sen klaszterezett. Mivel a legtöbb hálózat az id®függvényében n®, ezért legyen z®kben
{Gn }∞ n=1
{Gn }∞ n=1
gráfok egy sorozata, ahol
n∈N
a
Gn
csúcsszámát jelöli. A követke-
gráfok sorozatára de niálom a fenti fogalmakat, a [12] forrás alapján.
5.1. Hálózatok skálafüggetlensége Legyen
{Gn }∞ n=1
gráfok egy sorozata. Jelöljük
arányát, azaz:
dni
az
-nel a
Gn
gráfban a
k
fokszámú csúcsok
1 n (n) |{d : di = k, i ∈ {1, 2, . . . , n}}|, n i i ∈ {1, 2, . . . , n} csúcs fokszámát jelöli. Tehát minden n ∈ N-re (n)
Pk
ahol legyen
(n)
Pk
=
(n) ∞ a következ® fokszám sorozatot: {Pk }k=0 .
5.1.1. de níció. Egy {Gn }∞ n=1 véletlen gráfmodell ritka, ha (n)
lim Pk
n→∞
ahol {pk }∞ k=0 valószín¶ségi eloszlás.
18
= pk ,
kapjuk
∞ 5.1.2. de níció. Legyen {Gn }∞ n=1 egy véletlen gráfmodell. {Gn }n=1 skálafüggetlen a τ kitev®vel, ha ritka és
ln pk =τ k→∞ ln( 1 ) k lim
Használnak még egy alternatív de níciót skálafüggetlenségre, ha
k → pk
nem elég
sima.
∞ 5.1.3. de níció. Legyen {Gn }∞ n=1 egy véletlen gráfmodell. {Gn }n=1 skálafüggetlen a τ kitev®vel, ha ritka és
[ln 1 − F (k)] = τ, k→∞ ln( k1 ) lim
ahol F (x) =
P
y≤x
py .
5.2. Small-world Ma már a köztudatban is meggyökeresedett az a gondolat, hogy világunk úgy mond milyen kicsi, egy small-world. Népszer¶en megfogalmazva, a világon bármely két ember között átlagosan hat hosszú ismeretségi lánc van. Honnan is ered ez az állítás? A híres szociálpszichológus Milgram, aki nagy port kavaró engedelmességi kísérletér®l híres, megjelentette cikkét a small-world kísérletr®l megvizsgálva az addigi elméleti spekulációt egy igazi szociális hálózaton. Cikkét, 1969-ben a
Sociometry
cím¶ tudományos
folyóiratban jelentette meg (lásd [13]). A kísérletben kiválasztottak 300, Nebraskában, illetve Bosztonban él® embert. A feladatuk az volt, hogy juttassanak el egy csomagot ismer®sök ismer®sein keresztül, Amerika másik felébe, Massachusettsbe egy célszemélynek. Milgramék nagy lemorzsolódást tapasztaltak, sok csomag nem jutott célba. Azoknál a csomagoknál viszont, amelyek célba értek, átlagosan 5 hosszúságú volt az ismer®sökb®l álló lánc, ami meglep®en alacsony. Milgramék még egy fontos meg gyelést tettek. A láncok többsége átment három bizonyos ember valamelyikén. Milgramék azt felelték, hogy a szociális hálózatban (azaz az emberek és kapcsolataikból létrejöv® hálózatban) vannak, úgy nevezett kiemelt jelent®ség¶ emberek, akiknek információs közvetít® szerepe jelent®s. 2002-ben a Columbia Egyetem kutatócsoportja megismételte Milgram kísérletét (lásd [5]), modernizáltabb változatban. Egyrészt, az egész világra kiterjedt a vizsgálatuk, habár
19
a vizsgálatban résztvev®k többsége így is amerikai középosztálybeli maradt. A 18 célszemély között a legkülönfélébb foglalkozású és lakhely¶ emberek voltak (összesen 13 országból), mint például egy ausztrál rend®r vagy egy norvég állatorvos. Másrészt, a résztvev®k nem postai csomagot küldözgettek egymásnak, hanem e-mailt kellett tovább közvetíteni. A kutatók Milgramékhoz hasonlóan nagy lemorzsolódást tapasztaltak. Az összegy¶lt adatokból azt számították ki, hogy feltételezhet®, hogy a világon két ember között átlagosan 5-7 hosszú egy ismeretségi lánc, alacsony változékonysággal, a célszemélyek lakóhelyét®l függ®en. Milgramékkal szemben, a kutatók szerint a szociális hálóban nincsenek kiemelt jelent®ség¶ csomópontok, azaz, minden ember nagyjából ugyanakkora eséllyel fog szerepelni egy láncban. További érdekes meg gyeléseket is tettek, például meg gyelhet® volt, hogy a sikeres, befejezett láncok többségénél az emberek nem rokonsági, baráti kapcsolatait mozgósította, hanem úgy nevezett professzionális kapcsolatait használta, azaz munkahelyi vagy volt iskolatársi kapcsolatait. Másik érdekes meg gyelés az volt, hogy a n®k szívesebben küldték tovább n®knek az e-mailt, a fér ak pedig szívesebben küldték tovább a fér aknak. Nem csak az ismeretségi hálónak vannak small-world tulajdonságai. Small-world tulajdonságot találhatunk számos való életbeli rendszerben: úthálózatoknál, táplálkozási láncokban, szavazói hálózatokban, agyi neuron hálózatban, telefonhívások hálójában, szociális ráhatások rendszerében stb.. Érdemes megjegyezni, hogy olyan hálózatok, amelyek egy éle akkor van behúzva, ha a két elem id®beli vagy térbeli közelségben van, tipikusan nem rendelkeznek a fenti tulajdonsággal. Például tekinthetjük azt a hálózatot, amelyben legyenek egy középiskola mindenkori diákjai a csúcsok, és két csúcs legyen összekötve ha volt olyan év, hogy mindketten ebbe az iskolába jártak. Ha két volt-diákot tekintünk, akik egymáshoz képest 20 évvel jártak az intézményben, akkor valószín¶tlen, hogy lesz olyan diák, akivel mindketten egyszerre jártak. Másik tipikus példa, tekintsük a mindenkori nagy gondolkodók halmazát, két gondolkodó össze van kötve, ha alkottak ugyanazon a tudományterületen. Valószín¶tlen, hogy Nagy Sándornak és Albert Einsteinnek lenne rövid összeköttetése. Egy hálózatot modellez® véletlen gráf
tipikus
ha igaz rá a következ®. Legyen
Dn
kiválasztott két csúcs között (
v1 , v2 ∈ Gn
a
{Gn }∞ n=1
folyamat, small-world tulajdonságú,
távolság a gráfon egyenletes valószín¶séggel
), feltéve, ha van út a két csúcs között A két
csúcs összekötöttsége azért szükséges feltétel, mert vannak olyan véletlen gráfmodellek is, amelyben a gráf nem feltétlenül összefügg®. De niáljuk két csúcs távolságát úgy, mint az ®ket összeköt® minimális út hosszát a
Gn
gráfban.
20
5.2.1. de níció. Egy véletlen gráfmodell {Gn }∞ n=1 small-world tulajdonságú, ha létezik K konstans, hogy lim P (Dn ≤ K ln n) = 1
n→∞
Hálózatokat különböz® véletlen gráfokkal lehet modellezni. Néhány híres small-world tulajdonságú modell az Erd®s-Rényi véletlen gráfmodell, a Watts és Strogatz small-world modell, Barabási-Albert modell. Kapcsolódó fogalom a gráf
átmér®je.
5.2.2. de níció. Jelöljük diam(Gn )-nel a Gn gráf átmér®jét, azaz a gráfban található maximális távolságot. Gondolhatnánk, hogy a
small world
tulajdonságnál írhattuk volna
Dn
távolság helyett
diam(Gn ) átmér®t is. De gyeljük meg, hogy az diam(Gn ) mér®szám sokkal érzékenyebb a gráf kisebb változásaira. Vegyünk egy nagyméret¶
k
G gráfot, amelyhez adjunk hozzá egy
hosszú utat, amelyek ne legyenek összekötve a gráf többi részével,
mint
n.
Rögtön látszik, hogy diam(Gn )≥
k,
míg
robusztusabb mér®szám.
21
dn
k
legyen jóval kisebb,
legfeljebb kicsit változik, azaz
dn
egy
6. fejezet Néhány véletlen gráfmodell A következ®kben ismertetjük a legfontosabb véletlen gráfmodelleket legfontosabb tulajdonságaikkal együtt. A [1] alapján ismertetjük, hogy uiditás szempontjából mit mondhatunk róluk.
6.1. Erd®s-Rényi véletlen gráf Az Erd®s-Rényi véletlen gráf az egyik legrégebbi véletlen gráfmodell. A véletlen gráfok témakörének elindítója. A véletlen gráfmodelleket eleinte csak gráfok bizonyos tulajdonságinak belátásához használták. Szemléletesen a következ® valószín¶ségi módszerr®l van szó. Ha egy véletlen gráfnál be tudom látni valamilyen pozitív valószín¶ség mellett egy tulajdonság meglétét, akkor biztosan léteznie kell a gráfnak ilyen tulajdonsággal is. Kés®bb, a véletlen gráfokat elkezdték alkalmazni bonyolult hálózatok ábrázolásához. Nem meglep®, hogy az internet virágzásának korában népszer¶ a téma. Az Erd®s-Rényi modell egyik legegyszer¶bb véletlen gráfmodell, amelynek két szorosan egymáshoz kapcsolódó változata van. A modellt 1959-ben, egymástól függetlenül két helyen is publikálták, az egyiket Edgar Gilbert, míg a másikat Erd®s Pál és Rényi Alfréd írta, érdekesség, hogy mindkét cikk a véletlen gráfok összefügg®ségével foglalkozott. (lásd [6] és [7]) Az
ER(n, M )
egy olyan véletlenszer¶, irányítatlan, egyszer¶ gráf lesz, amelyet egyen-
letes eloszlás szerint választunk ki az A
ER(n, p)
esetén
n
n
csúcsú
M
él¶ egyszer¶, irányítatlan gráfok közül.
csúcsú gráfban húzunk be éleket, egy-egy élt
Nyilvánvalóan, minél nagyobb a
p,
annál több élt tartalmaz a gráf.
22
p
valószín¶séggel.
6.1.1. megjegyzés. Érdemes megjegyezni, hogy p helyett sokszor nλ -t is használnak második paraméterként. Ismeretes, hogy a
ER(n, nλ )
gráfban
k
fokszámú csúcsok aránya közel van a következ®
valószín¶séghez:
P(Bin(n − 1, λ/n) = k) Továbbá az is ismeretes, hogy nagy tart egy
λ
n-re,
a
n
P =
és
λ paraméter¶ binomiális eloszlás n
eloszlású Poisson-eloszláshoz:
P(Bin(n − 1, λ/n) = k) = e−λ Tehát látszik, hogy az
ER(n, nλ )
λk + o(1), k!
Erd®s-Rényi gráf
ritka
k ∈ N.
(vö. 5.1.1), de nem
skálafüggetlen
(vö. 5.1.3). Erd®s és Rényi több állítást is bizonyított az
ER
véletlen gráfok összefügg®ségével
kapcsolatban. Mivel a uiditást összefügg® gráfokon vizsgáljuk, ezért olyan letlen gráfokat nézünk, amelyek nagy valószín¶séggel összefügg®ek. Ha
p-t
ER(n, p)
vé-
következ®ként
választjuk meg, akkor a véletlen gráf nagy valószín¶séggel összefügg® lesz.
p=
c ln n , n
c>1
Az Erd®s-Rényi gráf magas uiditású lesz, ha a vetkez®:
|S| = o
makacsok
n log n
száma nagyságrendben a kö-
Szemléletesen ez azt jelenti, hogy ha van két makacs vélemény, akkor az
ER(n, p) véletlen
gráfban azonos módon befolyásolja a két vélemény a többiek álláspontját. Ha
n elég nagy
akkor nagy valószín¶séggel egy érték körül fognak mozogni a vélemények, ráadásul ez, két
makacs
vélemény esetén, a két vélemény átlaga lesz.
Érdemes megjegyezni, hogy a keverési id® az Erd®s-Rényi modell esetén relatíve alacsony
τ = O(ln n).
6.2. Kon gurációs modell A kon gurációs modell (vagy ahogy az idegennyelv¶ szakirodalomban nevezik
xed degree
distribution ) olyan modell, amelyben ismerjük a hálózat csúcsainak fokszámait, és ehhez 23
szeretnénk generálni egy véletlen gráfot, amelyben a csúcsok fokszámai pontosan ugyanekkorák. A véletlen gráfot úgy generáljuk, hogy vesszük az összes olyan gráfot, amelynek a csúcsai adott fokszámúak, majd egyenl® valószín¶séggel kiválasztunk egyet közülük, ez lesz a modellünk. Ebben a modellben a keveredési id®:
τ = O(ln n)
nagyságrend¶, amib®l következik,
hogy szintén magas uiditású lesz. (lásd: [1])
6.3. Barabási-Albert modell A Barabási-Albert modell a következ®. Kiindulunk egy tetsz®leges legalább két csúcsú gráfból. Majd minden lépésben hozzáveszek a gráfhoz egy újabb csúcsot, mégpedig úgy, hogy
m
éllel kapcsolódjon az eddigi gráfhoz. Az új csúcs egy régi csúcs pillanatnyi fok-
számával arányos valószín¶séggel kapcsolódik. Azaz nagyobb fokszámú csúcshoz nagyobb valószín¶séggel fog köt®dni. A modellnek ezt a jellegzetességét preferenciális kapcsolódás-
preferntal attachment
nak nevezik (
az idegennyelv¶ szakirodalomban).
Ez a modell indította el a hálózatok kutatásának virágzását az 1999-es évekt®l kezdve. Gondolhatnánk, hogy miért ilyen kés®n? Az Erd®s-Rényi modell, jó 40 éve megszületett. Ez igaz, de az Erd®s-Rényi modell inkább elméleti jelleg¶, nem igazán a valós hálózatok modellezésére alkalmas, hanem egyfajta bizonyítási eszköz, módszer. Láttuk, hogy az Erd®s-Rényi modell ritka ugyan, de nem skálafüggetlen, míg, ahogy Barabási és Albert megmérték (lásd: [3]), a valós hálózatok inkább skálafüggetlenek. Ezért Barabási és Albert javasolt egy újfajta véletlen gráfmodellt. A modell egyik motivációja a WWW volt (WWW, azaz Word Wide Web). A WWW-ben a különböz® internetes lapok egymásra hivatkoznak, ez de niál egy irányított gráfot. Barabásék ezt a gráfot szerették volna modellezni. A modellben a preferenciális kapcsolódásnak köszönhet®en a gráfban egyre nagyobb csomópontok alakulnak ki. Ami megfelel annak az intuitív képünknek is, amikor az internetes linkekre gondolunk. Hiszen ha egy lapnak sok hivatkozása van, akkor valószín¶, hogy a WWW növekedésével a lap hivatkozásainak száma még tovább gazdagodik. A Barabási-Albert modellben a fokszámok eloszlása a következ® kifejezéshez tart:
pk =
2m(m + 1) k(k + 1)(k + 2)
. Ebb®l egyrészt következik, hogy a modell részt
hatványrend¶
ritka tulajdonságú. (lásd 5.1.1 de níció). Más-
a fokszámok eloszlásának lecsengése.
24
A Barabási-Albert nagy valószín¶séggel összefügg®, így vizsgálhatjuk uiditás szempontjából. Az [1] alapján tudjuk, hogy el®z® példáinkhoz hasonlóan a keveredési id® a következ® nagyságrend¶ lesz:
τ = O(ln n)
és ezért szintén magas uiditású lesz.
6.4. Watts és Strogatz small-world modellje A modell a következ®. Vegyünk a legfeljebb
k
n csúcsot egy körben, majd minden csúcsot kössünk össze
távolságra lév® szomszédjaival (lásd 6.1 ábra). Ez lesz a kiinduló gráfunk.
Ezek után hozzáveszünk nagyságrendileg Poisson számú átlót, azaz élt két csúcs között,
pnk
átlaggal, ahol
p ∈ [0, 1].
Az éleket az
n
csúcs között lehetséges élek közül egyenl®
valószín¶séggel választjuk ki.
6.1. ábra. Watts és Strogatz small-world modelljének kiinduló gráfja
A modell megalkotását az inspirálta, hogy létrehozzanak egy olyan modellt, melyben sok a háromszög és a gráf átmér®je kicsi. Ahogy [1]-ben olvashatjuk, a keveredési id®
τ = O(ln3 n).
Tehát a modell magas uiditású lesz.
25
7. fejezet Összefoglalás Érdekes eredmény, hogy a közvélemény alakulásának modelljében az átlagos emberek véleménye nem fog konvergálni egy adott véleményhez, sosem lesz konszenzus (lásd [1]). Els®ként elszomoríthatóan hathat, hogy ha valóban így m¶ködik egy társadalom, akkor egy kérdéssel kapcsolatban soha sem lesz megegyezés a társadalom nem makacs tagjai között, (ha van legalább két különböz® makacs vélemény). De nézzünk erre az eredményre az evolúciós pszichológia szemüvegen keresztül! Tegyük fel, hogy a társadalom egy kérdésben megegyezik, csak egy vélemény lesz, és ez a társadalom szempontjából egy sikeres, jó döntés az adott történelmi helyzetben. De mi van akkor, ha változnak az id®k, változik a társadalom helyzete? A gazdaság válságba kerül, vagy háború tör ki, esetleg az életmódot teljesen megreformáló találmány terjed el. Az eddig sikeres stratégia, vagy vélemény, nem biztos hogy meg fogja állni a helyét a megváltozott körülmények között. De ha már minden különböz® véleményt elnyelt a konszenzus, akkor hogyan fog a társadalom sikeresen alkalmazkodni az új helyzethez? Tehát a társadalom sokszín¶ véleménye, konszenzus helyett kifejezetten adaptív is lehet. Másik érdekes eredmény a uiditással kapcsolatos. Amikor a uiditást megvizsgáltuk különböz® véletlen gráfmodellekben az tapasztaltuk, hogy azok magas uiditásúak voltak, annak ellenére, hogy a választott modellek igencsak különböznek egymástól. Legszembet¶n®bb eredmény, hogy mind az Erd®s-Rényi modell és mind a Barabási-Albert modell magas uiditású. A két modellt leginkább mint egymás ellentéteit szokták emlegetni. Az egyik mint hatékony elméleti eszköz (Erd®s-Rényi), a másik, mint a valóságot jól modellez® skálafüggetlen véletlen gráf (Barabási-Albert). Ahogy a [1] cikk szerz®i, akik a közvélemények alakulásának modelljét alkották meg, mi is feltehetjük a kérdést: vajon jól jellemzi a modell a valós társadalmi jelenségeket?
26
Emlékezzünk annak a szimulációnak az eredményére, amit az Erd®s-Rényi modell adott, amikor két
makacs
vélemény volt (legyen az egyik
dell egy magas uiditású hálózat, ezért a
makacs
1
másik
0).
Mivel az Erd®s-Rényi mo-
vélemények azonos mértékben fognak
hatni az átlagos emberek véleményére. Tehát, ha elég nagy gráal dolgozunk és megfelel® számú lépést megvárunk, akkor a vélemények
1 körül fognak mozogni. Ez ellentmond a 2
mindennapi intuíciónknak. Hiszen, ilyenkor a vélemények ketté szakadt táborát gyelhetjük meg. Részben annak is köszönhet®en, hogy a különböz® vélemény¶ emberek nem bíznak egymás véleményében, így feltehet®en nem fognak egymás véleményének irányában lépni. Ezt a gondolatot alátámasztja a szociálpszichológiában klasszikusnak számító elmélet, Heider egyensúlyelmélete (lásd [9]), de az egyensúly többet is mond. Az egyensúlyelmélet triádokon vizsgálja a különböz® viszonyulásokat. A triád tagjai az én (P), egy másik személy(O) és a tárgy (X), amelyet a másik személy preferál (X). Jelen esetben tárgy helyett beszélhetünk véleményr®l is. Heider szerint két esetben van egyensúlyban a hármas. Ha a másik személyt kedvelem, és vele együtt a személy véleményét is. A közvélemény alakulásának modelljében is ilyen kapcsolatokról van szó. Hiszen ha bízom valakiben, akkor közelítem a saját véleményemet az ® véleményéhez. Ellenben, van egy másik eset is. Ha a másik személyt nem kedvelem, és az a személy kedveli (x)-t, akkor én nem fogom, ha pedig nem kedveli (x)-t, akkor pedig kedvelni fogom (az ellenségem ellenfele az én jó barátom logikát fedezhetjük föl). A közvélemény alakulásának modelljének egy tovább nomításának ezt az irányt tudnám elképzelni. Összefoglalva, a fentiekben egy olyan társadalmi hálózat vélemény-dinamizmusának modelljét ismerhettük meg, amelyben feltételeztük, hogy vannak olyan emberek, akik soha nem adják fel a véleményüket. De niáltunk egy mér®számot, a uiditást, amely azt mérte, hogy a makacs vélemények mennyire egyenletesen hatnak a társadalom többi részére. A uiditást megvizsgálva több szokványos, véletlen gráfon azt tapasztaltuk, hogy a modelleknél a uiditás értéke magas. Az ismertetett modell azért hasznos eszköz, mert az eddigi, szakirodalomban intenzíven kutatott választási modellt tovább nomítja, bevezet az emberek közötti bizalmi paramétert.
27
Irodalomjegyzék [1] DAREN ACEGMOGLU, GIACOMO COMO, FABIO FAGNINI, ASUMAN OZDAGLAR
Opinion uctuations and disagreement in social networks,
Decision and
Control and European Control Conference (CDC-ECC), 2011., 50th IEEE Conference, 23472352. arXiv:1009.2653. DOI: 10.1109/CDC.2011.6161319 [2] BANGERTER, A., HEATH, C.
Scienti c Legend
The Mozart Eect: Tracking the Evolution of a
British Journal of Social Psychology, 43., 2004., 605-623.
[3] BARABÁSI ALBERT-LÁSZLÓ, ALBERT RÉKA,
networks. Science, 286, 1999, 509512, 1999.
Emergence of scaling in random
[4] CAROL BEZUIDENHOT, GEOFFREY GRIMMET,
The Critical Contact Process
Dies Out, The Annals of Probability, 1990, 1462-1464. [5] PETER DOODS, ROBY MUHAMAD, DUNCAN WATTS,
An Experimental Study
of Search in Global Social Networks, Science, 2003, 827.-829. [6] ERDS PÁL, RÉNYI ALFRÉD,
On Random Graphs I., Publicationes Mathemati-
cae, 1959, 290-297. [7] GILBERT, E. N.,
Rasndom Graphs, Annals of Mathematical Statisctics, 1959, 1141-
1144. DOI:10.1214/aoms/1177706098 [8] HEATH, C., BELL, C., STERNBERG, E.,
of Urban Legends.
Emotional Selection in Memes: The Case
Journal of Personality and Social Psychology, 81., 2001., 1028-
1041. [9] HEIDER, FRITZ
Attitudes and Cognitive Organization, The Journal of Psychology,
1946, 107?112.
28
[10] LEVIN, DAVID A., PERES, YUVAL, WILMER, ELIZABETH L.
Markov Chains
and Mixing Times, American Mathematical Society, 2009. 1-20., 47-60. [11] MOBILIA, M., PETERSEN, A., REDNER, S.,
On the role of zealotry in the voter
model, J. Statistical Mechanics: Theory and Experiments, 2007, 447?483. [12] REMCO VAN DER HOFSTAD,
Random Graphs and Complex Networks, el®készü-
letben, http://www.win.tue.nl/ rhofstad/NotesRGCN.pdf [13] JEFFREY TRIVERS, STANLEY MILGRAM,
World Problem, 1969, 425. - 443.
29
An Experimental Study of The Small
