122 Normat 52:3, 122–136 (2004)
Epidemispridning på sociala grafer
Maria Deijfen
Matematisk S tatistik
Stockholms Universitet
SE–106 91 Stockholm
mia@math.su.se
1 Inledning
Med epidemispridning menas allmänt spridning av någon slags smitta i någon typ
av population. Tänkbara exempel är en infektion som sprider sig bland invånarna
i en stad och ett rykte som sprider sig i en skolklass. För att beskriva spridningen
matematiskt behöver vi en modell, dvs en uppsättning regler som specificerar smitt-
spridningsdynamiken. Beroende på om dessa regler involverar slumpmässighet eller
ej sägs modellen vara antingen stokastisk eller deterministisk. Eftersom det är na-
turligt att tänka sig att en smittmekanism innefattar ett element av slump – det är
sällan vi säkert vet att en individ kommer att bli smittad – är det rimligt att anta
att en stokastisk modell bättre fångar beteendet hos en epidemi. Priset för denna
högre grad av realism är att en stokastisk modell i regel är betydligt mer kompli-
cerad att analysera än en deterministisk och en rad förenklande antaganden måste
införas för att modellen ska kunna hanteras. I majoriteten av de stokastiska epide-
mimodeller som har studerats antas att populationen i vilken epidemin äger rum är
(a) sluten, dvs inga dödsfall/födslar och ingen immigration/emigration äger rum;
(b) homogen, dvs alla individer är av samma typ vad gäller smittsamhet/mot-
taglighet; (c) homogent blandad, dvs en given individ har med samma sannolikhet
kontakt med varje annan individ.
I den här uppsatsen ska vi studera den enklaste stokastiska epidemimodellen,
Reed & Frost-modellen, och försöka släppa på antagandet om homogen blandning
i populationen. Att en population är homogent blandad inneb är att den saknar
social struktur, vilket naturligtvis är mycket orealistiskt. I själva ve rket består
deijfen.tex,v 1.11
Normat 3/2004 Maria Deijfen 123
en mänsklig population av en rad sociala grupperingar – hushåll, arbetsplatser,
skolklasser etc – där kontakter sker i långt större utsträckning än i den övriga
populationen. För att representera denna sociala struktur ska vi använda grafer,
där noderna representerar individer och kanterna representerar sociala relationer.
Smittan i fråga sprids sedan längs detta nätverk.
De populationer s om betraktas i epidemimodellering är typiskt mycket stora,
vilket betyder att det är omöjligt att i detalj kartlägga de sociala relationerna. För
att modellera den sociala grafen ska vi därför använda slumpgrafer, dvs grafer där
kanterna är genererade av någon typ av slumpmekanism. Problemställningen som
ska behandlas är tvådelad. Dels vill vi hitta en slumpmekanism som ger grafer som
liknar verkliga sociala nätverk, dels vill vi undersöka hur smittspridningen påverkas
av den underliggande grafen. De epidemiska storheter vi kommer att intressera oss
för är:
– Reproduktionstalet, R
0
. En kritisk storhet som beror av modellens parametrar
och som är definierad så att ett stort utbrott – dvs ett utbrott av samma stor-
leksordning som hela populationen – är möjligt om och endast om R
0
> 1.
I de modeller vi ska studera ges R
0
av det förväntade antalet nya smittfall som
genereras av en given smittad ind ivid i en stor mottaglig population.
– Epidemins slutstorlek, , som anger hur stor andel av populationen som har
upplevt smittan när ep idemin upphör.
Resten av uppsatsen är upplagd så att avsnitt 2 innehåller en beskrivning av den
vanliga Reed & Frost-modellen med en homogent blandad population, i avsnitt
3 modifieras modellen så att social struktur i form av en underliggande graf in-
kluderas och i avsnitt 4–6 behandlas ett antal olika slumpgrafkonstruktioner och
deras effekter på epidemiprocessen. Läsaren förutsätts vara bekant med grundläg-
gande begrepp inom san nolikhetsteorin. Referenser förekommer relativt sparsamt
– för vidare läsning hänvisas till Andersson och Britton (2000) samt, när det gäller
epidemispridning på grafer, till Andersson (1999) och Deijfen (2000).
2 Reed & Frost-modellen
En av de första stokastiska epidemimodellerna introduc erades 1928 av Reed och
Frost. Mo de llen beskriver spridning av en smitta i en sluten, homogen population
som vid tid t =0består av n osmittade mottagliga individer och en smittsam
individ. Dynamiken är följande: Antag att en individ i är smittsam vid tid t (t =
0, 1, 2,...). En given mottaglig individ j smittas av i med sannolikhet /n, där
>0, och blir, i händelse av en smittöverföring, smittsam vid tid t +1. Individ i
avlägsnas från den epidemiska processen vid tid t +1– tex till följd av immunitet
eller isolering – och deltar sedan inte vidare i spridningsförloppet. Alla kontakter
antas s ke oberoend e av varandra och epidemin upphör när det inte finns några
smittsamma individer kvar i populationen.
Enligt ovanstående beskrivning förutsätter Reed & Frost-modellen en latent pe-
rio d om en tidsenhet följd av en mycket kort smittsam perio d , under vilken en given
smittsam individ för smittan vidare till en given mottaglig individ med sannolikhet
deijfen.tex,v 1.11
124 Maria Deijfen Normat 3/2004
/n. De smittsamma individerna kan alltså delas in i generationer och vi ska nu
beskriva hur de inledande faserna i denna generationsprocess kan approximeras av
en så kallad förgreningsprocess om populationen är stor.
För att förklara dynamiken i en förgreningprocess, betrakta utvecklingen av en
ätt där varje individ, under sin livstid, föder ett slumpmässigt antal barn. Des-
sa barn föder i sin tur ett slumpmässigt antal barn, osv. En förgreningsprocess
{X
k
}
k0
anger antalet individer i generation k, dvs d et sammanlagda antalet barn
som produceras av individerna i generation k 1. Reglerna för reproduktionen är
att alla individer föder barn enligt samma fördelning, oberoende av varandra. Van-
ligtvis antas att ätten vid tid t =0består av en enda individ – en stamfader –
varifrån alla andra individer härstammar.
I förgreningsprocesstolkningen av en Reed & Frost-epidemi fungerar den individ
som är smittsam vid tid t =0som stamfader och en födelse i förgreningsprocessen
svarar mot uppkomsten av en ny smittsam individ i epidemiprocessen. Eftersom
det från början fi nn s n stycken mottagliga individer som var och en smittas med
sannolikhet /n, så är antalet nya smittfall som genereras av den initialt smittade
individen binomialfördelat med parametrar n och /n, dvs sannolikheten att precis
k nya smittfall genereras ges av
b
k
=
n
k
1
n
nk
n
k
,k=0, 1, . . . , n.
För en given smittsam individ i en se nare generation är fördelningen för antalet nya
smittfall inte riktigt densamma, eftersom en del av de n initialt mottagliga indivi-
derna nu redan har blivit smittade och därmed inte längre deltar i processen. Om vi
fortfarande befinner oss i början av epidemiprocessen och om populationen är stor,
så är den avlägsnade andelen av populationen dock mycket liten och fördelningen
för antalet nya smittfall s om genereras av en given smittsam individ approximeras
väl av en binomialfördelning med parametrar n och /n. Då n är stort kan denna
fördelning ersättas av en Poissonfördelning med parameter – det gäller ju att
b
k
n
k
k!
1
n
nk
k
n
k
k
k!
e
då n ,
där högerledet känns igen som en Poisson-sannolikhet. Sammanfattningsvis har
vi ”visat” att en Reed & Frost-epidemi i en stor population under de inledande
faserna beter sig som en förgreningsprocess där avkomman är Poissonfördelad med
parameter .
I denna uppsats ska vi uteslutande fokusera oss på epidemispridning i stora
populationer. Detta betyder att asymptotiska resultat, dvs resultat härledda då
n , kan antas gälla med god noggrannhet. Det förklarar också varför smitt-
sannolikheten, p
s
, måste skalas med n: Enligt ovanstående resonemang genererar
en smittsam individ i genomsnitt np
s
nya smittfall. Om p
s
p, gäller förstås att
np
s
då n , vilket medför att epidemin exploderar och med sannolikhet 1
drabbar hela populationen – en tämligen ointressant modell. Om däremot p
s
= /n,
är np
s
= oberoende av n och modellen b lir icke-trivial även i stora populationer.
Låt oss till exempel härleda asymptotiska uttryck för reproduktionstalet, R
0
,och
slutstorleken. Följande grundläggande sats från förgreningsprocessteorin kommer
att vara till hjälp.
deijfen.tex,v 1.11
Normat 3/2004 Maria Deijfen 125
Sats 1 Betrakta en förgreningsprocess där varje individ producerar i genomsnitt
barn och låt Z beteckna det sammanlagda antalet individer som genereras i proces-
sen. Då gäller:
(i) 1 P (Z<)=1;
(ii) >1 P (Z = ) > 0.
Reproduktionstal: Som beskrivits ovan kan de inledande faserna av den generations-
process som definieras av de smittsamma individerna i en Reed & Frost-epidemi
approximeras av en förgreningsprocess där varje individ föder ett Poissonfördelat
antal barn med väntevärde .Om 1 är, enligt Sats 1, den totala avkomman i
denna förgreningsprocess ändlig med sannolikhet 1. Detta betyder att förgrenings-
processen så småningom dör ut och ett stort utbrott i epidemiprocessen är därmed
omöjligt. Om >1 däremot, finns en positiv sannolikhet att förgreningsprocess en
exploderar, vilket ger upphov till ett stort utbrott i epidemiprocessen. Alltså har
vi R
0
= i Reed-Frost modellen.
Slutstorlek: Sannolikheten att en given mottaglig individ undgår att smittas av
en given smittsam individ är 1 /n och för att undslippa epidemin måste den
mottagliga individen undgå smitta från samtliga n individer som är smittsamma
under epidemins gång. Sannolikheten att en given individ aldrig smittas är alltså
(1 /n)
n
vilket konvergerar mot e
då n . Asymptotiskt ska sannolikheten
att en given individ undgår smitta vara lika med andelen av populationen som
undgår smitta, och vi får alltså
(1) 1 = e
.
För 1 är =0den end a lösningen till denna ekvation. Detta reflekterar det
faktum att stora utbrott inte är möjliga då 1.Om>1 finns en positiv
sannolikhet att ett stort utbrott inträffar och det visar sig att ekvationen (1) för
slutstorleken i detta fall även har en icke-trivial lösning i intervallet (0, 1]. Denna
lösning, som ses plottad mot i Figur 1, anger slutstorleken i händelse av ett stort
utbrott.
3 Reed & Frost-epidemier på grafer
I Reed & Frost-modellen för en given smittsam individ smittan vidare till samtliga
andra individer med samma sannolikhet /n, vilket i en stor population är ett
mycket litet tal. Detta stämmer naturligtvis dåligt överens med dynamiken i en
verklig epidemi. En mer realistisk modell vore att låta en smittsam individ smitta
de individer hon faktiskt har kontakt med – familj, vänner, arbetskamrater etc –
med någon sannolikhet p som inte beror av populationsstorleken. Vi ska nu beskriva
hur Reed & Frost-modellen, genom att en social graf införs, kan anpassas så att
detta blir fallet.
En graf G består av en upps ättning noder, V =(v
1
,...,v
n
), och ett antal kanter,
E =(e
1
,...,e
k
), som sammanbinder par av noder. Varje kant kan skrivas som ett
deijfen.tex,v 1.11
126 Maria Deijfen Normat 3/2004
0 1 2 3 4 5 6
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Figur 1 : Slutstorlek vid stort utbrott i en Reed-Frost epidemi, som funktion av .
par av noder (v
i
,v
j
). Två noder tillhör samma komponent i grafen om det finns en
stig som sammanbinder dem, dvs om det går att ta sig från den ena noden till den
andra via kanter i grafen. Om den kortaste stigen mellan två noder v
i
och v
j
består
av en enda kant, dvs om (v
i
,v
j
) E, så sägs v
i
och v
j
vara grannar. Slutligen
definierar vi graden hos en nod som antalet grannar till noden.
En graf kan användas för att representera social struktur i en population och
kallas då för ett sociogram. I ett sociogram representerar varje nod en individ och
kanterna svarar mot sociala relationer mellan individerna. Antag nu att vi vill
studera spridningen av en smitta i en sluten, homogen population av storlek n där
den sociala strukturen beskrivs av sociogrammet G. Reed & Frost-modellen kan då
modifieras på följande sätt: Vid tid t =0introducerar vi smittan i populationen
genom att smitta ner en slumpmässigt vald individ. En individ i som är smittsam
vid tid t (t =0, 1, 2,...) smittar sedan ner en given mottaglig granne i G, j, med
sannolikhet p, och i händelse av en smittöverföring blir j smittsam vid tid t +1.
Individen i avlägsnas från den epidemiska proc ess en vid tid t +1 – tex till följd av
immunitet eller isolering – och deltar sedan inte vidare i spridningsförloppet. Alla
kontakter antas ske oberoende av varandra och epidemin upphör när det inte finns
några smittsamma individer kvar i populationen.
Denna modell påminner mycket om modellen från avsnitt 2, men det finns två
viktiga skillnader: En smittsam individ kan bara smitta ner sina grannar i det
sociala nätverket och smittsannolikheten är inte skalad med populationsstorleken.
Att endast grannar i den sociala grafen kan smittas betyder att populationen inte
längre är homogent blandad och modellen kallas därför ibland för den heterogena
Reed & Frost-modellen. I den homogena Reed & Frost-modellen, där en smittsam
individ kan infektera samtliga mottagliga individer i populationen, var vi tvungna
att skala smittsannolikheten med populationsstorleken för att förhindra epidemin
från att explodera. I denna nya formulering är detta inte nödvändigt, förutsatt att
deijfen.tex,v 1.11
Normat 3/2004 Maria Deijfen 127
den sociala grafen har begränsade gradtal, så att antalet grannar till en individ
alltså är litet i förhållande till p opulationsstorleken.
Eftersom vi intress erar oss för epidemier i stora populationer är det omöjligt att i
detalj ta reda på hur sociogrammet ser ut. I denna uppsats ska vi låta kanterna som
representerar bekantskapsstrukturen gen ereras av en slumpmekanism och vi vill
förstås att den graf vi får ska likna ett verkligt sociogram. Här är några egenskaper
vi strävar efter.
– Begränsad grad: Det f örväntade antalet grannar till en given nod ska förbli ändligt
då n . I ett sociogram reflekterar detta det faktum att bekantskapskretsar
är begränsade i storlek även i stora populationer.
– Transitivitet: Vi vill att grafen ska innehålla många trianglar. Detta är en av
de mest utmärkande egenskaperna hos sociala nätverk och förklaras av att vi
kan förvänta oss att många av våra vänner är bekanta också med varandra.
Mekanismen som genererar kanterna bör alltså vara sådan att sannolikheten att
en viss kant finns med i grafen, givet grafens utseende i övrigt, är större om
noderna som den förbinder har en gemensam granne.
– Realistisk beroendestruktur: Grafen får inte uppvisa onaturliga beroenden mellan
kanterna. Hurvida en viss kant finns med i grafen eller ej bör tex inte påverkas
av information om delar av grafen som ligger långt ifrån kanten i fråga. Detta
eftersom en individs sociala beteende normalt inte påverkas av individer som hon
inte har någon slags anknytning till.
Resten av denna uppsats kommer att ägnas åt exempel på olika typer av slumpgraf-
konstruktioner. Vi studerar hur grafen påverkar epidemispridningen i en h eterogen
Reed & Frost-modell samt undersöker om den kan anses utgöra en god modell för
ett socialt nätverk.
4 Bernoulligrafer och triangelgrafer
Den enklaste tänkbara slumpgrafmodellen är Bernoulligrafen. Givet n +1stycken
noder genererar man en Bernoulligraf genom att, oberoend e av varandra, inkludera
var och en av de
n+1
2
möjliga kanterna med sannolikhet r. För en given nod v
i
finns
n möjliga grannar och var och en av dessa är förbundna med v
i
med sannolikhet r.
Antalet grannar till en given nod är alltså binomialfördelat med parametrar n och
r. För att den förväntade graden, nr, ska förbli ändlig då n låter vi r = /n
för något >0.
Låt oss härleda as ymptotiska uttryck för reproduktionstalet och slutstorleken
hos en Reed & Frost-epidemi på en Bernoulligraf.
Reproduktionstal: I en stor popu lation är kontaktade individer med stor sannolikhet
mottagliga i början av epidemin och de inledande faserna av generationsprocesse n
av smittsamma individer b e ter sig därför ungef är som en förgreningsprocess. Enligt
Sats 1 finns en positiv sannolikhet att denna förgreningsprocess exploderar (och
därmed ger upphov till ett stort utbrott i epidemiprocessen) om och endast om
varje individ i genomsnitt föd er mer än ett barn. Den kritiska parametern R
0
för
deijfen.tex,v 1.11
128 Maria Deijfen Normat 3/2004
epidemiprocessen fås följaktligen som reproduktionsmedelvärdet i förgreningspro-
cessen, vilket i epidemitermer motsvaras av det förväntade antalet nya smittfall
som genereras av en smittsam in divid i början av epidemin.
För att hitta ett uttryck för R
0
, betrakta en given smittsam individ i i bör-
jan av en Reed & Frost-epidemi i en stor population där bekantskapsstrukturen
representeras av en Be rnoulligraf G. Låt M
i
beteckna antalet mottagliga grannar
till i i G. Var och en av dessa grannar smittas av i med sannolikhet p, så an-
talet nya smittfall genererade av i är binomialfördelat med parametrar M
i
och
p. Det går att visa att väntevärdet i denna fördelning är E[M
i
]p. Eftersom po-
pulationen är stor är kantsannolikheten i Bernoulligrafen liten och det är därför
osannolikt att i har en bekantskapskant till någon av de få individer som in-
te längre är mottagliga, bortsett förstås från den individ varifrån smittan kom.
Antalet mottagliga grannar, M
i
, är alltså ungefär binomialfördelat med paramet-
rar n 1 och /n och ef tersom n är stort approximeras denna fördelning väl
av e n Poissonfördelning med parameter . Vi har alltså E[M
i
]= och således
R
0
= p.
Slutstorlek: Låt A
i
beteckna händelsen att en given individ i undgår epidemin och
låt D
i
beteckna antalet grannar till i i G. Vi har då att
P (A
i
)=E
P (A
i
|D
i
)
= E
P (A
j
i
)
D
i
,
där A
j
i
är händelsen att i undslipper smitta från en given granne j. Asymptotiskt
är sannolikheten att j blir smittad d ens amma som andelen av populationen som
drabbas av epidemin, dvs , och om j blir smittad så för hon smittan vidare till i
med san nolikhet p. Det följer att P (A
j
i
)=1 p och alltså
(2) P (A
i
)=E
(1 p )
D
i
.
Den sannolikhetsgenererande funktionen för en stokastisk variabel X definieras
allmänt som
X
(k)=E[k
X
] och, om X är Poissonfördelad med parameter , så fås
att
X
(k)=e
(1k)
. Högerledet i (2) känns igen som den sannolikhetsgenererande
funktionen för D
i
i punkten 1p och, eftersom D
i
är asymptotiskt Poissonfördelad
med parameter , så har vi
P (A
i
)=e
p
.
Asymptotiskt ska sannolikheten att en given individ undgår smitta vara lika med
andelen av populationen som slipper undan epidemin. Epidemins slutstorlek, ,
bestäms alltså av ekvationen
1 = e
p
.
För givna värden på p och löses denna ekvation enkelt numeriskt.
Är nu en Bernoulligraf en bra modell för ett socialt nätverk? Eftersom kantsannolik-
heten är skalad med populationsstorleken är den asymptotiska genomsnittsgraden
i grafen ändlig, men hur är det med de övriga kraven vi ställde upp på s. 127? Låt
oss tex un dersöka grafens transitivitet – minns att sociala nätverk har en hög grad
av transitivitet eftersom sannolikheten att två individer lär känna varandra är stor
om de har en gemensam bekant. I en Bernoulligraf är ju dock san nolikheten att två
deijfen.tex,v 1.11
Normat 3/2004 Maria Deijfen 129
noder sammanbinds av en kant /n oavsett om noderna har en gemensam granne
eller ej, eftersom alla kanter inkluderas oberoende av varandra. Detta betyder att
grafen asymptotiskt kommer att innehålla mycket få trianglar och alltså inte kan
anses vara en god mode ll för ett socialt n ätverk.
Ett försök att öka grafens transitivitet är följande: Förutom att inkludera varje
möjlig kant med sannolikhet r = /n, inkluderar vi, oberoende av varandra, även
var och en av grafens
n+1
3
möjliga trianglar med någon sannolikhet ˜r. Detta ger
en graf G som kan skrivas som unionen av en Bernoulligraf G
1
och en triangelgraf
G
2
. Multipla kanter mellan två noder i denna konstruktion reduceras till en, så att
varje nodpar alltså förbinds av högst en kant.
Kantsannolikheten i Bernoulligrafen är skalad med populationsstorleken så att
G
1
har ge nomsn ittsgrad för alla n. För att den asymptotiska genomsnittsgraden
i G = G
1
G
2
ska vara ändlig krävs att även triangelsannolikheten ˜r skalas på rätt
sätt. Graden för en given nod v i G
2
är 2X, där X betecknar antalet trianglar som
har ett av sina hörn i v. Eftersom de andra två hörnen ska väljas bland övriga n
noder finns
n
2
möjliga trianglar som innehåller v och var och en av dessa trianglar
inkluderas i G
2
med sannolikhet ˜r. Alltså är X binomialfördelad med parametrar
n
2
och ˜r, och för att väntevärdet i denna fördelning ska förbli ändligt då n
låter vi ˜r =
˜
/
n
2
för något
˜
>0.
I Deijfen (2000) härleds asymptotiska uttryck för reproduktionstalet, R
0
,och
slutstorleken, , för en Reed & Frost-modell på den graf som beskrivs ovan. Det
visar sig att
R
0
= p +2
˜
(p + p
2
p
3
)
och för slutstorleken fås ekvationen
1 = exp
p
˜
2(2 )p + (2 3)p
2
2 (1 )p
3
.
För detaljer hänvisas till Deijfen (2000).
Via parametern
˜
kan vi styra andelen trianglar i en triangelgraf och bristen på
transitivitet hos Bernoulligrafen kan alltså kompe nse ras genom att
˜
väljs tillräck-
ligt stor. Det visar sig dock att triangelgrafen har en beroendestruktur som inte är
riktigt naturlig i ett socialt nätverk. För att förstå detta, betrakta sannolikheten
att det finns en kant mellan två givna noder v
i
och v
j
i en triangelgraf, givet resten
av grafen (dvs hela konfigurationen av kanter, undantaget kanten mellan v
i
och v
j
,
är given). Om kanten (v
i
,v
j
) inte skapar en triangel är sannolikheten att den finns
med i grafen 0. Antag å andra sidan att kanten f aktiskt skapar en triangel, dvs
att v
i
och v
j
har en gemensam granne v
k
. Om kanterna (v
i
,v
k
) och (v
j
,v
k
) redan
ingår i andra trianglar så är den betingade sannolikheten att kanten (v
i
,v
j
) finns
med i grafen
1
1
˜
n
2
n1
2
˜
/n,
eftersom minst en av de n 1 möjliga trianglarna med hörn i v
i
och v
j
måste
inkluderas. Ingår (v
i
,v
k
) och (v
j
,v
k
) däremot inte i andra trianglar så finns det
med sannolikhet 1 en kant mellan v
i
och v
j
. Sannolikheten att två individer i och
j är bekanta med varandra påverkas alltså inte bara av om de har en gemens am
bekant eller ej (dvs av om en kant mellan v
i
och v
j
skulle skapa en triangel eller ej),
deijfen.tex,v 1.11
130 Maria Deijfen Normat 3/2004
utan även av bekantskapsformationer som inte är gemensamma för de två indivi-
derna (ingår v
i
och v
j
i andra trianglar eller ej?). Sådan information är normalt
inte relevant i en social graf och, även om fenomenet mildras något av Bernoulli-
grafen, så minskar detta beteende lämpligheten hos denna sammansmältning av en
Bernoulligraf och en triangelgraf som mo de ll för ett socialt n ätverk.
5 Markovgrafer
Markovgrafen är ett försök att skapa en transitiv grafmodell utan den typ av ona-
turliga beroenden mellan kanterna som triangelgrafen uppvisar. Definitionen av
modellen ges i form av ett sannolikhetsmått som innehåller en parameter som styr
antalet trianglar i grafen och där kanter som inte har någon gemensam nod är obe-
ro e nde . Tyvärr visar det sig att modellen har ett mycket onaturligt asymptotiskt
beteende. I detta avsnitt är det viktigt att skilja mellan en slumpgraf som stokastisk
modell för generering av kanter och en konkret realisering av denna. Vi kommer
därför att reservera beteckningen G för den stokastiska modellen och skriva G för
realiseringar.
En graf med n noder kan beskrivas av kantindikatorer {I
ij
} (i, j =1,...n)
definierade så att
I
ij
=
1 om (v
i
,v
j
) E
0 annars,
dvs I
ij
=1om det finns en kant mellan noderna v
i
och v
j
och I
ij
=0annars. I
en slumpgrafmodell G är kantindikatorerna stokastiska variabler och vi kan införa
en beroendegraf, D. Detta är en icke-stokastisk graf som konstrueras genom att
varje kantindikator representeras med en nod och en kant ritas mellan två node r
om motsvarande indikatorer är beroende givet övriga indikatorer. Noderna i D är
alltså de möjliga kanterna i G o ch kanterna i D svarar mot de par av kanter i G
som är betingat beroende.
Med e n klick menas inom grafteorin en fullständig delgraf, d vs en delmängd av
noderna sådan att samtliga möjliga kanter finns med. Klickbegreppet är centralt
i följande sats, som specificerar sannolikhetsfunktionen för en slumpgrafmodell G
med given beroende struktur D.
Sats 2 Betrakta en given realisering G av en slumpgraf G med beroendestruktur D
och låt E beteckna kantmängen i G. Grafen G har sannolikhet
P (G)=z
1
exp
KE
(K)
,
där (K) är en godtycklig konstant om K är en klick i D och (K)=0annars.
De enda egenskaper vi kan styra hos en slumpgraf är alltså de som på något sätt är
kopplade till klickar i beroe nd egrafen. En sådan egenskap kan belönas (bestraffas)
genom att konstanterna (K) väljs så att grafer som uppvisar e gens kapen i fråga
ges större (mindre) sann olikhet än grafer som inte gör det.
deijfen.tex,v 1.11
Normat 3/2004 Maria Deijfen 131
En slumpgrafmodell G sägs vara Markovsk om dess beroendegraf inte innehål-
ler några kanter mellan indikatorer I
ij
och I
kl
som svarar mot disjunkta nodpar
(kanter). Två kanter i en Markovgraf tillåts alltså vara beroende endast om de
har en gemensam nod. Klickarna i beroendegrafen svarar såled es mot kantmäng-
der där samtliga kanter har en nod gemensam och de enda konfigurationer där
detta är fallet är trianglar, T
v
i
v
j
v
k
= {(v
i
,v
j
), (v
j
,v
k
), (v
k
,v
i
)}, och stjärnor,
S
v
i
0
...v
i
k
= {(v
i
0
,v
i
l
); l =1,...,k}, där k =1,...n 1.
Låt oss nu formulera Sats 2 i fallet då G är Markovsk. Introducera först no-
tationen (T
v
i
v
j
v
k
)=
ijk
och (S
v
i
0
...v
i
k
)=
i
0
...i
k
. För att förenkla modellen
och reducera antalet parametrar antar vi att isomorfa grafer har samma sannolik-
het. Detta betyder att vi, istället för att introducera en parameter för varje möjlig
triangel, nöjer oss med en enda triangelparameter som styr d et totala antalet tri-
anglar i grafen och, på samma sätt, för varje k definierar vi en enda parameter som
kontrollerar det totala antalet k-stjärnor. Vi har alltså
ijk
= och
i
0
...i
k
=
k
.
Sannolikhetsfunktionen för en Markovgraf fås nu som ett korrollarium till Sats 2.
Korrollarium 3 En given realisering G av en Markovgraf med n noder har san-
nolikhet
P (G)=z
1
exp
t(G)+
n1
k=1
k
s
k
(G)
,
där t(G) är antalet trianglar och s
k
(G) antalet k-stjärnor i G.
I en Markovgrafmodell tillåts kanter vara beroende endast om de har en nod ge-
mensam. I termer av bekantskapsformationer betyder detta att en individs sociala
beteende endast kan påverkas av individer som hon har någon typ av relation till,
vilket ju är en naturlig egenskap hos ett socialt nätverk. Markovgrafmodellen in-
nehåller dessutom en parameter, , som gör det möjligt att styra antalet trianglar
i grafen – genom att välja >0 åstadkoms ett mått som belönar grafer med
många trianglar. Så långt tycks Markovgrafen vara en mycket lovande modell för
ett socialt nätverk. Som nämndes i detta avsnitts inledning visar det sig dock att
grafen har ett ofördelaktigt asymptotiskt beteende: I Strauss (1986) visas att, om
>0, s å gäller att sannolikheten att en godtyckligt stor andel av kanterna i grafen
samlas i en enda stor klick konvergerar mot 1 då n . För ett socialt nätverk
betyder detta att samtliga bekantskapskanter i en stor population med stor sanno-
likhet kommer att vara samlade i en enda jättelik bekantskapskomp onent där alla
individer är bekanta med varand ra. Detta gör Markovgrafen mycket olämplig som
nätverksmod ell.
Låt oss illustrera Strauss’ resultat med hjälp av en simulering. För att för-
enkla simuleringen har vi valt
k
=0för alla k och måttet blir alltså P (G)=
z
1
exp{t(G)}. Vidare har vi fixerat grafens genomsnittsgrad. Eftersom det i
en graf med n noder och genomsnittsgrad d finns ungefär nd/2 kanter, så är
detta i princip detsamma som att fixera antalet kanter i grafen. Markovgrafer
med n noder och nd/2 kanter har genererats med hjälp av MCMC-metoder
och det förväntade antalet trianglar i grafen har beräknats genom att utnyttja
att tidsmedelvärdet i en Markovkedja konvergerar mot väntevärdet – se Deijfen
(2000) för detaljer angående detta. Simuleringarna är mycket tidskrävande varför
endast relativt små grafer har studerats – den största grafen har n = 30 noder.
deijfen.tex,v 1.11
132 Maria Deijfen Normat 3/2004
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2
0
50
100
150
200
250
300
Figur 2 : Förväntat och maximalt antal trianglar som funktion av i en Markovgraf
med 10, 20 respek tive 30 noder och genomsnittsgrad 5.
Det maximala antalet trianglar i en graf med ett fixt antal kanter fås förstås om
kanterna är samlade i en enda klick. Storleken, k
max
, hos den maximala klicken fås
ur sambandet
k
max
2
= nd/2. Approximativt har vi k
max
=
nd och det maximala
antalet trianglar i grafen är alltså
nd
3
. Markovgrafens degenererade beteende
illustreras i Figur 2. Vi ser där att, då blir positiv, så närmar sig det förväntade
antalet trianglar i grafen snabbt det maximala antalet (som är markerat med räta
linjer), vilket betyder att samtliga kanter är samlade i en klick. Omslagspunkten,
som för den största grafen med n =30noder infaller i närheten av =0.5, kryper
för större grafer in mot =0.
6 ”Small-world”-grafer
Att möta en fullständig främling och upptäcka att man h ar en gemensam bekant
är något som många av oss har varit med om. ”Världen är liten!” kanske vi ut-
brister. Faktum är att detta är ett fen omen som har observerats i många verkliga
sociala nätverk: Väljer vi ut två go d tyckliga individer så kan de ofta förbindas
med en förvånansvärt kort bekantskapskedja, se tex Milgram (1967). Detta är an-
märkningsvärt eftersom sociala nätverk för det mesta är (a) stora; (b) glesa, dvs
genomsnittsgraden är liten jämfört med populationsstorleken; (c) decentraliserade,
dvs de innehåller ingen centralnod till vilken de fle sta andra n od er är länkade.
”Small-world”-nätve rken introducerades av Strogatz och Watts (1998) och är ett
försök att skapa transitiva grafer med korta stigar. Transitivitet och korta stigar
är egenskaper som i förstone kan tyckas svåra att förena hos en graf, eftersom
deijfen.tex,v 1.11
Normat 3/2004 Maria Deijfen 133
transitivitet uppstår då vi ”klumpar ihop” kanterna och korta stigar då vi sprider
ut dem, men i det här avsnittet ska vi beskriva en konstruktion som faktiskt lyckas
med d etta förutsatt att dess parametrar väljs på rätt sätt. För att kvantifiera
transitiviteten och stiglängden inför vi följande storheter:
– Klustringsindex, C. Antag att en given nod v
i
har k grannar. Om k 2 finns
k
2
möjliga kanter mellan d es sa grannar. Låt E
v
i
beteckna antalet av dessa möjliga
kanter som finns med i grafen och definera klustringen för noden v
i
som
C
v
i
=
E
v
i
k
2
om k 2,
|E| k
n
2
(n 1)
om k<2.
(Definitionen av C
v
i
för k<2, som vid första anblicken kan verka lite krånglig,
är nödvändig för att komma runt problemet med noll-division. Den kan tolkas
som den övergripande klustringen i resten av grafen och anger hur stor andel av
de totalt
n
2
(n 1) möjliga kanterna utan anknytning till noden v
i
som är
inkluderade i grafen.) Klustringsinde xet för grafen definieras nu som
C =
1
n
n
i=1
C
v
i
.
I ett socialt nätverk är klustringsindexet ett mått på i vilken utsträckning våra
vänner är vänner också med varandra.
– Stiglängdsindex, L. För en given graf med n noder, låt S
m
beteckna antalet nod-
par mellan vilka den kortaste stigen består av mer än m kanter (m =1,...,n1)
eller som inte har någon stig alls emellan sig och definiera L
m
= S
m
/
n
2
, dvs L
m
är andelen nodpar i grafen som ligger långt ifrån varandra i den meningen att
det krävs mer än m länkar för att ta sig från den ena nod en till den andra, om
det överhuvudtaget går. Vill vi kunna använda detta mått för att j ämföra grafer
med olika antal node r bör m väljas som en växande funktion av n: Bekantskaps-
kedjorna är troligen längre i en storstad med 1 000 000 invånare än i en ort med
1 000 invånare. Vi väljer m = log n och skriver L
log n
= L.
En graf sägs vara ett ”small-world”-n ätverk om klustringsindex är stort och stig-
längdsindex litet. Vad menas då med ”stort”/”litet” här? Det största möjliga värdet
för C är 1, vilket antas i en fullständig graf (dvs en graf där samtliga kanter fi nn s
med), och det minsta tänkbara värdet är 0, vilket antas i en tom graf (dvs en
graf som saknar kanter). Dessa två grafer är också extrema i fråga om stiglängd.
Det är dock inte särskilt instruktivt att jämföra dessa grafer med varandra, ef-
tersom klustringen förstås ökar och stiglängden minskar då fler kanter adderas till
en graf. Vi ska här stude ra grafer med ett fixt antal kanter och se hur klustringen
och stiglängden påverkas då vi, genom att justera modellens parametrar, förändrar
fördelningen av kanterna över grafen. Målet är att hitta en struktur som ger ett
stort värde på C och ett litet värde på L, där ”stort”/”litet” ska ses i relation till
det största/minsta möjliga värdet för en graf med det givna antalet kante r.
deijfen.tex,v 1.11
134 Maria Deijfen Normat 3/2004
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Figur 3 : Klustringsindex (heldragen linje) och stiglängdsindex (streckad linje), ska-
lade med värdet för r =1, som funktion av r.
För att konstruera nätverket, arrangera de n noderna i en cirkel. Låt G
1
vara
en graf där varje nod sammanbinds med var och en av sina k närmaste grannar
åt båda håll med sannolikhet r, där k n, och låt G
2
vara en Bernoulligraf med
kantsannolikhet /n. Grafen G
1
är här tänkt att representera en lokal bekantskaps-
struktur (tex det nätverk som uppstår då vi lär känna folk i vårt eget kvarter) och
Bernoulligrafen G
2
representerar globala kontakter (tex människor vi lär känna när
vi är ute och reser). Den graf vi ska studera är G = G
1
G
2
.
Låt d b ete ckna den asymptotiska genomsnittsgraden i G. Eftersom k n är det,
om n är stort, mycket osannolikt att en Bernoullikant ska överlappa en kant i G
1
.
Genomsnittsgraden i G ges därför asymptotiskt av summan av genomsnittsgraderna
i G
1
och G
2
, dvs d =2kr + . För att reducera antalet fria parametrar i modellen,
fixerar vi genomsnittsgraden till 2k så att
(3) 2kr + =2k.
(Eftersom vi fritt kan välja k när vi konstruerar grafen är den enda inskränkning-
en här att vi antar att genomsnittsgraden är ett jämnt tal.) Detta är i princip
detsamma som att fixera antalet kanter i grafen till nk. Är det nu möj ligt att väl-
ja parametrarna r och så att klustringsindex, C, är stort och stiglängdsind ex,
L, litet i relation till de extrema värdena för en graf med nk kanter? I Figur 3
visas simulerade klustrings- och stiglängdsindex för olika värden på den lokala kon-
taktsannolikheten r. Den globala kontaktparametern fås ur (3). De simulerade
graferna har n = 500 noder och genomsnittsgrad d =4(dvs k =2). Då r minskas
från 1 ser vi först ett kraftigt fall för L, följt av ett intervall där L är litet samtidigt
som C fortfarande är stort. För r i detta intervall, säg r (0.8, 0.9), uppvisar gra-
fen ett ”small-world”-b eteen de. Mins kas r ytterligare avtar C mot sitt låga värde
för den rena Bernoulligrafen (som vi har då r =0) och ”small-world”-egenskap e n
deijfen.tex,v 1.11
Normat 3/2004 Maria Deijfen 135
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
50
100
150
200
250
300
350
Figur 4 : Genomsnittlig storlek hos den största komponenten i smittgrafen som funk-
tion av mot r då n = 500, k =2och p =0.4.
förstörs. Denna simulering ger vid handen att vi, genom att introdu cera endast en
mycket liten andel globala kanter i nätverket, minskar s tiglängden dramatiskt utan
att påverka klustringen nämnvärt, med ett ”small-world”-nätverk som resultat.
Reproduktionstal: För k =1visas i Deijfen (2000) att
R
0
=
2pr
1 pr
+1
p.
För att skapa ett realistiskt nätverk krävs dock större värden på k, säg k 10,och
för sådana k saknas explicita uttryck för R
0
– se dock Moore och Newman (2000:1)
för relaterade resultat.
Slutstorlek: Slutstorleken hos en Reed & Frost-epidemi på ett ”small-world”-nätverk
har bla studerats av Moore och Newman (2000:2). De analytiska resultaten är
dessvärre inte särskilt explicita och här nöjer vi oss med att presentera ett simule-
ringsresultat.
Givet en social graf och en smittsannolikhet p kan vi tunna ut grafen med san-
nolikhet 1 p, så att varje kant alltså lämnas kvar i grafen med sannolikhet p och
suddas ut med sannolikhet 1 p. Vi får då en smittgraf som representerar utfallet
av en Reed & Frost-epidemi: Epidemin kommer att drabba precis de individer som
tillhör samma komponent som den initialt smittade individen. I Figur 4 har d en
genomsnittliga storleken hos den största komponenten i en smittgraf baserad på ett
”small-world”-nätve rk plottats mot den lokala kontaktsannolikheten r (den globala
parametern bestäms av (3)). Detta ska tolkas som slutstorleken för den värsta
tänkbara epidemin initierad av en enda individ. Vi ser att komponenterna blir stör-
re då r avtar – dvs då andelen globala länkar ökar – och den största förändringen
sker just i intervallet r (0.8, 0.9) där ”small-world”-beteendet hos grafen sätter in.
deijfen.tex,v 1.11
136 Maria Deijfen Normat 3/2004
7 Avslutande kommentar
Avsikten med denna uppsats har varit att ge en inblick i stokastisk epidemimo-
dellering och att beskriva hur slumpgrafer kan använd as för att modellera social
struktur. Samtliga grafmodeller vi har tagit upp är behäftade med olika typer av
nackdelar: Bernoulligrafen har alltför låg transitivitet, triangelgrafen har en nå-
got orealistisk beroe nd estruktur, i Markovgrafen fördelas kanterna på ett mycket
onaturligt sätt och ”small-world”-nätverken är analytiskt svårhanterliga. Sökandet
efter god a modeller för sociala nätverk fortsätter!
Bibliografi
Andersson, H. (1999): Epidemic models and social networks, The mathematical scientist
24, 128–147.
Andersson, H. och Britton, T. (2000): Stochastic Epidemic models and their statistical
analysis, Springer.
Deijfen M. (2000): Epidemics on soci al network graphs, Examensarbete 2000:1,
Stockholms Universitet.
Milgram, S. (1967): The small world problem, Psychology Today 2, 60–67.
Moore, C. och Newman, M. (2000:1): Epidemics and percolation in small-world
networks, Phys. Rev. E 61, 5678–5682.
Moore, C. och Newman, M. (2000:2): Exact solution of site and bond percolation on
small-world networks, Phys. Rev. E 62, 7059–7064.
Strauss, D. (1985): On a general class of model s for interaction, SIAM Review 28,
513–527.
Strogatz, S. och Watts, D. (1998): Collective dynamics of small-world networks, Letters
to Nature 393, 440–442.
deijfen.tex,v 1.11
