kCliques
Find all the kcliques in an undirected graph
Find all the kcliques in an undirected graph
 Keywords
 models
Usage
kCliques(g)
Arguments
 g
 an instance of the
graph
class
Details
Notice that there are different definitions of kclique in different context.
In computer science, a kclique of a graph is a clique, i.e., a complete subgraph, of k nodes.
In Social Network Analysis, a kclique in a graph is a subgraph where the distance between any two nodes is no greater than k.
Here we take the definition in Social Network Analysis.
Let D be a matrix, D[i][j] is the shortest path from node i to node j. Algorithm is outlined as following: (1) use Johnson's algorithm to fill D; let N = max(D[i][j]) for all i, j; (2) each edge is a 1clique by itself; (3) for k = 2, ..., N, try to expand each (k1)clique to kclique: (3.1) consider a (k1)clique the current kclique KC; (3.2) repeat the following: if for all nodes j in KC, D[v][j]
Value

A list of length N; kth entry (k = 1, ..., N) is a list of all the kcliques in graph
g
.
References
Social Network Analysis: Methods and Applications. By S. Wasserman and K. Faust, pp. 258.
Examples
con < file(system.file("XML/snacliqueex.gxl",package="RBGL"))
coex < fromGXL(con)
close(con)
kCliques(coex)