Last chance! 50% off unlimited learning
Sale ends in
Last chance! 50% off unlimited learning
Sale ends in
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