kCliques: Find all the k-cliques in an undirected graph

In RBGL: An interface to the BOOST graph library

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 <[e-mail]>

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)

Example output

Loading required package: graph
Loading required package: BiocGenerics
Loading required package: parallel

Attaching package: ‘BiocGenerics’

The following objects are masked from ‘package:parallel’:

    clusterApply, clusterApplyLB, clusterCall, clusterEvalQ,
    clusterExport, clusterMap, parApply, parCapply, parLapply,
    parLapplyLB, parRapply, parSapply, parSapplyLB

The following objects are masked from ‘package:stats’:

    IQR, mad, sd, var, xtabs

The following objects are masked from ‘package:base’:

    anyDuplicated, append, as.data.frame, basename, cbind, colnames,
    dirname, do.call, duplicated, eval, evalq, Filter, Find, get, grep,
    grepl, intersect, is.unsorted, lapply, Map, mapply, match, mget,
    order, paste, pmax, pmax.int, pmin, pmin.int, Position, rank,
    rbind, Reduce, rownames, sapply, setdiff, sort, table, tapply,
    union, unique, unsplit, which.max, which.min

$`1-cliques`
$`1-cliques`[[1]]
[1] "1" "2" "3"

$`1-cliques`[[2]]
[1] "2" "4"

$`1-cliques`[[3]]
[1] "3" "5"

$`1-cliques`[[4]]
[1] "4" "6"

$`1-cliques`[[5]]
[1] "5" "6"


$`2-cliques`
$`2-cliques`[[1]]
[1] "1" "2" "3" "4" "5"

$`2-cliques`[[2]]
[1] "2" "3" "4" "5" "6"


$`3-cliques`
$`3-cliques`[[1]]
[1] "1" "2" "3" "4" "5" "6"

RBGL documentation built on Nov. 8, 2020, 5 p.m.