# Degeneracy

Graphs.jl provides a few functions for graph degeneracy.

## Full docs

Graphs.core_numberMethod
core_number(g)

Return the core number for each vertex in graph g.

A k-core is a maximal subgraph that contains vertices of degree k or more. The core number of a vertex is the largest value k of a k-core containing that vertex.

Implementation Notes

Not implemented for graphs with self loops.

References

• An O(m) Algorithm for Cores Decomposition of Networks, Vladimir Batagelj and Matjaz Zaversnik, 2003. http://arxiv.org/abs/cs.DS/0310049

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> core_number(g)
6-element Array{Int64,1}:
1
2
2
2
2
0
source
Graphs.k_coreFunction
k_core(g[, k]; corenum=core_number(g))

Return a vector of vertices in the k-core of graph g. If k is not specified, return the core with the largest degree.

A k-core is a maximal subgraph that contains vertices of degree k or more.

Implementation Notes

Not implemented for graphs with self loops.

References

• An O(m) Algorithm for Cores Decomposition of Networks, Vladimir Batagelj and Matjaz Zaversnik, 2003. http://arxiv.org/abs/cs.DS/0310049

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> k_core(g, 1)
5-element Array{Int64,1}:
1
2
3
4
5

julia> k_core(g, 2)
4-element Array{Int64,1}:
2
3
4
5
source
Graphs.k_coronaMethod
k_corona(g, k; corenum=core_number(g))

Return a vector of vertices in the k-corona of g.

The k-corona is the subgraph of vertices in the k-core which have exactly k neighbors in the k-core.

Implementation Notes

Not implemented for graphs with parallel edges or self loops.

References

• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects, A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes, Phys. Rev. E 73, 056101 (2006) http://link.aps.org/doi/10.1103/PhysRevE.73.056101

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> k_corona(g, 0)
1-element Array{Int64,1}:
6

julia> k_corona(g, 1)
1-element Array{Int64,1}:
1

julia> k_corona(g, 2)
4-element Array{Int64,1}:
2
3
4
5

julia> k_corona(g, 3)
0-element Array{Int64,1}
source
Graphs.k_crustFunction
k_crust(g[, k]; corenum=core_number(g))

Return a vector of vertices in the k-crust of g. If k is not specified, return the crust of the core with the largest degree.

The k-crust is the graph g with the k-core removed.

Implementation Notes

This definition of k-crust is different than the definition in References. The k-crust in References is equivalent to the k+1 crust of this algorithm.

Not implemented for graphs with self loops.

References

• A model of Internet topology using k-shell decomposition Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 http://www.pnas.org/content/104/27/11150.full

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> k_crust(g, 0)
1-element Array{Int64,1}:
6

julia> k_crust(g, 1)
2-element Array{Int64,1}:
1
6

julia> k_crust(g, 2)
6-element Array{Int64,1}:
1
2
3
4
5
6
source
Graphs.k_shellFunction
k_shell(g[, k]; corenum=core_number(g))

Return a vector of vertices in the k-shell of g. If k is not specified, return the shell of the core with the largest degree.

The k-shell is the subgraph of vertices in the k-core but not in the (k+1)-core. This is similar to k_corona but in that case only neighbors in the k-core are considered.

Implementation Notes

Not implemented for graphs with parallel edges or self loops.

References

• A model of Internet topology using k-shell decomposition Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 http://www.pnas.org/content/104/27/11150.full

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> k_shell(g, 0)
1-element Array{Int64,1}:
6

julia> k_shell(g, 1)
1-element Array{Int64,1}:
1

julia> k_shell(g, 2)
4-element Array{Int64,1}:
2
3
4
5
source