algoritmo incrementale k-core

Question

Calcolare il valore k-core di un grafico estraendo in modo iterativo i vertici è abbastanza semplice. Tuttavia, per la mia applicazione, mi piacerebbe essere in grado di aggiungere i vertici al grafico iniziale e ottenere il core aggiornato senza dover ricalcolare l'intero k-core da zero. Esiste un algoritmo affidabile in grado di sfruttare il lavoro svolto su iterazioni precedenti?

Per i curiosi, il k-core viene utilizzato come fase di pre-elaborazione in un algoritmo di ricerca di cricche. Qualsiasi cricca di taglia 5 è garantita come parte del 4-core di un grafico. Nel mio set di dati, il 4-core è molto più piccolo di tutto il grafico, quindi la forza bruta - forzandola da lì potrebbe essere trattabile. L'aggiunta incrementale di vertici consente all'algoritmo di lavorare il più piccolo possibile di un set di dati. La mia serie di vertici è infinita e ordinata (numeri primi), ma mi interessa solo la cricca numerata più bassa.

Edit:

Pensando ancora un po 'in base alla risposta del akappa, rilevando la creazione di un ciclo è davvero critica. Nel grafico sottostante, il 2-core è vuoto prima di aggiungere F. L'aggiunta di F non modifica il grado di A, ma aggiunge ancora A al 2-core. È facile estenderlo per vedere come chiudere un loop di qualsiasi dimensione causerebbe l'unione simultanea di tutti i vertici del 2-core.

L'aggiunta di un vertice può avere un effetto sul coreness dei vertici a una distanza arbitraria, ma forse questo si sta concentrando troppo sul comportamento del caso peggiore.

Answer 1

Mi sembra che un algoritmo per un incrementale calcolo k-core basato su esplorazione locale del grafico, invece di una potatura iterativo "globale", avrebbe bisogno di un ciclo di rilevamento incrementale per vedere quali bordi potrebbero contribuire a inserire un vertice nel k-core, che è un problema difficile.

Penso che il meglio che puoi fare è ricalcolare l'algoritmo del k-core ad ogni passaggio, rimuovendo dal grafico i vertici che sono già nel k-core e inizializzando, nel vertice della mappa -> "k -core vertices adiacenti "il numero di vertici adiacenti che già si trovano nel k-core.

Answer 2

Idea veloce: È possibile salvare la cronologia in un elenco L, ad esempio, salvare l'ordine in cui i nodi sono stati rimossi. Ogni volta che aggiungi un nuovo nodo v, inizia dal primo nodo w in L, che è adiacente a v. Quindi, passa attraverso i nodi rimanenti in L da w on in ordine lineare. (E testare il nodo v pure ed eventualmente aggiungerlo a L.)

Answer 3

È un problema difficile, ma sicuramente non NP-Hard. Per quanto ne so, non ci sono soluzioni generali nell'accademia sull'aggiornamento incrementale di K-core con qualsiasi numero K. Ma i seguenti due documenti sono sicuramente degni di lettura:

[1] Estrazione Analizzando e Visualizzando Triangolo K- Motivi principali all'interno delle reti. http://www.cse.ohio-state.edu/~zhangya/ICDE12_conf_full_179.pdf

[2] Algoritmi di streaming per la decomposizione di k-core. http://www.cse.ohio-state.edu/~sariyuce/file/Publications_files/VLDB13.pdf

Sono comparse in importanti conferenze nell'area di gestione dei dati, quindi la metodologia dovrebbe essere affidabile.