Detektion av gemenskapen har blivit en grundläggande funktion i många grafteoretiska tillämpningar. Det används för att avslöja naturliga uppdelningar som finns inom verkliga nätverk utan att påtvinga tidigare storlek eller kardinalitet begränsningar på grupper av samhällen. Trots dess potential för tillämpning finns det endast begränsat stöd för detektering av samhället på storskaliga parallella datorer, till stor del på grund av den oregelbundna och inneboende sekventiella karaktären hos de underliggande heuristikerna. I detta papper presenterar vi parallellisering heuristik för snabb community detektion med hjälp av Louvain metoden som seriell mall. Louvainmetoden är en iterativ heuristisk metod för modularitetsoptimering. Ursprungligen utvecklat av Blondel et al. Under 2008 har metoden blivit alltmer populär på grund av sin förmåga att upptäcka hög moduläritet gemenskap partitioner på ett snabbt och minneseffektivt sätt. Metoden är dock också i sig sekventiell, vilket begränsar skalbarheten. Här observerar vi vissa nyckelegenskaper hos denna metod som innebär utmaningar för dess parallellisering, och föreslår därför heuristik som är utformade för att bryta den sekventiella barriären. För utvärderingsändamål implementerade vi våra heuristiker med OpenMP multithreading och testade dem över verkliga grafer från flera applikationsområden (t.ex. internet, citering, biologisk). Jämfört med den serie Louvain implementering, vår parallella implementation kan producera community outputs med en högre moduläritet för de flesta av de ingångar testade, i jämförbart antal iterationer, samtidigt som den ger verkliga upphastigheter på upp till 8× med 32 trådar. Dessutom kunde vårt parallella genomförande uppvisa svaga skalegenskaper på upp till 32 trådar.
I REF föreslår författarna en parallell version av Louvainmetoden, som uppnår en hastighetsökning på 16x med 32 trådar.
Parallel Heuristics for Scalable Community Detection
{'venue': '2014 IEEE International Parallel & Distributed Processing Symposium Workshops', 'journal': '2014 IEEE International Parallel & Distributed Processing Symposium Workshops', 'mag_field_of_study': ['Computer Science', 'Physics']}