kCliques {RBGL} | R Documentation

## Find all the k-cliques in an undirected graph

### Description

Find all the k-cliques in an undirected graph

### Usage

    kCliques(g)

### Arguments

`g` | an instance of the `graph` class

### Details

Notice that there are different definitions of k-clique in different context.

In computer science, a k-clique of a graph is a clique, i.e., a complete subgraph, of k nodes.

In Social Network Analysis, a k-clique 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 1-clique by itself; (3) for k = 2, ..., N, try to expand each (k-1)-clique to k-clique: (3.1) consider a (k-1)-clique the current k-clique KC; (3.2) repeat the following: if for all nodes j in KC, D[v][j] <= k, add node v to KC; (3.3) eliminate duplicates; (4) the whole graph is N-clique.

### Value

A list of length N; k-th entry (k = 1, ..., N) is a list of all the k-cliques in graph `g`.

### Author(s)

Li Long <li.long@isb-sib.ch>

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

[Package RBGL version 1.68.0 Index]