Vi ser över det klassiska problemet med att uppskatta gradfördelningsmomenten i en oriktad graf. Betrakta en oriktad graf G = (V, E) med n (icke-isolerade) hörn, och definiera (för Vårt mål är att uppskatta μs inom en multiplikativ fel (1 + ε) (för en given approximation parameter ε > 0) i sublinjär tid. Vi anser den glesa grafen modell som ger tillgång till: enhetliga slumpmässiga hörn, frågor till graden av någon vertex, och frågor till en slumpmässig granne av någon vertex. Feige (SICOMP 06) och Goldreich-Ron (RSA 08) visade sig vara gränsen för s = 1 fall (genomsnittsnivån). Gonen-Ron-Shavitt (SIDMA 11) utökade detta resultat till alla integral s > 0, genom att utforma en O(n 1‐1/(s+1) algoritm. (Svårt talat, deras algoritm approximerar antalet star-subgraphs av en given storlek, men en liten ändring ger en algoritm för ögonblick.) Vi utformar en ny, betydligt enklare algoritm för detta problem. I värsta fall stämmer det exakt överens med Gonen-Ron-Shavitts gränser och har ett mycket enklare bevis. Ännu viktigare, körtiden för denna algoritm är ansluten till Arboricity av G: det minsta antalet skogar som E kan delas in i. För familjen av grafer med arboricity som mest α, det har en frågekomplex av Således, för klassen av avgränsade arboricity grafer (som inkluderar planar grafer, alla mindre slutna familjer, och preferensbilaga grafer), kan vi uppskatta den genomsnittliga graden i O(1) frågor, och kan uppskatta variansen av graden fördelningen i O( ε n) frågor. Detta är en stor förbättring jämfört med de tidigare värsta fallgränserna. Vår nyckelinsikt är att en viss estimator för μs har betydligt mindre varians när G inte har stora täta subgrafer.
Eden m.fl. föreslog en algoritm för att uppskatta den genomsnittliga graden med hjälp av Õ(1) frågor REF.
Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
{'venue': 'SIAM J. Discrete Math.', 'journal': 'SIAM J. Discrete Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}