KCoreComponents

KCoreComponents[g,k]

gives the k-core components of the underlying simple graph of g.

KCoreComponents[g,k,"In"]

gives the k-core components with vertex in-degrees at least k.

KCoreComponents[g,k,"Out"]

gives the k-core components with vertex out-degrees at least k.

KCoreComponents[{vw,},]

uses rules vw to specify the graph g.

Details

  • A k-core component is a maximal weakly connected subgraph in which all vertices have degree at least k.
  • KCoreComponents returns a list of components {c1,c2,}, where each component ci is given as a list of vertices.
  • For a directed graph g, KCoreComponents[g,k] gives the k-core components of the underlying undirected simple graph of g.
  • KCoreComponents works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open allclose all

Basic Examples  (2)

Find the 3-core components of a graph:

Show the 3-core components:

Find the 4-core components in a social network:

Scope  (10)

KCoreComponents works with undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

KCoreComponents finds core components of any size:

Find k-core components with vertex in-degrees at least k:

Find k-core components with vertex out-degrees at least k:

Use rules to specify the graph:

KCoreComponents gives an empty list if there is no k-core:

KCoreComponents works with large graphs:

Applications  (3)

Highlight the k-cores of a graph:

Find the degeneracy of a graph g, being the largest k such that g has a k-core:

Trees and forests are 1-degenerate graphs:

The BarabasiAlbert model with k edges added at each step is k-degenerate:

A social network:

Group actors:

Highlight groups:

Properties & Relations  (8)

Find k-core components by repeatedly removing vertices of out-degree less than k:

First iteration:

Second iteration:

No more vertices are removed by further iteration:

Use ConnectedComponents to obtain the components of the k-core:

The obtained k-cores of undirected graphs are connected:

A vertex in a k-core component ci has at least k neighbors in ci:

For an undirected graph, the vertex in-degree and out-degree are equal to the vertex degree:

The k-core vertex in-degree and out-degree components are equal to the k-core components:

The maximum clique of size k+1 is contained in a k-core component:

A k-core component is contained in a (k-1)-core component:

The adjacency matrix of a k-core component has at least k nonzero entries in each row:

The adjacency matrix of a k-core in-degree component has at least k nonzero entries in each column:

The adjacency matrix of a k-core out-degree component has at least k nonzero entries in each row:

Introduced in 2010
 (8.0)
 |
Updated in 2014
 (10.0)
2015
 (10.3)