På senare tid har stora datamängder som lagras på Internet gjort det möjligt att analysera processer, t.ex. storskalig spridning av information, på nya detaljnivåer. I en nyligen genomförd studie konstaterade Liben-Nowell och Kleinberg [(2008) Proc Natl Acad Sci USA 105:4633-4638] att informationsflödet på Internet uppvisar överraskande mönster där ett kedjebrev når sin typiska mottagare genom långa vägar av hundratals mellanhänder. Vi visar att en grundläggande Galton-Watson-epidemimodell kombinerad med urvalsfördelen att observera endast stora diffusioner räcker för att förklara dessa mönster. Således kan urvalsfördomar av vilka data vi observerar radikalt ändra uppskattningen av klassiska diffusionsprocesser. diameter -kedjebokstäver - Galton-Watson process - maximal sannolikhet uppskattning -sociala nätverk A s sociala nätverk data blir allt mer tillgängliga i elektronisk form, forskare håller på att utveckla mer detaljerade och exakta bilder av mönster av sociala interaktioner. Dessa empiriska undersökningar är av största vikt med tanke på de många sätt på vilka sociala nätverk påverkar våra liv (1). Men sådana data kommer med sina egna idiosynkrasier. Framför allt har tidigare de flesta uppgifterna om sociala nätverk erhållits via frågeformulär (2), intervjuer (3), experiment (4) eller observationer direkt gjorda av forskare (5), och därför valde forskaren uppgifterna. På senare tid har tillgången till elektroniska data gjort det vanligare att uppgifterna väljer forskare. Det vill säga, ofta blir stora och intressanta dataset tillgängliga på grund av den elektroniska lagringen av olika former av interaktion som sker via Internet, och dessa blir sedan användbara testbäddar för teorier om sociala nätverk. I detta dokument fokuserar vi på den förklarande kraften hos en inneboende valfördomar som kommer tillsammans med många sådana datauppsättningar. Särskilt undersöker vi en urvalsfördomar som uppstår genom att titta på ovanligt stora fall av diffusionsprocesser-med en särskild tillämpning på Internet kedjebokstäver. Liben-Nowell och Kleinberg gav i en nyligen publicerad artikel (6) en viktig och intressant undersökning av två kedjebrev som hade stor spridning på Internet: en framställning till stöd för offentlig radio och TV som började cirkulera 1995 och en framställning mot det slutliga kriget i Irak som spreds 2002 och 2003. Genom att få många kopior av e-posten och spårningen genom de beställda listorna över namn som lagts till varje petition, Liben-Nowell och Kleinberg kunde rekonstruera stora delar av träden för spridning av dessa kedjebokstäver. Den anmärkningsvärda aspekten av Liben-Nowell och Kleinbergs upptäckter är att dessa träd inte uppvisar de korta avstånden mellan noder som är karakteristiska för många sociala nätverk (7, 8). I stället har dessa träd mycket små bredder (dvs. många noder har en enda avkomma), och mediannoden får bokstaven efter det har varit genom hundratals mellanhänder. För att förstå varför den spridning av kedjebrev som Liben-Nowell och Kleinberg rekonstruerar är förbryllande, låt oss diskutera vad som verkar vara den mest naturliga och enkla modellen för hur en sådan process skulle fungera. Denna modell är den klassiska en av Galton och Watson (9), som utvecklades på 1870-talet för att studera livslängden av familjenamn i ett patrilineal system. Galton och Watson föreslog en förgreningsprocess där varje nod har ett slumpmässigt antal barn, ritade oberoende enligt samma fördelning. Processen kan också fungera som en modell för en epidemi, där antalet barn är antalet andra en given nod infekterar. I denna ansökan är antalet barn till en viss avsändare det antal andra personer som undertecknar framställningen omedelbart nedanför avsändarens underskrift i olika versioner av brevet som förgrenas som olika mottagare undertecknar. Det är välkänt (10) att den nyckelmängd som kännetecknar denna processs asymptotiska egenskaper är det förväntade antalet barn per nod. Om denna kvantitet ligger under enhetströskeln, då kallas processen subkritisk och med sannolikhet kommer den att sluta i utplåning efter ett begränsat antal steg. Om det förväntade antalet barn är mer än ett, då processen kallas superkritisk och kommer att fortsätta för evigt med positiv sannolikhet. (Vi ignorerar det icke-generiska gränsfall där varje nod har exakt ett barn i förväntan.) Mysteriet är att ingen av ordningarna tycks förklara de observerade uppgifterna. De två datauppsättningar som Liben-Nowell och Kleinberg studien har mer än 10 000 noder vardera, medan det är ganska ovanligt att en subkritisk förgreningsprocess med rimliga parametrar har mer än ett dussin noder. Således är det typiska subkritiska trädet en dålig matchning till data på många dimensioner. Å andra sidan, om man försöker att passa data med en superkritisk process, då de träd som uppstår har enorma bredder, gren mycket ofta, och inte har de långa kedjor som observeras i data. Liben-Nowell och Kleinberg utvecklade därför en rikare nätverksbaserad modell för distribution av kedjebrev med två viktiga funktioner: asynkron responstid och gruppsvar. De insikter om deras process som är lika stora som de observerade diffusionerna har de rätta formerna. Vi visar att trots deras överraskande utseende har de observerade träden en global struktur som motsvarar en grundläggande och klassisk process. I synnerhet den enkla Galton-Watson epidemimodellen räcker för att generera träd som når många noder men ändå har långa kedjor som i data. För att visa detta passar vi först in på parametrarna i en Galton-Watson process genom att använda maxlikelihood uppskattning på grundval av ett av de träd som härleds av Liben-Nowell och Kleinberg. Sedan simulerar vi processen och undersöker endast de sällsynta utfall där en kedjebokstäv med dessa parametrar sprider sig lika brett som de som observerades. De flesta insikter är mycket små och har praktiskt taget ingen chans att observeras; vi är intresserade av egenskaperna hos de sällsynta som är tillräckligt stora för att matcha de offentliga radio- och krigsframställningar som beskrivs ovan. Simulerade resultat från denna villkorade fördelning stämmer väl överens med de verkliga observationerna av globala dimensioner som träddjup, bredd och fördelning av barn per nod. Den skenbara hinder diskuteras ovan - att ingen av
I REF föreslås en enkel förgreningsprocess (Galton-Watson-processen) för modellering av kedjebokstäverskaskader.
Using selection bias to explain the observed structure of Internet diffusions
{'venue': 'Proceedings of the National Academy of Sciences of the United States of America', 'journal': 'Proceedings of the National Academy of Sciences of the United States of America', 'mag_field_of_study': ['Medicine', 'Computer Science']}