Vi studerar problemet med att känna igen klusterstrukturen i en graf inom ramen för egenskapstestning i den avgränsade examensmodellen. Med tanke på en parameter ε, en d-bundet grad graf definieras som (k,  och)-klusterbar, om den kan delas i högst k delar, så att (inre) ledning av den inducerade subgrafen på varje del är minst och (yttre) ledning av varje del är som mest c d,k ε 4  och 2, där c d,k beror endast på d, k. Vårt huvudresultat är en sublinjär algoritm med körtiden O( ε n · poly(∂, k, 1/ε)) som tar som inmatning en graf med maximal grad avgränsad av d, parametrar k, ∂, ε, och med sannolikhet minst 2 3, accepterar grafen om det är (k, ∂)-klusterbar och avvisar grafen om det är ε-långt från (k, )-klusterbar för ∂ * = c′ d,k ε 4 log n, där c′ d, där c är beroende av vår expansion, där k(t) bara är nödvändigt för att mäta med ett enda problem.
En algoritm för att testa klusterstrukturen av grafer har föreslagits i REF.
Testing Cluster Structure of Graphs
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}