Compute Path or Cycle Census Information
Description
kpath.census
and kcycle.census
compute kpath or kcycle 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 comembership information may be computed.
Usage
1 2 3 4 5 6 7  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"))

Arguments
cycle.comembership 
the type of cycle comembership 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. 
Details
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, ... k1 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. kpaths and kcycles 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 kpaths and kcycles, 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 comemberships, potentially disaggregated by length (when the appropriate comembership 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 (ifdyadic.tabulation=="bylength"
).
The length of the maximumlength 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.
Value
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 
Warning
The computational cost of calculating paths and cycles grows very sharply in both maxlen
and network density. Be wary of setting maxlen
greater than 56, 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).
Author(s)
Carter T. Butts buttsc@uci.edu
References
Butts, C.T. (2006). “Cycle Census Statistics for Exponential Random Graph Models.” IMBS Technical Report MBS 0605, University of California, Irvine.
West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.
See Also
dyad.census
, triad.census
, clique.census
, geodist
Examples
1 2 3 4 5 6 7 8 9 10 11 12 13 14  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 comembership 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,,] #Comembership for 2cycles
cc$cycle.comemb[2,,] #Comembership for 3cycles
cc$cycle.comemb[3,,] #Comembership for 4cycles
