Detektion av gemenskapen används ofta för att förstå de stora och komplexa nätens struktur. En av de mest populära algoritmerna för att avslöja samhällsstruktur är den så kallade Louvain algoritmen. Vi visar att denna algoritm har en stor defekt som till stor del gick obemärkt fram till nu: Louvain algoritmen kan ge godtyckligt dåligt anslutna samhällen. I värsta fall kan grupper till och med kopplas bort, särskilt när algoritmen körs iterativt. I vår experimentella analys konstaterar vi att upp till 25 procent av samhällena är dåligt sammankopplade och upp till 16 procent är urkopplade. Detta kan leda till allvarliga problem vid efterföljande analyser. För att ta itu med problemet introducerar vi Leiden-algoritmen. Vi bevisar att Leiden algoritm ger samhällen som garanterat är anslutna. Dessutom bevisar vi att när Leiden algoritmen tillämpas iterativt, konvergerar den till en partition där alla undergrupper av alla samhällen är lokalt optimalt tilldelade. Dessutom, genom att förlita sig på en snabb lokal flytta tillvägagångssätt, Leiden algoritm körs snabbare än Louvain algoritm. Vi demonstrerar prestandan av Leiden algoritmen för flera riktmärken och verkliga nätverk. Vi finner att Leiden algoritm är snabbare än Louvain algoritm och avslöjar bättre partitioner, förutom att ge uttryckliga garantier. Baserat på våra resultat drar vi slutsatsen att Leiden-algoritmen är att föredra framför Louvain-algoritmen.
För att ta itu med detta problem föreslogs en ny Leidenalgoritm, som är snabbare än Louvain och upptäcker bättre partitioner REF.
From Louvain to Leiden: guaranteeing well-connected communities
{'venue': 'Scientific Reports, vol. (9): 5233 (2019)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Medicine', 'Physics']}