sna (version 2.7)

kcores: Compute the k-Core Structure of a Graph

Description

kcores calculates the k-core structure of the input network, using the centrality measure indicated in cmode.

Usage

kcores(dat, mode = "digraph", diag = FALSE, cmode = "freeman",
    ignore.eval = FALSE)

Value

A vector containing the maximum core membership for each vertex.

Arguments

dat

one or more (possibly valued) graphs.

mode

"digraph" for directed data, otherwise "graph".

diag

logical; should self-ties be included in the degree calculations?

cmode

the degree centrality mode to use when constructing the cores.

ignore.eval

logical; should edge values be ignored when computing degree?

Author

Carter T. Butts

Details

Let $G=(V,E)$ be a graph, and let $f(v,S,G)$ for $v\in V,S\subseteq V$ be a real-valued vertex property function (in the language of Batagelj and Zaversnik). Then some set $H\subseteq V$ is a generalized k-core for $f$ if $H$ is a maximal set such that $f(v,H,G)\ge k$ for all $v\in H$. Typically, $f$ is chosen to be a degree measure with respect to $S$ (e.g., the number of ties to vertices in $S$). In this case, the resulting k-cores have the intuitive property of being maximal sets such that every set member is tied (in the appropriate manner) to at least k others within the set.

Degree-based k-cores are a simple tool for identifying well-connected structures within large graphs. Let the core number of vertex $v$ be the value of the highest-value core containing $v$. Then, intuitively, vertices with high core numbers belong to relatively well-connected sets (in the sense of sets with high minimum internal degree). It is important to note that, while a given k-core need not be connected, it is composed of subsets which are themselves well-connected; thus, the k-cores can be thought of as unions of relatively cohesive subgroups. As k-cores are nested, it is also natural to think of each k-core as representing a “slice” through a hypothetical “cohesion surface” on $G$. (Indeed, k-cores are often visualized in exactly this manner.)

The kcores function produces degree-based k-cores, for various degree measures (with or without edge values). The return value is the vector of core numbers for $V$, based on the selected degree measure. Missing (i.e., NA) edge are removed for purposes of the degree calculation.

References

Batagelj, V. and Zaversnik, M. (2002). “An $O(m)$ Algorithm for Cores Decomposition of Networks.” arXiv:cs/0310049v1

Batagelj, V. and Zaversnik, M. (2002). “Generalized Cores.” arXiv:cs/0202039v1

Wasserman, S. and Faust,K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

See Also

degree

Examples

#Generate a graph with core-periphery structure
cv<-runif(30)
g<-rgraph(30,tp=cv%o%cv)

#Compute the k-cores based on total degree
kc<-kcores(g)
kc

#Plot the result
gplot(g,vertex.col=kc)