# path.census: Compute Path or Cycle Census Information In sna: Tools for Social Network Analysis

## Description

`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.

## 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 co-membership information to be tabulated, if any. `"sum"` returns a vertex by vertex matrix of cycle co-membership counts; these are disaggregated by cycle length if `"bylength"` is used. If `"none"` is given, no co-membership information is computed. `dat` one or more input graphs. `maxlen` the maximum path/cycle length to evaluate. `mode` `"digraph"` for directed graphs, or `"graph"` for undirected graphs. `tabulate.by.vertex` logical; should path or cycle incidence counts be tabulated by vertex? `path.comembership` as per `cycle.comembership`, for paths rather than cycles. `dyadic.tabulation` the type of dyadic path count information to be tabulated, if any. `"sum"` returns a vertex by vertex matrix of source/destination path counts, while `"bylength"` disaggregates these counts by path length. Selecting `"none"` disables this computation.

## 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, ... 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.

## Value

For `kpath.census`, a list with the following elements:

 `path.count ` If `tabulate.byvertex==FALSE`, a vector of aggregate counts by path length. Otherwise, a matrix whose first column is a vector of aggregate path counts, and whose succeeding columns contain vectors of path counts for each vertex. `path.comemb ` If `path.comembership!="none"`, a matrix or array containing co-membership in paths by vertex pairs. If `path.comembership=="sum"`, only a matrix of co-memberships is returned; if `bylength` is used, however, co-memberships are returned in a `maxlen` by n by n array whose i,j,kth cell is the number of paths of length i containing `j` and `k`. `paths.bydyad ` If `dyadic.tabulation!="none"`, a matrix or array containing the number of paths originating at a particular vertex and terminating. If `bylength` is used, dyadic path counts are supplied via a `maxlen` by n by n array whose i,j,kth cell is the number of paths of length i starting at `j` and ending with `k`. If `sum` is used instead, only a matrix whose i,j cell contains the total number of paths from i to j is returned.

For `kcycle.census`, a similar list:

 `cycle.count ` If `tabulate.byvertex==FALSE`, a vector of aggregate counts by cycle length. Otherwise, a matrix whose first column is a vector of aggregate cycle counts, and whose succeeding columns contain vectors of cycle counts for each vertex. `cycle.comemb ` If `cycle.comembership!="none"`, a matrix or array containing co-membership in cycles by vertex pairs. If `cycle.comembership=="sum"`, only a matrix of co-memberships is returned; if `bylength` is used, however, co-memberships are returned in a `maxlen` by n by n array whose i,j,kth cell is the number of cycles of length i containing `j` and `k`.

## 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 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).

## Author(s)

Carter T. Butts [email protected]

## References

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.

`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 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 ```

### Example output

```Loading required package: statnet.common

Attaching package: 'statnet.common'

The following object is masked from 'package:base':

order

network: Classes for Relational Data
Version 1.13.0 created on 2015-08-31.
copyright (c) 2005, Carter T. Butts, University of California-Irvine
Mark S. Handcock, University of California -- Los Angeles
David R. Hunter, Penn State University
Martina Morris, University of Washington
Skye Bender-deMoll, University of Washington
For citation information, type citation("network").
Type help("network-package") to get started.

sna: Tools for Social Network Analysis
Version 2.4 created on 2016-07-23.
copyright (c) 2005, Carter T. Butts, University of California-Irvine
For citation information, type citation("sna").
Type help(package="sna") to get started.

Agg v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v20
1  24  2  6  2  6  1  2  2  0  1   2   6   0   1   2   5   2   2   2   3   1
2  34  5 15  5 14  0  4  3  0  1   2  15   0   3   8  10   3   1   6   4   3
3  42 10 23  7 22  0  5  6  0  1   3  27   0   5  14  17   6   3   9   7   3
4  53 17 31  8 32  0  5  7  0  3   7  40   0   7  27  33  13   2  14  14   5
5  48 18 33  9 35  0  6  7  0  3   5  39   0   5  31  38  15   3  18  18   5
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v20
v1   0  1  0  0  0  0  0  0  0   0   1   0   1   1   1   1   0   0   0   0
v2   2  0  0  1  0  0  0  0  1   0   2   0   2   3   3   1   0   1   1   0
v3   3  3  0  2  0  0  0  0  2   0   4   0   3   3   5   2   0   2   2   0
v4   2  2  0  0  0  0  0  0  1   0   3   0   2   2   3   2   0   1   1   0
v5   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v6   1  1  0  1  0  0  0  0  0   0   1   0   1   2   2   1   0   1   1   0
v7   1  1  0  1  0  0  0  0  1   0   2   0   1   1   3   1   0   1   1   0
v8   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v9   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v10  2  2  0  2  0  0  1  0  0   0   2   0   2   2   2   2   0   1   1   0
v11  1  1  0  1  0  0  0  0  1   0   0   0   1   2   3   1   0   1   1   0
v12  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v13  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v14  1  1  0  1  0  0  0  0  0   0   1   0   1   0   2   1   0   1   1   0
v15  1  1  0  1  0  0  0  0  0   0   1   0   1   1   0   1   0   1   0   0
v16  1  1  0  1  0  0  0  0  0   0   1   0   1   1   1   0   0   0   0   0
v17  1  1  0  1  1  1  0  0  0   0   1   0   1   0   2   1   0   1   0   0
v18  1  1  0  0  0  0  0  0  1   0   1   0   1   1   1   0   0   0   1   0
v19  1  1  0  1  0  0  0  0  1   0   1   0   1   1   1   1   0   0   0   0
v20  2  2  0  1  0  0  0  0  1   0   2   0   2   2   2   1   0   1   1   0
2 3 4 5
2 0 0 2
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v20
v1   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v2   0  2  0  1  0  0  0  0  0   0   1   0   0   0   0   0   0   0   0   0
v3   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v4   0  1  0  1  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v5   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v6   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v7   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v8   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v9   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v10  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v11  0  1  0  0  0  0  0  0  0   0   1   0   0   0   0   0   0   0   0   0
v12  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v13  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v14  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v15  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v16  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v17  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v18  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v19  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v20  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v20
v1   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v2   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v3   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v4   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v5   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v6   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v7   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v8   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v9   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v10  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v11  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v12  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v13  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v14  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v15  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v16  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v17  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v18  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v19  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v20  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v20
v1   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v2   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v3   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v4   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v5   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v6   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v7   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v8   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v9   0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v10  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v11  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v12  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v13  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v14  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v15  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v16  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v17  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v18  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v19  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
v20  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
```

sna documentation built on May 30, 2017, 12:18 a.m.