I detta dokument introducerar vi en ny, allmän metod för snabbare provtagning av noder över ett socialt nätverk på nätet. Till skillnad från traditionell slumpmässig gång som väntar på konvergens av provtagning distribution till en förutbestämd målfördelning - en väntande process som ådrar sig en hög frågekostnad - utvecklar vi WALK-ESTIMATE, som börjar med en mycket kortare slumpmässig gång, och sedan proaktivt uppskatta provtagnings sannolikheten för noden tas innan man använder acceptans-avvisning provtagning för att justera provtagnings sannolikheten till den förutbestämda målfördelningen. Vi presenterar en ny bakåtvänd slumpmässig gångteknik som ger bevisligen opartiska uppskattningar för provtagningsannolikheten, och visar WALK-ESTIMATEs överlägsenhet över traditionella slumpmässiga promenader genom teoretisk analys och omfattande experiment över verkliga online sociala nätverk.
Walk-skattning som föreslås i REF syftade till att minska overhead-in-perioden genom att överväga korta slumpmässiga promenader och sedan använda acceptans-avvisningsprov för att justera provtagnings sannolikheten för en nod med avseende på dess stationära fördelning.
Walk, Not Wait: Faster Sampling Over Online Social Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Physics']}