Bakgrund/Purpose: Gemenskapspartition är av stor betydelse inom sociologi, biologi och datavetenskap. På grund av den exponentiellt ökande mängden sociala nätverkstillämpningar är en snabb och korrekt metod nödvändig för delning i sociala nätverk. Mot bakgrund av detta undersöker vi delningsproblemet i samhället ur ett perspektiv av inflytandeutbredning, vilket är ett av de viktigaste inslagen i den sociala kommunikationen. Vi formulerar partition i samhället som ett kombinatoriskt optimeringsproblem som syftar till att dela upp ett socialt nätverk i olika grupper i K så att summan av påverkansutbredning inom varje gemenskap maximeras. När K = 2 utvecklar vi en optimal algoritm som har en påvisbar prestandagaranti för en klass av påverkansutbredningsmodeller. För general K bevisar vi att det är N P-hard att hitta en maximal partition för sociala nätverk i den välkända linjära tröskeln och oberoende kaskadmodeller. För att få nära optimala lösningar utvecklar vi en girig algoritm baserad på den optimala algoritmen. Vi utvecklar också en heuristisk algoritm med låg beräkningskomplexitet för stora sociala nätverk. Resultat: För att utvärdera den praktiska effektiviteten hos våra algoritmer gör vi en simuleringsstudie baserad på verkliga scenarier. Experimenten utförs på tre verkliga sociala nätverk, och de experimentella resultaten visar att mer exakta partitioner enligt påverkan utbredning kan erhållas med hjälp av våra algoritmer snarare än med hjälp av några klassiska community partition algoritmer. Slutsatser: I denna studie undersöker vi problemet med samhällsdelning i sociala nätverk. Det formuleras som ett optimeringsproblem och undersöks både teoretiskt och praktiskt. Resultaten kan tillämpas för att hitta samhällen i sociala nätverk och är också användbara för påverkan utbredningsproblem i sociala nätverk.
Z. Lu m.fl. REF anser community partition problemet som en kombinatorisk optimering problem, som delar K osammanhängande samhällen i målet att maximera inflytandet i varje gemenskap.
Influence-based community partition for social networks
{'venue': None, 'journal': 'Computational Social Networks', 'mag_field_of_study': ['Computer Science']}