Graph Decomposition

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> add_vertex!(g);

julia> add_edge!(g, 5, 2);

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

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> add_vertex!(g);

julia> add_edge!(g, 5, 2);

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    

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> add_vertex!(g);

julia> add_edge!(g, 5, 2);

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}

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> add_vertex!(g);

julia> add_edge!(g, 5, 2);

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

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> add_vertex!(g);

julia> add_edge!(g, 5, 2);

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