Compute the k-Core Structure of a Graph
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)dat |
one or more (possibly valued) graphs. |
mode |
|
diag |
logical; should self-ties be included in the degree calculations? |
cmode |
the |
ignore.eval |
logical; should edge values be ignored when computing degree? |
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 V subseteq H is a generalized k-core for f if H is a maximal set such that f(v,H,G)>=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.
A vector containing the maximum core membership for each vertex.
Carter T. Butts buttsc@uci.edu
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.
#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)
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.