kcore

Introduction

This algorithm is used for estimating the degeneracy of a undirected graph which can be bounded by the result, k-core. It indicates an vertex is in the core region of a graph or not. The algorithm deleting all vertices of degress less than k repeatedly. If a vertex belongs to a k-core but not to any (k+1)-core graph, it has a coreness k. The k-core of a subgraph is the largest k when a non-empty k-core exists. The Wikipedia page is here. (https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#k-Cores )

Parameters

use --help param to view detailed help information.

Input Format

Input files should be formatted as follows:

<src>,<dst>

where <src> and <dst> are integers of type uint32_t, representing the end nodes of an edge.
Note that Plato treats every input graph as undirected by default. For a directed graph, please ensure both <A, B> and <B, A> appear in the input file if they exist. Edges that appear more than once will be considered as multiple edges between the same pair of nodes.

Input example (Following numbers are synthetic and are for demonstration purpose only.)：

4564,823192
823192,973033
1713,823192

Output Format

Output files are formatted as follows：

<vertex_id>,<kcore_value>

where <vertex_id> represents a node and <kcore_value> gives the k-core value of node.

Output example (Following numbers are synthetic and are for demonstration purpose only.)：

4564,2
823192,3

Source code

https://github.com/Tencent/plato/tree/master/plato/algo/kcore