This algorithm adds an attribute to each node that specifies the k-core that node belongs to. The k-core a node belongs to is the last k-core it would be part of before being removed from the graph in the next k-core. To find a k-core, recursively remove every node with fewer than k edges connected to it.
A k-core is a part of a graph with strong structure. K-cores have been analyzed for their properties, as indicators of the structure of the graph, and to help visualize graphs.
B. Bollobas, The evolution of sparse graphs, in Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honor of Paul Erdos, Academic Press, 1984, 35-57. (References: [ALGDOC:1], [ALGDOC:2])
S. B. Seidman, Network structure and minimum degree, Social Networks 5:269-287.
Size and Connectivity of the k-core of a Random Graph. ?uczak, Tomasz.
Generalized Cores. V. Batagelj, M. Zaversnik.
k-Core Organization of Complex Networks. Dorogovtsev, Goltsev, Mendes