Att hitta täta subgrafer i stora grafer är en viktig primitiv i en mängd olika tillämpningar i verkligheten som omfattar analys av sociala nätverk, händelsedetektering, biologi och finansiering. I de flesta sådana tillämpningar syftar man vanligtvis till att hitta flera (eventuellt överlappande) täta subgrafer som kan motsvara samhällen i sociala nätverk eller intressanta händelser. Medan en stor mängd arbete ägnas åt att hitta en enda tätaste subgraf, kanske förvånande, har problemet med att hitta flera täta subgrafer med begränsad överlappning inte studerats på ett principfast sätt, så vitt vi vet. I detta arbete definierar och studerar vi en naturlig generalisering av det tätaste subgraf problemet, där det huvudsakliga målet är att hitta som mest k subgrafer med maximal total aggregattäthet, samtidigt som den uppfyller en övre gräns på den parvisa Jaccard koefficienten mellan uppsättningarna av noder i subgraferna. Efter att ha visat att ett sådant problem är NP-Hard, vi utformar en effektiv algoritm som kommer med bevisbara garantier i vissa fall av intresse, samt en effektiv praktisk heuristic. Vår omfattande utvärdering av stora verkliga grafer bekräftar effektiviteten och effektiviteten hos våra algoritmer.
I REF studerar författarna problemet med att hitta flera subgrafer med maximal total densitet och begränsad överlappning.
Finding Subgraphs with Maximum Total Density and Limited Overlap
{'venue': "WSDM '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}