Databases
StackOverflow2013
Postsdbo
POincremental k-core algorithm
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POincremental k-core algorithm
    text
    copied!<p>Calculating the <a href="http://en.wikipedia.org/wiki/K-core" rel="nofollow noreferrer">k-core</a> of a graph by iteratively pruning vertices is easy enough. However, for my application, I'd like to be able to add vertices to the starting graph and get the updated core without having to recompute the entire k-core from scratch. Is there a reliable algorithm that can take advantage of the work done on previous iterations?</p> <p>For the curious, the k-core is being used as a preprocessing stage in a clique finding algorithm. Any cliques of size 5 are guaranteed to be part of the 4-core of a graph. In my data set, the 4-core is much smaller than the whole graph so brute-forcing it from there might be tractable. Incrementally adding vertices lets the algorithm work with as small of a data set as possible. My set of vertices is infinite and ordered (prime numbers), but I only care about the lowest numbered clique.</p> <p>Edit:</p> <p>Thinking about it some more based on akappa's answer, detecting the creation of a loop is indeed critical. In the graph below, the 2-core is empty before adding F. Adding F does not change the degree of A but it still adds A to the 2-core. It's easy to extend this to see how closing a loop of any size would cause all of the vertices to simultaneously join the 2-core.</p> <p>Adding a vertex can have an effect on the coreness of vertices an arbitrary distance away, but perhaps this is focusing too much on worst-case behavior. </p> <p><img src="https://lh5.ggpht.com/_fJRu319XW2Q/SjB1a5xBDLI/AAAAAAAAAJ8/f9zxhnavB3U/s800/kcorexample1.png" alt="A -- B; A -- C; A -- D -- E; B -- F; C -- F;"></p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload