Abstract-K-kärnan i en graf är den största subgraf där varje vertex är ansluten till minst k andra hörn i subgrafen. Kärnnedbrytning finner k-kärnan i grafen för varje möjlig k. Tidigare studier har visat viktiga tillämpningar av kärnnedbrytning såsom i studien av egenskaperna hos stora nätverk (t.ex. hållbarhet, konnektivitet, centralitet, etc.).), för att lösa NP-hårda problem effektivt i verkliga nätverk (t.ex. maximal klickfyndighet, tätaste subgraph approximation, etc.), och för storskaliga nätverk fingeravtryck och visualisering. K-kärnan är ett väl accepterat koncept delvis eftersom det finns en enkel och effektiv algoritm för core nedbrytning, genom att rekursivt ta bort de lägsta grad hörn och deras incident kanter. Denna algoritm kräver dock slumpmässig åtkomst till grafen och förutsätter därför att hela grafen kan behållas i huvudminnet. Verkliga nätverk som sociala nät online har dock blivit oerhört stora under de senaste åren och fortsätter att växa i jämn takt. I detta dokument föreslår vi den första externa-minnesalgoritmen för kärnnedbrytning i massiva grafer. När minnet är tillräckligt stort för att hålla grafen, uppnår vår algoritm jämförbar prestanda som den inbyggda algoritmen. När grafen är för stor för att behållas i minnet, kräver vår algoritm endast O(kmax ) skanning av grafen, där kmax är det största kärnantalet av grafen. Vi demonstrerar effektiviteten i vår algoritm på verkliga nätverk med upp till 52,9 miljoner hörn och 1,65 miljarder kanter.
I REF, Cheng et al. beskriva en effektiv I/O-algoritm för core sönderdelningsproblem i massiva nätverk.
Efficient core decomposition in massive networks
{'venue': '2011 IEEE 27th International Conference on Data Engineering', 'journal': '2011 IEEE 27th International Conference on Data Engineering', 'mag_field_of_study': ['Computer Science']}