Nyligen har det funnits ett stort intresse för att studera problemet med samhällssökning i sociala nätverk och informationsnätverk: med tanke på en eller flera frågenoder, hitta tätt sammankopplade samhällen som innehåller frågenoder. De flesta befintliga studier tar dock inte upp frågan om "fri ryttare", det vill säga noder långt borta från frågenoder och irrelevanta för dem ingår i den upptäckta gemenskapen. Vissa state-of-the-art modeller har försökt att ta itu med denna fråga, men inte bara är deras formulerade problem NP-hård, de tillåter inte några approximationer utan restriktiva antaganden, som kanske inte alltid håller i praktiken. I det här dokumentet, givet en oriktad graf G och en uppsättning frågenoder Q, studerar vi community search med hjälp av den k-truss-baserade gemenskapsmodellen. Vi formulerar vårt problem med att hitta en närmaste community (CTC), som att hitta en ansluten k-truss subgraph med den största k som innehåller Q, och har den minsta diametern bland sådana subgrafer. Vi bevisar att det här problemet är NP-hard. Dessutom är det svårt för NP att uppskatta problemet inom en faktor (2−ε), för alla ε > 0. Men vi utvecklar en girig algoritmisk ram, som först hittar en CTC som innehåller Q, och sedan iterativt tar bort de yttersta noderna från Q, från grafen. Metoden uppnår 2 approximation till den optimala lösningen. För att ytterligare förbättra effektiviteten använder vi ett kompakt truss index och utvecklar effektiva algoritmer för k-truss identifiering och underhåll när noder elimineras. Dessutom, med hjälp av bulk radering optimering och lokala prospekteringsstrategier, föreslår vi två mer effektiva algoritmer. Den ena handlar med en viss approximativ kvalitet för effektivitet medan den andra är en mycket effektiv heuristisk. Omfattande experiment på 6 verkliga nätverk visar effektiviteten och effektiviteten i vår samhällsmodell och sökalgoritmer.
Mer nyligen, Huang et al. REF föreslog den närmaste communitymodellen för att hitta k-truss-gemenskapen med liten diameter.
Approximate Closest Community Search in Networks
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}