kcores
calculates the k-core structure of the input network, using the centrality measure indicated in cmode
.
kcores(dat, mode = "digraph", diag = FALSE, cmode = "freeman",
ignore.eval = FALSE)
A vector containing the maximum core membership for each vertex.
one or more (possibly valued) graphs.
"digraph"
for directed data, otherwise "graph"
.
logical; should self-ties be included in the degree calculations?
the degree
centrality mode to use when constructing the cores.
logical; should edge values be ignored when computing degree?
Carter T. Butts buttsc@uci.edu
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.
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.
degree
#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)
Run the code above in your browser using DataLab