kcores: Compute the k-Core Structure of a Graph

In sna: Tools for Social Network Analysis

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)

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?

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.

Value

A vector containing the maximum core membership for each vertex.

Author(s)

Carter T. Butts [e-mail]

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)

sna documentation built on Sept. 11, 2024, 8:45 p.m.