PGX 1.2.0
Documentation

K-Core

Time Complexity O(E)    Space Requirement O(3*N)

Computes the k-core decomposition of the graph. Returns the largest k-core value found.

Signature

Input Argument Type Comment
G graph
min_core long minimum core ID. Vertices having a smaller core ID will be assigned minCore.
max_core long maximum k-core to consider. Vertices having a larget core ID will be assigned maxCore.
Output Argument Type Comment
k_core nodeProperty node property mapping each vertex to its computed k-core value.
Return Value Type Comment
long the biggest core ID found.

Green-Marl Code

/*
 * Computes the k-core decomposition of the graph. Returns the largest k-kore value found.
 */

procedure k_core(G: graph, min_core, max_core: long;
            k_core: nodeProp<long>): long
{
    nodeProp<int> active_nbrs;
    nodeProp<bool> active, just_deleted; 

    int current_k_core = min_core;
    bool nodes_just_deleted = false;
    bool active_nodes_left = true;

    G.k_core = 0;
    G.active = true;
    G.just_deleted = false;

    G.active_nbrs = _.outDegree() + _.inDegree(); 

    while(current_k_core <= max_core && active_nodes_left) {
        do {
            active_nodes_left = false;
            nodes_just_deleted = false;
            // Notify neighbors that node is deleted
            foreach(n : G.nodes) (n.just_deleted) {
                foreach(k : n.outNbrs) {
                    k.active_nbrs--;
                }
                foreach(k : n.inNbrs) {
                    k.active_nbrs--;
                }
            }
            //consolidate
            foreach(n : G.nodes) (n.active) {
                if(n.just_deleted) {
                    n.just_deleted = false;
                    n.active = false;
                }
                else if(n.active_nbrs < current_k_core) {
                    n.just_deleted = true;
                    n.k_core = current_k_core - 1;
                    active_nodes_left |= true;
                    nodes_just_deleted |= true;
                }
                else {
                    active_nodes_left |= true;
                }
            }
        } while (nodes_just_deleted);
        current_k_core++;
    }

    return current_k_core - 2;
}