Många nätnät är inte helt kända och studeras ofta via provtagning. Random Walk (RW) baserade tekniker är den nuvarande state-of-the-art för att uppskatta nodal attribut och lokala graf egenskaper, men uppskattning av globala egenskaper är fortfarande en utmaning. I detta papper är vi intresserade av en grundläggande egenskap av denna typ - grafen storlek N, dvs antalet av dess noder. Befintliga metoder för att uppskatta N är i) ineffektiva och ii) kan inte lätt användas med RW-provtagning på grund av beroendet mellan på varandra följande prover. I detta dokument tar vi upp båda problemen. Först föreslår vi IE (Induced Edges), en effektiv teknik för att uppskatta N från ett oberoende prov av grafens noder. IE utnyttjar de kanter som induceras på de provade noderna. För det andra introducerar vi SafetyMargin, en metod som korrigerar estimatorer för beroende i RW prover. Slutligen kombinerar vi dessa två fristående tekniker för att få en RW-baserad grafstorleksskattning. Vi utvärderar vår strategi i simuleringar på ett brett spektrum av verkliga topologier, och på flera prover av Facebook. IE med SafetyMargin kräver normalt minst 10 gånger färre prover än de senaste teknikerna (över 100 gånger i fallet Facebook) för samma skattningsfel.
På senare tid har tillämpningar för sociala nätverk skapat intresse för att utveckla metoder för att uppskatta antalet noder i grafer baserat på en del urval av graferna; den intresserade läsaren kan hänvisa till REF och referenser där.
Graph Size Estimation
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Physics', 'Mathematics']}