Att uppskatta egenskaper hos stora grafer genom provtagning är en viktig del av studien av komplexa nätverk. Nuvarande provtagningsmetoder såsom (oberoende) slumpmässig vertex och slumpmässiga promenader är användbara men har nackdelar. Slumpmässig vertex provtagning kan kräva för många resurser (tid, bandbredd, eller pengar). Slumpmässiga promenader, som normalt kräver färre resurser per prov, kan lida av stora skattningsfel i närvaro av frånkopplade eller löst anslutna grafer. I detta arbete föreslår vi en ny m-dimensionell slumpmässig gång som använder m beroende slumpmässiga vandrare. Vi visar att den föreslagna provtagningsmetoden, som vi kallar Frontier Sample, uppvisar alla de fina provtagningsegenskaperna hos en vanlig slumpmässig gång. Samtidigt visar våra simuleringar över stora verkliga grafer att i närvaro av frånkopplade eller löst anslutna komponenter uppvisar Frontier-provtagning lägre skattningsfel än vanliga slumpmässiga promenader. Vi visar också att Frontier provtagning är mer lämplig än slumpmässig vertex provtagning för att provta svansen av graden fördelningen av grafen.
När det gäller nackdelarna med slumpmässiga promenader presenteras en flerdimensionell slumpmässig gång, kallad Frontier Sampling, i REF och författarna finner att detta tillvägagångssätt är lämpligare att provta svansen av gradfördelningen av grafen.
Estimating and sampling graphs with multidimensional random walks
{'venue': "IMC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}