Nätverken har under senare år framträtt som ett ovärderligt verktyg för att beskriva och kvantifiera komplexa system inom många vetenskapsområden [1, 2, 3]. Nya studier tyder på att nätverk ofta uppvisar hierarkisk organisation, där hörn delar upp sig i grupper som ytterligare delar upp sig i grupper och så vidare över flera skalor. I många fall anses dessa grupper motsvara kända funktionella enheter, såsom ekologiska nischer i matnät, moduler i biokemiska nätverk (proteininteraktionsnätverk, metaboliska nätverk eller genetiska regleringsnät), eller samhällen i sociala nätverk [4, 5, 6, 7]. Här presenterar vi en allmän teknik för att härleda hierarkisk struktur från nätverksdata och visa att förekomsten av hierarki samtidigt kan förklara och kvantitativt reproducera många vanliga observerade topologiska egenskaper hos nätverk, såsom högerstyrda gradfördelningar, höga klusterkoefficienter och korta väglängder. Vi visar vidare att kunskap om hierarkisk struktur kan användas för att förutsäga saknade anslutningar i delvis kända nätverk med hög noggrannhet, och för mer allmänna nätverksstrukturer än konkurrerande tekniker [8]. Sammantaget tyder våra resultat på att hierarkin är en central organisationsprincip för komplexa nätverk, som kan erbjuda insikt i många nätverksfenomen. En stor del av det senaste arbetet har ägnats åt studier av klusterbildning och samhällsstruktur i nätverk [5, 6, 9, 10, 11]. Hierarkisk struktur går dock utöver enkel klusterbildning genom att uttryckligen inkludera organisation på alla skalor i ett nätverk samtidigt. Konventionellt representeras hierarkisk struktur av ett träd eller dendrogram i vilket nära besläktade par hörn har lägst vanliga förfäder som är lägre i trädet än de av mer avlägset besläktade par-se bild. 1................................................................ Vi förväntar oss att sannolikheten för ett samband mellan två hörn beror på deras grad av släktskap. Struktur av denna typ kan modelleras matematiskt med en probabilistisk metod där vi ger varje intern nod r av dendrogram med en sannolikhet p r och sedan ansluta varje par hörn för vilka r är den lägsta gemensamma förfadern oberoende med sannolikhet p r (Fig. 1).................................................................. Denna modell, som vi kallar en hierarkisk slumpmässig graf, liknar i andemening (även om den skiljer sig från verkligheten) de trädbaserade modeller som används i vissa studier av nätverkssökning och navigering [12, 13]. Liksom de flesta arbeten på samhällsstruktur, det * Denna uppsats publicerades som Natur 453, 98 -101 (2008); doi:10.1038/naturen06830. antar att samhällen på varje organisationsnivå är osammanhängande. Överlappande samhällen har ibland studerats (se t.ex. [14] ) och kan representeras med hjälp av en mer genomtänkt probabilistisk modell, men som vi diskuterar nedan fångar den nuvarande modellen redan många av de strukturella särdragen i intresse. Med tanke på ett dendrogram och en uppsättning sannolikheter p r, ger den hierarkiska slumpmässiga grafmodellen oss möjlighet att skapa artificiella nätverk med en specificerad hierarkisk struktur, ett förfarande som kan vara användbart i vissa situationer. Vårt mål här är dock ett annat. Vi skulle vilja upptäcka och analysera den hierarkiska strukturen, om någon, av nätverk i den verkliga världen. Vi åstadkommer detta genom att montera den hierarkiska modellen till observerade nätverksdata med hjälp av verktygen för statistisk inferens, kombinera en maximal sannolikhet att närma sig möjliga dendrograms. Denna teknik gör det möjligt för oss att prova hierarkiska slumpmässiga grafer med sannolikhet proportionell mot sannolikheten att de genererar det observerade nätverket. För att få de resultat som beskrivs nedan kombinerar vi information från ett stort antal sådana prover, som vart och ett är en rimligen trolig modell av data. Framgången med detta tillvägagångssätt bygger på att vår hierarkiska modell är flexibel, vilket gör att vi kan anpassa oss till ett brett spektrum av nätverksstrukturer. Den traditionella bilden av samhällen eller moduler i ett nätverk, till exempel, motsvarar kopplingar som är täta inom grupper av hörn och glest mellan dem-ett beteende som kallas "assortativitet" i litteraturen [17]. Den hierarkiska slumpmässiga grafen kan fånga beteende av detta slag med sannolikheter p r som minskar när vi flyttar högre upp i trädet. Omvänt, sannolikheter som ökar när vi flyttar upp trädet motsvarar "disassortativa" strukturer där hörn är mindre benägna att anslutas på små skalor än på stora. Genom att låta p r-värdena variera godtyckligt i hela dendrogrammet, kan den hierarkiska slumpmässiga grafen fånga både diverse och disassortativa strukturer, liksom godtyckliga blandningar av de två, på alla skalor och i alla delar av nätverket. För att visa vår metod har vi använt den för att konstruera hierarkiska nedbrytningar av tre exempelnätverk som hämtats från olika fält: det metaboliska nätverket av spirochete Treponema pallidum [18], ett nätverk av associationer mellan terrorister [19], och ett livsmedelsnät av gräsmarksarter [20]. För att testa om dessa nedbrytningar exakt fångar upp nätens viktiga strukturella egenskaper använder vi de provtagna dendrogram för att generera nya nätverk, som skiljer sig i detalj från originalen, men per definition har liknande hierarkisk struktur (se Kompletterande information för mer information). Vi finner att dessa "replikerade" nätverk matchar de statistiska egenskaperna hos originalen nära, inklusive deras gradfördelningar, klustereringskoefficienter, och fördelningar av kortaste väglängder mellan par av hörn, trots det faktum att ingen av dessa egenskaper uttryckligen representeras i den hierarkiska slumpmässiga grafen (Tabell I, och Bild. S3 i tilläggsinformationen). Det verkar alltså som om ett näts hierarkiska struktur också kan förklara en mängd andra nätverksfunktioner. De dendrogram som produceras genom vår metod är också av intresse för sig själva, som en grafisk representation och sammanfattning av det observerade nätverkets hierarkiska struktur. Som dis-. Observera att i flera fall grupperas en uppsättning parasitoider i en disassortativ gemenskap av algoritmen, inte för att de lever på varandra, utan för att de lever på samma växtätare. Enligt ovan kan vår metod generera inte bara ett enda dendrogram utan en uppsättning dendrogram, som var och en passar bra till datan. Från denna uppsättning kan vi, med hjälp av tekniker från phylogeny rekonstruktion [21], skapa en enda konsensus dendrogram, som fångar de topologiska egenskaper som visas konsekvent över alla eller en stor del av dendrograms och typiskt representerar en bättre sammanfattning av nätverkets struktur än någon enskild dendrogram. Figur 2a visar ett sådant samförstånd dendrogram för nätverket av gräsmarksarter, som tydligt avslöjar samhällen och subkommuniteter av växter, växtätare, parasitoider och hyperparasitoider. En annan tillämpning av den hierarkiska nedbrytningen är förutsägelsen om saknade interaktioner i nätverk. I många miljöer kräver upptäckten av interaktioner i ett nätverk betydande experimentella insatser i laboratoriet eller fältet. Som ett resultat av detta är våra nuvarande bilder av många nätverk sub-3 starkt ofullständiga [22, 23, 24, 25, 26, 27, 28]. Ett attraktivt alternativ till att kontrollera uttömmande för en anslutning mellan varje par hörn i ett nätverk är att försöka förutsäga, i förväg och baserat på de anslutningar som redan observerats, vilka hörn är mest sannolikt att vara anslutna, så att knappa experimentella resurser kan fokuseras på testning för dessa interaktioner. Om våra förutsägelser är goda kan vi på detta sätt avsevärt minska de ansträngningar som krävs för att etablera nätverkets topologi. Den hierarkiska nedbrytningen kan användas som grund för en effektiv metod för att förutsäga saknade interaktioner enligt följande. Med tanke på ett observerat men ofullständigt nätverk, genererar vi som beskrivs ovan en uppsättning hierarkiska slumpmässiga grafsdendrogram och tillhörande sannolikheter p r -som passar det nätverket. Sedan letar vi efter par av hörn som har en hög genomsnittlig sannolikhet för anslutning inom dessa hierarkiska slumpmässiga grafer men som inte är anslutna i det observerade nätverket. Dessa par vi anser de mest sannolika kandidater för saknade anslutningar. (Tekniska uppgifter om förfarandet finns i den kompletterande informationen.) Vi demonstrerar metoden med hjälp av våra tre exempelnätverk igen. För varje nätverk tar vi bort en delmängd av anslutningar som väljs jämnt på måfå och försöker sedan förutsäga, baserat på de återstående anslutningar, vilka som har tagits bort. Ett standardmått för att kvantifiera noggrannheten av förutsägelsealgoritmer, som vanligen används i medicinska och maskininlärning samhällen, är AUC-statistiken, som är likvärdig med området under mottagaren-operativa egenskapen (ROC) kurva [29]. I det aktuella sammanhanget kan AUC-statistiken tolkas som sannolikheten att en slumpmässigt vald saknad anslutning (ett sant positivt) ges en högre poäng genom vår metod än ett slumpmässigt valt par osammanhängande hörn (ett sant negativt). Den grad i vilken AUC överstiger 1/2 indikerar alltså hur mycket bättre våra förutsägelser är än slumpen. Figur 3 visar AUC-statistiken för de tre nätverken som en funktion av fraktionen av de anslutningar som är kända för algoritmen. För alla tre nätverk gör vår algoritm mycket bättre än slumpen, vilket tyder på att hierarkin är en stark allmän prediktor för saknad struktur. Det är också lärorikt att jämföra prestanda av vår metod med andra metoder för länk förutsägelse [8]. Tidigare föreslagna metoder inkluderar antagandet att hörn sannolikt kommer att anslutas om de har många gemensamma grannar, om det finns korta vägar mellan dem, eller om produkten av deras grader är stor. Dessa strategier fungerar bra för starkt olika nätverk som samarbete och citeringsnätverk [8] och för de metabola och terroristiska nätverk som studeras här (Fig. 3a b)........................................................................................................... För det metabola nätverket fungerar den kortaste heuristiska vägen bättre än vår algoritm. Dessa enkla metoder kan dock vara vilseledande för nätverk som uppvisar mer allmänna typer av struktur. I födovävar, till exempel, delar par av rovdjur ofta bytesarter, men sällan på varandra. I sådana situationer skulle en vanlig granne eller en kortaste vägbaserad metod förutsäga samband mellan rovdjur där det inte finns några. Den hierarkiska modellen kan däremot uttrycka både olika och olika strukturer och som bild. 3c visar, ger betydligt bättre prognoser för gräsmarksnätet. (I- gärning, i Bild. 2b Det finns flera grupper av parasitoider som vår algoritm har grupperat tillsammans i en disassortativ gemenskap, där de lever på samma växtätare men inte på varandra.) Den hierarkiska metoden gör därför exakta förutsägelser för ett bredare spektrum av nätverksstrukturer än de tidigare metoderna. I applikationerna ovan har vi antagit för enkelhetens skull 4 att det inte finns några falska positiva i våra nätverksdata, d.v.s. att varje observerad kant motsvarar en verklig interaktion. I nätverk där falska positiva kan vara närvarande, kan de också förutsägas med samma tillvägagångssätt: vi skulle helt enkelt leta efter par av hörn som har en låg genomsnittlig sannolikhet för anslutning inom den hierarkiska slumpmässiga grafen men som är anslutna i det observerade nätverket. Den metod som beskrivs här skulle också kunna utvidgas till att omfatta domänspecifik information, såsom artmorfologiska eller beteendemässiga egenskaper för livsmedelsvävar [28] eller fylogenetiska eller bindningsdomändata för biokemiska nätverk [23], genom att justera sannolikheterna för kanter i enlighet därmed. Som resultaten ovan visar, kan vi dock få bra förutsägelser även i avsaknad av sådan information, vilket tyder på att topologi ensam kan ge rika insikter. Avslutningsvis konstaterar vi att vår strategi skiljer sig mycket från tidigare arbete om hierarkisk struktur i nätverk [1, 4, 5, 6, 7, 9, 11, 30] genom att den uttryckligen erkänner att de flesta verkliga nätverk har många rimliga hierarkiska representationer av ungefär lika stor sannolikhet. Tidigare arbete har däremot vanligtvis sökt en enda hierarkisk representation för ett visst nätverk. Genom att ta en ensemble av dendrogram undviker vårt tillvägagångssätt att överanstränga data och gör det möjligt för oss att förklara många gemensamma topologiska funktioner, generera omprovade nätverk med liknande struktur som originalet, härleda en tydlig och koncis sammanfattning av ett nätverks struktur via dess konsensus dendrogram, och exakt förutsäga saknade anslutningar i en mängd olika situationer.
En länk upptäckt förutsäger förekomsten av en okänd länk mellan två noder från informationen om de kända attributen för noderna och de kända länkarna REF ].
Hierarchical structure and the prediction of missing links in networks
{'venue': 'Nature 453, 98 - 101 (2008)', 'journal': None, 'mag_field_of_study': ['Biology', 'Mathematics', 'Physics', 'Medicine']}