clique.census: Compute Cycle Census Information

In sna: Tools for Social Network Analysis

Compute Cycle Census Information

Description

clique.census computes clique census statistics on one or more input graphs. In addition to aggregate counts of maximal cliques, results may be disaggregated by vertex and co-membership information may be computed.

Usage

clique.census(dat, mode = "digraph", tabulate.by.vertex = TRUE,
    clique.comembership = c("none", "sum", "bysize"), enumerate = TRUE,
    na.omit = TRUE)

Arguments

dat	one or more input graphs.
mode	"digraph" for directed graphs, or "graph" for undirected graphs.
tabulate.by.vertex	logical; should maximal clique counts be tabulated by vertex?
clique.comembership	the type of clique co-membership information to be tabulated, if any. "sum" returns a vertex by vertex matrix of clique co-membership counts; these are disaggregated by clique size if "bysize" is used. If "none" is given, no co-membership information is computed.
enumerate	logical; should an enumeration of all maximal cliques be returned?
na.omit	logical; should missing edges be omitted?

Details

A (maximal) clique is a maximal set of mutually adjacenct vertices. Cliques are important for their role as cohesive subgroups, but show up in many other contexts as well.

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). Likewise, kpath.census and kcycle.census compute a range of census statistics related to k-paths and k-cycles. clique.census provides similar functionality for the census of maximal cliques, including:

• Aggregate counts of maximal cliques by size.

• Counts of cliques to which each vertex belongs (when tabulate.byvertex==TRUE).

• Counts of clique co-memberships, potentially disaggregated by size (when the appropriate co-membership argument is set to bylength).

These calculations are intrinsically expensive (clique enumeration is NP hard in the general case), and users should be aware that computing the census can be impractical on large graphs (unless they are very sparse). On the other hand, the algorithm employed here (a variant of Makino and Uno (2004)) is generally fast enough to suport enumeration for even dense graphs of several hundred vertices on a typical desktop computer.

Calling this function with mode=="digraph", forces and initial symmetrization step, which can be avoided with mode=="graph". While incorrectly employing the default is harmless (except for the relatively small cost of verifying symmetry), setting mode=="graph" incorrectly may result in problematic behavior. When in doubt, stick with the default.

Value

A list with the following elements:

clique.count	If tabulate.byvertex==FALSE, a vector of aggregate counts by clique size. Otherwise, a matrix whose first column is a vector of aggregate clique counts, and whose succeeding columns contain vectors of clique counts for each vertex.
clique.comemb	If clique.comembership!="none", a matrix or array containing co-membership in cliques by vertex pairs. If clique.comembership=="sum", only a matrix of co-memberships is returned; if bysize is used, however, co-memberships are returned in a maxsize by n by n array whose i,j,kth cell is the number of cliques of size i containing j and k (with maxsize being the size of the largest maximal clique).
cliques	If enumerate=TRUE, a list of length equal to the maximum clique size, each element of which is in turn a list of all cliques of corresponding size (given as vectors of vertices).

Warning

The computational cost of calculating cliques grows very sharply in size and network density. It is possible that the expected completion time for your calculation may exceed your life expectancy (and those of subsequent generations).

Author(s)

Carter T. Butts [e-mail]

References

Wasserman, S. and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

Makino, K. and Uno, T. (2004.) “New Algorithms for Enumerating All Maximal Cliques.” In T. Hagerup and J. Katajainen (eds.), SWAT 2004, LNCS 3111, 260-272. Berlin: Springer-Verlag.

See Also

dyad.census, triad.census, kcycle.census, kpath.census

Examples

#Generate a fairly dense random graph
g<-rgraph(25)

#Obtain cliques by vertex, with co-membership by size
cc<-clique.census(g,clique.comembership="bysize")
cc$clique.count                             #Examine clique counts
cc$clique.comemb[1,,]                       #Isolate co-membership is trivial
cc$clique.comemb[2,,]                       #Co-membership for 2-cliques
cc$clique.comemb[3,,]                       #Co-membership for 3-cliques
cc$cliques                                  #Enumerate the cliques

sna documentation built on Sept. 11, 2024, 8:45 p.m.