Att hitta täta substrukturer i en graf är en grundläggande grafbrytning, med tillämpningar inom bioinformatik, sociala nätverk och visualisering för att nämna några. Men de flesta standardformuleringar av detta problem (som klique, kvasiclique, k-densest subgraph) är NP-hård. Dessutom är målet sällan att hitta "sann optimal", men att identifiera många (om inte alla) täta understrukturer, förstå deras fördelning i grafen, och helst bestämma relationer mellan dem. Nuvarande täta subgraph finding algoritmer brukar optimera vissa mål, och bara hitta några sådana subgraphs utan att tillhandahålla några strukturella relationer. Vi definierar kärnans nedbrytning av en graf, som representerar grafen som en skog av nuclei. Varje kärna är en subgraph där mindre cliques är närvarande i många större cliques. Skogen av nuclei är en hierarki genom inneslutning, där kanten densitet ökar när vi går mot blad nuclei. Syskonkärnor kan ha begränsade skärningspunkter, vilket gör det möjligt att upptäcka överlappande täta subgrafer. Med rätt parametrar generaliserar kärnans nedbrytning de klassiska begreppen k-cores och k-truss-dekompositioner. Vi ger bevisligen effektiva algoritmer för nuclear decompositions, och empiriskt utvärdera deras beteende i en mängd verkliga grafer. Trädet av nuclei ger konsekvent en global, hierarkisk ögonblicksbild av täta substrukturer, och utgångar täta subgrafer av högre kvalitet än andra toppmoderna lösningar. Vår algoritm kan bearbeta grafer med tiotals miljoner kanter på mindre än en timme.
För att skapa strukturella relationer mellan kliquer, Sariyuce et al. REF definierar kärnans nedbrytning av en graf, som representerade grafen som en skog av nuclei.
Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions
{'venue': "WWW '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}