Compute Path or Cycle Census Information
kpath.census
and kcycle.census
compute k-path or k-cycle census statistics (respectively) on one or more input graphs. In addition to aggregate counts of paths or cycles, results may be disaggregated by vertex and co-membership information may be computed.
kcycle.census(dat, maxlen = 3, mode = "digraph", tabulate.by.vertex = TRUE, cycle.comembership = c("none", "sum", "bylength")) kpath.census(dat, maxlen = 3, mode = "digraph", tabulate.by.vertex = TRUE, path.comembership = c("none", "sum", "bylength"), dyadic.tabulation = c("none", "sum", "bylength"))
cycle.comembership |
the type of cycle co-membership information to be tabulated, if any. |
dat |
one or more input graphs. |
maxlen |
the maximum path/cycle length to evaluate. |
mode |
|
tabulate.by.vertex |
logical; should path or cycle incidence counts be tabulated by vertex? |
path.comembership |
as per |
dyadic.tabulation |
the type of dyadic path count information to be tabulated, if any. |
There are several equivalent characterizations of paths and cycles, of which the following is one example. For an arbitrary graph G, a path is a sequence of distinct vertices v_1, v_2, .... v_n and included edges such that v_i is adjacent to v_{i+1} for all i in 1, 2, ... k-1 via the pair's included edge. (Contrast this with a walk, in which edges and/or vertices may be repeated.) A cycle is the union of a path and an edge making v_n adjacent to v_i. k-paths and k-cycles are respective paths and cycles having k edges (in the former case) or k vertices (in the latter). The above definitions may be applied in both directed and undirected contexts, by substituting the appropriate notion of adjacency. (Note that authors do not always employ the same terminology for these concepts, especially in older texts – it is wise to verify the definitions being used in any particular context.)
A subgraph census statistic is a function which, for any given graph and subgraph, gives the number of copies of the latter contained in the former. A collection of subgraph census statistics is referred to as a subgraph census; widely used examples include the dyad and triad censuses, implemented in sna
by the dyad.census
and triad.census
functions (respectively). kpath.census
and kcycle.census
compute a range of census statistics related to k-paths and k-cycles, including:
Aggregate counts of paths/cycles by length (i.e., k).
Counts of paths/cycles to which each vertex belongs (when tabulate.byvertex==TRUE
).
Counts of path/cycle co-memberships, potentially disaggregated by length (when the appropriate co-membership argument is set to bylength
).
For path.census
, counts of the total number of paths from each vertex to each other vertex, possibly disaggregated by length (if dyadic.tabulation=="bylength"
).
The length of the maximum-length path/cycle to compute is given by maxlen
. These calculations are intrinsically expensive (path/cycle computation is NP complete in the general case), and users should hence be wary when increasing maxlen
. On the other hand, it may be possible to enumerate even long paths or cycles on a very sparse graph; scaling is approximately c^k, where k is given by maxlen
and c is the size of the largest dense cluster.
The paths or cycles computed by this function are directed if mode=="digraph"
, or undirected if mode=="graph"
. Failing to set mode
correctly may result in problematic behavior.
For kpath.census
, a list with the following elements:
path.count |
If |
path.comemb |
If |
paths.bydyad |
If |
For kcycle.census
, a similar list:
cycle.count |
If |
cycle.comemb |
If |
The computational cost of calculating paths and cycles grows very sharply in both maxlen
and network density. Be wary of setting maxlen
greater than 5-6, unless you know what you are doing. Otherwise, the expected completion time for your calculation may exceed your life expectancy (and those of subsequent generations).
Carter T. Butts buttsc@uci.edu
Butts, C.T. (2006). “Cycle Census Statistics for Exponential Random Graph Models.” IMBS Technical Report MBS 06-05, University of California, Irvine.
West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.
g<-rgraph(20,tp=1.5/19) #Obtain paths by vertex, with dyadic path counts pc<-kpath.census(g,maxlen=5,dyadic.tabulation="sum") pc$path.count #Examine path counts pc$paths.bydyad #Examine dyadic paths #Obtain aggregate cycle counts, with co-membership by length cc<-kcycle.census(g,maxlen=5,tabulate.by.vertex=FALSE, cycle.comembership="bylength") cc$cycle.count #Examine cycle counts cc$cycle.comemb[1,,] #Co-membership for 2-cycles cc$cycle.comemb[2,,] #Co-membership for 3-cycles cc$cycle.comemb[3,,] #Co-membership for 4-cycles
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.