Child pages
  • Annotate K-Coreness (Unweighted & Directed)
Skip to end of metadata
Go to start of metadata

You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 2 Next »

Description

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.

Applications

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.

References

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: [1], [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

  • No labels