Vi studerar utformningen av lokala algoritmer för massiva grafer. En lokal algoritm är en som hittar en lösning som innehåller eller nära en given vertex utan att titta på hela grafen. Vi presenterar en lokal klusteralgoritm. Vår algoritm finner en bra kluster-en delmängd av hörn vars interna anslutningar är betydligt rikare än dess externa anslutningar nära en given vertex. Tiden för vår algoritm, när den hittar ett lokalt kluster som inte är tomt, är nästan linjär i storleken på det kluster som den producerar. Vår klusteralgoritm kan vara en användbar primitiv för hantering av massiva grafer, såsom sociala nätverk och webbgrafer. Som en tillämpning av denna kluster algoritm, presenterar vi en partitionering algoritm som finner en ungefärlig glesaste snitt med nästan optimal balans. Vår algoritm tar tid nästan linjär i talkanterna på grafen. Med hjälp av partitioneringsalgoritmen i det här pappret har vi konstruerat en nästan linjär tidsalgoritm för att konstruera spektrala sparifierare av grafer, som vi i sin tur använder i en nästan linjär tidsalgoritm för att lösa linjära system i symmetriska, diagonalt dominerande matriser. Den linjära systemlösaren leder också till en nästan linjär tidsalgoritm för approximering av det näst minsta eigenvärdet och motsvarande eigenvektor för den laplaciska matrisen i en graf. Dessa andra resultat presenteras i två följedokument. * Detta papper är den första i en sekvens av tre papper expanderar på material som dök först under titeln "Nära-linjära tid algoritmer för graf partitionering, graf sparifiering, och lösa linjära system" [ST03]. Den andra tidningen, "Spectral Sparsification of Graphs" [ST08b] innehåller ytterligare resultat på partitionering grafer, och tillämpar dem för att producera spektral sparifierare av grafer. Den tredje tidningen, "Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems" [ST08a] innehåller resultaten på att lösa linjära ekvationer och att approximera eigen values och eigenvectors.
Vissa diagram partitionering algoritmer REF partition grafen för att minimera dess ledning.
A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}