En k-kärna i en graf är en maximal ansluten subgraf där varje vertex är ansluten till minst k hörn i subgrafen. K-core nedbrytning används ofta i storskalig nätverksanalys, såsom community detektion, proteinfunktionsförutsägelse, visualisering, och lösa NP-Hard problem på verkliga nätverk effektivt, som maximal klick fynd. I många tillämpningar i verkligheten förändras nätverken över tiden. Därför är det viktigt att utveckla effektiva inkrementella algoritmer för strömmande grafdata. I detta dokument föreslår vi de första inkrementella k-core nedbrytningsalgoritmerna för streaming grafdata. Dessa algoritmer lokaliserar en liten subgraf som garanterat innehåller listan över hörn vars maximala k- core- värden måste uppdateras, och effektivt bearbeta den här subgrafen för att uppdatera k- core- nedbrytningen. Våra resultat visar en betydande minskning av körtiden jämfört med icke-inkrementella alternativ. Vi visar effektiviteten av våra algoritmer på olika typer av verkliga och syntetiska grafer, på olika skalor. För en graf på 16 miljoner hörn, observerar vi speedups som når en miljon gånger, i förhållande till de icke-inkrementella algoritmer.
Saríyüce m.fl. REF föreslog en effektiv parallellalgoritm för att hitta en k-core subgraph, där varje vertex är ansluten till minst k hörn i subgrafen.
Streaming Algorithms for k-core Decomposition
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}