incremental k-core algorithm

Answer 1

It seems to me that an algorithm for an incremental k-core computation based on local exploration of the graph, instead of a "global" iterative pruning, would need an incremental loop detection in order to see which edges could contribute to enter a vertex in the k-core, which is an hard problem.

I think that the best you can do is to recompute the k-core algorithm at each pass, just removing from the graph the vertices that already are in the k-core and initializing, in the map vertex -> "k-core adjacent vertices" the number of adjacent vertices that already are in the k-core.

Answer 2

Quick idea: You could save the history in a list L, i.e., save the order in which the nodes where removed. Whenever you add a new node v, start at the first node w in L which is adjacent to v. Then just go through the remaining nodes in L from w on in linear order. (And test the node v as well and possibly add it to L.)