1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/cliques.R
\name{cliques}
\alias{cliques}
\alias{largest_cliques}
\alias{max_cliques}
\alias{count_max_cliques}
\alias{clique_num}
\alias{largest_weighted_cliques}
\alias{weighted_clique_num}
\alias{clique_size_counts}
\title{Functions to find cliques, i.e. complete subgraphs in a graph}
\usage{
cliques(graph, min = 0, max = 0)
largest_cliques(graph)
max_cliques(graph, min = NULL, max = NULL, subset = NULL, file = NULL)
count_max_cliques(graph, min = NULL, max = NULL, subset = NULL)
clique_num(graph)
largest_weighted_cliques(graph, vertex.weights = NULL)
weighted_clique_num(graph, vertex.weights = NULL)
clique_size_counts(graph, min = 0, max = 0, maximal = FALSE)
}
\arguments{
\item{graph}{The input graph, directed graphs will be considered as
undirected ones, multiple edges and loops are ignored.}
\item{min}{Numeric constant, lower limit on the size of the cliques to find.
\code{NULL} means no limit, i.e. it is the same as 0.}
\item{max}{Numeric constant, upper limit on the size of the cliques to find.
\code{NULL} means no limit.}
\item{subset}{If not \code{NULL}, then it must be a vector of vertex ids,
numeric or symbolic if the graph is named. The algorithm is run from these
vertices only, so only a subset of all maximal cliques is returned. See the
Eppstein paper for details. This argument makes it possible to easily
parallelize the finding of maximal cliques.}
\item{file}{If not \code{NULL}, then it must be a file name, i.e. a
character scalar. The output of the algorithm is written to this file. (If
it exists, then it will be overwritten.) Each clique will be a separate line
in the file, given with the numeric ids of its vertices, separated by
whitespace.}
\item{vertex.weights}{Vertex weight vector. If the graph has a \code{weight}
vertex attribute, then this is used by default. If the graph does not have a
\code{weight} vertex attribute and this argument is \code{NULL}, then every
vertex is assumed to have a weight of 1. Note that the current implementation
of the weighted clique finder supports positive integer weights only.}
\item{maximal}{Specifies whether to look for all weighted cliques (\code{FALSE})
or only the maximal ones (\code{TRUE}).}
}
\value{
\code{cliques()}, \code{largest_cliques()} and \code{clique_num()}
return a list containing numeric vectors of vertex ids. Each list element is
a clique, i.e. a vertex sequence of class \code{\link[=V]{igraph.vs()}}.
\code{max_cliques()} returns \code{NULL}, invisibly, if its \code{file}
argument is not \code{NULL}. The output is written to the specified file in
this case.
\code{clique_num()} and \code{count_max_cliques()} return an integer
scalar.
\code{clique_size_counts()} returns a numeric vector with the clique sizes such that
the i-th item belongs to cliques of size i. Trailing zeros are currently
truncated, but this might change in future versions.
}
\description{
These functions find all, the largest or all the maximal cliques in an
undirected graph. The size of the largest clique can also be calculated.
}
\details{
\code{cliques()} find all complete subgraphs in the input graph, obeying the
size limitations given in the \code{min} and \code{max} arguments.
\code{largest_cliques()} finds all largest cliques in the input graph. A
clique is largest if there is no other clique including more vertices.
\code{max_cliques()} finds all maximal cliques in the input graph. A
clique is maximal if it cannot be extended to a larger clique. The largest
cliques are always maximal, but a maximal clique is not necessarily the
largest.
\code{count_max_cliques()} counts the maximal cliques.
\code{clique_num()} calculates the size of the largest clique(s).
\code{clique_size_counts()} returns a numeric vector representing a histogram
of clique sizes, between the given minimum and maximum clique size.
}
\examples{
# this usually contains cliques of size six
g <- sample_gnp(100, 0.3)
clique_num(g)
cliques(g, min = 6)
largest_cliques(g)
# To have a bit less maximal cliques, about 100-200 usually
g <- sample_gnp(100, 0.03)
max_cliques(g)
}
\references{
For maximal cliques the following algorithm is implemented:
David Eppstein, Maarten Loffler, Darren Strash: Listing All Maximal Cliques
in Sparse Graphs in Near-optimal Time. \url{https://arxiv.org/abs/1006.5440}
}
\seealso{
Other cliques:
\code{\link{ivs}()},
\code{\link{weighted_cliques}()}
}
\author{
Tamas Nepusz \email{ntamas@gmail.com} and Gabor Csardi
\email{csardi.gabor@gmail.com}
}
\concept{cliques}
\keyword{graphs}
\section{Related documentation in the C library}{\href{https://igraph.org/c/html/latest/igraph-Cliques.html#igraph_cliques}{\code{igraph_cliques()}}, \href{https://igraph.org/c/html/latest/igraph-Cliques.html#igraph_largest_cliques}{\code{igraph_largest_cliques()}}, \href{https://igraph.org/c/html/latest/igraph-Cliques.html#igraph_clique_number}{\code{igraph_clique_number()}}, \href{https://igraph.org/c/html/latest/igraph-Cliques.html#igraph_largest_weighted_cliques}{\code{igraph_largest_weighted_cliques()}}, \href{https://igraph.org/c/html/latest/igraph-Cliques.html#igraph_weighted_clique_number}{\code{igraph_weighted_clique_number()}}, \href{https://igraph.org/c/html/latest/igraph-Cliques.html#igraph_maximal_cliques_hist}{\code{igraph_maximal_cliques_hist()}}, \href{https://igraph.org/c/html/latest/igraph-Cliques.html#igraph_clique_size_hist}{\code{igraph_clique_size_hist()}}.}
|
