Identifieringen av kluster, väl anslutna komponenter i en graf, är användbar i många tillämpningar från biologisk funktionsförutsägelse till social community upptäckt. Det kan dock vara svårt att hitta dessa kluster när grafstorlekarna ökar. De flesta nuvarande graf kluster algoritmer skala dåligt i termer av tid eller minne. En viktig insikt är att många klustertillämpningar bara behöver delmängd av bästa kluster, och inte alla kluster i hela grafen. I detta papper föreslår vi en ny teknik, Top Graph Clusters (TopGC), som probabilistiskt söker stora, kantviktade, riktade grafer för sina bästa kluster i linjär tid. Algoritmen är i sig parallelliserbar, och kan hitta variabel storlek, överlappande kluster. För att öka skalbarheten införs en parameter som styr minnesanvändningen. Jämfört med tre andra toppmoderna klustertekniker uppnår TopGC snabbare drifttider på upp till 70 % på storskaliga realtidsdatauppsättningar. Dessutom är de kluster som TopGC returnerat konsekvent att vara bättre både i beräknade poäng och när det jämförs på verkliga riktmärken.
TopGC REF är en snabb algoritm för att probabilistiskt söka stora, kantviktade, riktade grafer för sina bästa kluster i linjär tid.
Scalable Discovery of Best Clusters on Large Graphs
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}