Forskare har föreslagit en mängd olika mått för att mäta viktiga grafegenskaper, till exempel i sociala, biologiska och datornätverk. Värden för en viss graf metriska kan fånga en grafs motståndskraft mot fel eller dess routing effektivitet. Kunskap om lämpliga metriska värden kan påverka designen av framtida topologier, reparationsstrategier inför misslyckanden och förståelse av grundläggande egenskaper hos befintliga nätverk. Tyvärr finns det vanligtvis inga algoritmer för att generera grafer som matchar en eller flera föreslagna mätvärden och det finns liten förståelse för sambanden mellan individuella mätvärden eller deras tillämplighet på olika inställningar. Vi presenterar ett nytt systematiskt tillvägagångssätt för att analysera nätverkstopologier. Vi introducerar först dK-serien av sannolikhetsfördelningar som specificerar alla grad korrelationer inom d-stora subgrafer i en given graf G. Ökande värden av d fånga gradvis fler egenskaper hos G på bekostnad av mer komplex representation av sannolikhetsfördelningen. Med hjälp av denna serie kan vi kvantitativt mäta avståndet mellan två grafer och konstruera slumpmässiga grafer som exakt reproducerar praktiskt taget alla mätvärden som föreslås i litteraturen. DK-seriens karaktär innebär att den också kommer att fånga upp eventuella framtida mätvärden som kan komma att föreslås. Med vårt tillvägagångssätt konstruerar vi grafer för d = 0, 1, 2, 3 och visar att dessa grafer reproducerar, med ökande noggrannhet, viktiga egenskaper hos uppmätta och modellerade Internet topologier. Vi finner att d = 2 fallet är tillräckligt för de flesta praktiska ändamål, medan d = 3 väsentligen rekonstruerar Internet AS-och router-nivå topologier exakt. Vi hoppas att en systematisk metod för att analysera och syntetisera topologier erbjuder en betydande förbättring av den uppsättning verktyg som finns tillgängliga för att nätverka topologi och protokollforskare.
Vi antar den systematiska ramen för dK-serien REF, som infördes för att karakterisera egenskaperna hos en oriktad graf med hjälp av en serie sannolikhetsfördelningar som specificerar alla grad korrelationer inom d-storlek, enkel, och anslutna subgrafer av en given graf G. I detta ramverk, högre värden av d fånga gradvis fler egenskaper hos G på bekostnad av mer komplex representation av sannolikhetsfördelningen.
Systematic Topology Analysis and Generation Using Degree Correlations
{'venue': 'SIGCOMM 2006 (ACM SIGCOMM Computer Communication Review (CCR), v.36, n.4, p.135-146, 2006)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}