Abstrakt. En distribuerad algoritm utför lokala beräkningar på indatabitar och kommunicerar resultaten via givna kommunikationslänkar. Vid bearbetning av en massiv graf i en distribuerad algoritm måste lokala utgångar konfigureras som en lösning på ett grafproblem utan delat minne och med några kommunikationsrundor. I det här dokumentet ser vi problemet med att beräkna ett lokalt kluster i en massiv graf i den distribuerade inställningen. De lokala datorklustren har vissa tillämpningsspecifika intressen, till exempel att upptäcka samhällen i sociala nätverk eller grupper av samverkande proteiner i biologiska nätverk. När grafen modellerar själva datornätet, att upptäcka lokala kluster kan bidra till att förhindra kommunikationsflaskhalsar. Vi ger en distribuerad algoritm som beräknar ett lokalt kluster i tiden som endast beror logaritmiskt på storleken på grafen i CONGEST-modellen. I synnerhet, när ledning av den optimala lokala kluster är känd, algoritmen körs i tid helt oberoende av storleken på grafen och beror endast på felgränser för approximation. Vi visar också att det lokala klusterproblemet kan beräknas i k-maskinen distribuerad modell i sublinjär tid. Hastigheten i våra lokala klusteralgoritmer beror främst på användningen av vår distribuerade algoritm för värmekärnan sidarank.
Nyligen presenterar arbetet med REF distribuerade algoritmer för att beräkna lokala kluster i k-maskinmodellen.
Distributed Algorithms for Finding Local Clusters Using Heat Kernel Pagerank
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}