Grafkluster är en av de viktigaste teknikerna för att förstå de strukturer som finns i grafer. Förutom detektering av kluster är det också en viktig uppgift att identifiera knutpunkter och avvikelser, eftersom de har viktiga roller att spela i grafdatautvinning. Den strukturella klusteralgoritm SCAN, som föreslås av Xu et al., används framgångsrikt i många tillämpningar eftersom den inte bara upptäcker tätt anslutna noder som kluster utan också identifierar glest anslutna noder som nav eller yttre. Det är dock svårt att tillämpa SCAN på storskaliga grafer på grund av dess höga tids komplexitet. Detta beror på att det utvärderar densiteten för alla angränsande noder som ingår i de givna graferna. I det här dokumentet föreslår vi en ny grafklusteralgoritm som heter SCAN++. För att minska tids komplexiteten introducerar vi ny datastruktur för direkt två-hop-away nåbar nod uppsättning (Dtar). DTAR är uppsättningen av två-hop-away noder från en given nod som sannolikt kommer att vara i samma kluster som den givna noden. SCAN++ använder två metoder för effektiv klusterbildning genom att använda DTAR utan att offra klusterkvalitet. För det första minskar det antalet densitetsutvärderingar genom att beräkna densiteten endast för angränsande noder såsom anges av DTARs. För det andra, genom att dela en del av densitetsutvärderingarna för DTAR, erbjuder den effektiva densitetsutvärderingar av angränsande noder. Som ett resultat av detta upptäcker SCAN++ exakt samma kluster, nav och avvikelser från storskaliga grafer som SCAN med mycket kortare beräkningstid. Omfattande experiment på både verkliga och syntetiska grafer visar prestanda överlägsenheten hos SCAN++ jämfört med befintliga metoder.
För att lindra detta problem föreslår REF en algoritm som heter SCAN++.
SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}