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 om graden av någon vertex, och frågor för en granne till någon vertex. För s = 1 (genomsnittlig grad) räcker det med O( ε n)-frågor för varje konstant ε (Feige, SICOMP 06 och Goldreich-Ron, RSA 08). Gonen-Ron-Shavitt (SIDMA 11) utökade detta resultat till alla integral s > 0, genom att utforma en algoritm som utför O(n 1-1/(s+1) frågor. (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 degeneracy av G. Detta är (i huvudsak) den maximala densiteten av en inducerad subgraf. För familjen av grafer med degeneracy som mest α, det har en fråga komplexitet av Således, för klassen av avgränsade degeneracy grafer (som inkluderar alla mindre slutna familjer och preferensbilagor), kan vi uppskatta den genomsnittliga graden i O(1) frågor, och kan uppskatta variationen i 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 i att utforma en uppskattning för μs som har låg varians när G inte har stora täta subgrafer.
Betydelsen av avgränsad degeneracy har ytterligare undersökts i samband med uppskattningen av grad ögonblick REF i denna modell.
Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection
{'venue': None, 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}