Gemenskapens upptäckter i komplexa nätverk är ett intressant problem med ett antal tillämpningar, särskilt när det gäller kunskapsutvinning i sociala nätverk och informationsnätverk. Många stora nätverk saknar emellertid ofta en särskild samhällsorganisation på global nivå. I dessa fall, traditionella graf partitionering algoritmer misslyckas med att låta latent kunskap inbäddad i modulär struktur uppstår, eftersom de inför en top-down global vy av ett nätverk. Vi föreslår här en enkel lokal-första strategi för samhällets upptäckt, som kan presentera den modulära organisationen av verkliga komplexa nätverk. Detta uppnås genom att demokratiskt låta varje nod rösta på de samhällen som den ser omger den i sin begränsade syn på det globala systemet, d.v.s. dess ego grannskap, med hjälp av en etikettutbredningsalgoritm; slutligen, de lokala samhällena slås samman till en global samling. Vi testade denna intuition mot de toppmoderna överlappande och icke-överlappande metoderna för upptäckt i samhället, och fann att vår nya metod klart överträffar de andra i kvaliteten på de erhållna samhällena, utvärderade genom att använda de extraherade samhällena för att förutsäga metadata om noderna i flera verkliga nätverk. Vi visar också hur vår metod är deterministisk, helt inkrementell, och har en begränsad tids komplexitet, så att den kan användas på webbscale verkliga nätverk.
Den DEMON algoritm REF, till exempel, demokratiskt låter varje vertex rösta för de samhällen som den ser omger det i sin begränsade syn på det globala systemet med hjälp av en etikett utbredning algoritm, och sedan slår samman de lokala samhällena till en global samling.
DEMON: a Local-First Discovery Method for Overlapping Communities
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Physics', 'Mathematics']}