Sammanfattning Att hitta täta subgrafer är ett viktigt problem inom grafbrytning och har många praktiska tillämpningar. Samtidigt, medan stora verkliga nätverk är kända för att ha många samhällen som inte är väl åtskilda, de flesta av det befintliga arbetet fokuserar på problemet med att hitta en enda tätaste subgraf. Därför är det naturligt att överväga frågan om att hitta topp-k tätaste subgrafer. En stor utmaning när det gäller att ta itu med denna fråga är hur man ska hantera överlappningar: att helt eliminera överlappningar är ett alternativ, men detta kan leda till att subgrafer inte blir så täta som det skulle vara möjligt genom att tillåta en begränsad mängd överlappningar. Dessutom är överlappningar önskvärda eftersom det i de flesta verkliga grafer finns hörn som tillhör mer än en gemenskap, och därmed mer än en tätaste subgraf. I detta dokument studerar vi problemet med att hitta topp-k överlappande tätaste subgrafer, och vi presenterar ett nytt tillvägagångssätt som förbättrar över de befintliga teknikerna, både i teori och praktik. För det första omformulerar vi problemdefinitionen på ett sätt som vi kan få en algoritm med konstanta approximationsgarantier. Vår strategi bygger på att vi använder tekniker för att lösa problemet med maximal diversifiering, som vi dock måste utvidga för att göra dem tillämpliga på vår miljö. För det andra utvärderar vi vår algoritm på en samling referensdataset och visar att den på ett övertygande sätt överträffar de tidigare metoderna, både när det gäller kvalitet och effektivitet.
Vidare, Galbrun et al. REF undersökte problemet med att tänja på de översta överlappande tätaste delgraferna och gav garantier för approximering av konstanta faktorer.
Top-k overlapping densest subgraphs
{'venue': 'Data Mining and Knowledge Discovery', 'journal': 'Data Mining and Knowledge Discovery', 'mag_field_of_study': ['Computer Science']}