Degeneracy
Graphs.jl provides a few functions for graph degeneracy.
Index
Full docs
Graphs.core_number
— Methodcore_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> add_vertex!(g);
julia> add_edge!(g, 5, 2);
julia> core_number(g)
6-element Vector{Int64}:
1
2
2
2
2
0
Graphs.k_core
— Functionk_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> add_vertex!(g);
julia> add_edge!(g, 5, 2);
julia> k_core(g, 1)
5-element Vector{Int64}:
1
2
3
4
5
julia> k_core(g, 2)
4-element Vector{Int64}:
2
3
4
5
Graphs.k_corona
— Methodk_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> add_vertex!(g);
julia> add_edge!(g, 5, 2);
julia> k_corona(g, 0)
1-element Vector{Int64}:
6
julia> k_corona(g, 1)
1-element Vector{Int64}:
1
julia> k_corona(g, 2)
4-element Vector{Int64}:
2
3
4
5
julia> k_corona(g, 3)
Int64[]
Graphs.k_crust
— Functionk_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> add_vertex!(g);
julia> add_edge!(g, 5, 2);
julia> k_crust(g, 0)
1-element Vector{Int64}:
6
julia> k_crust(g, 1)
2-element Vector{Int64}:
1
6
julia> k_crust(g, 2)
6-element Vector{Int64}:
1
2
3
4
5
6
Graphs.k_shell
— Functionk_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> add_vertex!(g);
julia> add_edge!(g, 5, 2);
julia> k_shell(g, 0)
1-element Vector{Int64}:
6
julia> k_shell(g, 1)
1-element Vector{Int64}:
1
julia> k_shell(g, 2)
4-element Vector{Int64}:
2
3
4
5