Vi studerar problemet med att tillnärma antalet k-kluster i en graf när det ges frågeåtkomst till grafen. Vi anser att standard frågemodell för allmänna grafer via (1) examensförfrågningar, (2) grannförfrågningar och (3) parförfrågningar. Låt n betecknar antalet hörn i grafen, m antalet kanter, och C k antalet k- cliques. Vi designar en algoritm som ger en (1 + ε ) - approximation (med hög sannolikhet) för C k, vars förväntade frågekomplexitet och Därför, komplexiteten i algoritmen är sublinear i storleken på grafen för C k =  på (m k /2−1 ). Dessutom är frågekomplexiteten hos vår algoritm i huvudsak optimal (upp till beroendet av log n, 1/ε och k). De tidigare resultaten i denna ven är av Feige (SICOMP 06) och av Goldreich och Ron (RSA 08) för kanträkning (k = 2) och av Eden et al. (FOCS 2015) för triangelräkning (k = 3). Vårt resultat matchar komplexiteten i dessa resultat. Det tidigare resultatet av Eden m.fl. beror på en viss avskrivningar teknik som fungerar för triangelräkning, och inte generaliserar till alla k. Vi får en allmän algoritm som fungerar för någon k ≥ 3 genom att utforma en procedur som tar prov varje k-clique incident till en given uppsättning S hörn med ungefär lika stor sannolikhet. Den primära svårigheten är att hitta kliquer incident till rent hög grad hörn, eftersom slumpmässig provtagning inom grannar har en låg framgång sannolikhet. Detta uppnås genom en algoritm som provar enhetliga slumpmässiga höggradiga hörn och en noggrann avvägning mellan uppskattande kliquer incident enbart till höggradiga hörn och de som inkluderar en låggradig vertex.
Deras resultat generaliserades av Eden m.fl. Vid hänvisning till approximering av antalet k-kluster för varje k ≥ 3.
On approximating the number of k-cliques in sublinear time
{'venue': 'STOC 2018', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}