weighted_cliques {igraph}R Documentation

Functions to find weighted cliques, ie. weighted complete subgraphs in a graph

Description

These functions find all, the largest or all the maximal weighted cliques in an undirected graph. The weight of a clique is the sum of the weights of its edges.

Usage

weighted_cliques(
  graph,
  vertex.weights = NULL,
  min.weight = 0,
  max.weight = 0,
  maximal = FALSE
)

Arguments

graph

The input graph, directed graphs will be considered as undirected ones, multiple edges and loops are ignored.

vertex.weights

Vertex weight vector. If the graph has a weight vertex attribute, then this is used by default. If the graph does not have a weight vertex attribute and this argument is 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.

min.weight

Numeric constant, lower limit on the weight of the cliques to find. NULL means no limit, ie. it is the same as 0.

max.weight

Numeric constant, upper limit on the weight of the cliques to find. NULL means no limit.

maximal

Specifies whether to look for all weighted cliques (FALSE) or only the maximal ones (TRUE).

Details

weighted_cliques find all complete subgraphs in the input graph, obeying the weight limitations given in the min and max arguments.

largest_weighted_cliques finds all largest weighted cliques in the input graph. A clique is largest if there is no other clique whose total weight is larger than the weight of this clique.

max_weighted_cliques finds all maximal weighted cliques in the input graph. A weighted clique is maximal if it cannot be extended to a clique with larger total weight. The largest weighted cliques are always maximal, but a maximal weighted clique is not necessarily the largest.

count_max_weighted_cliques counts the maximal weighted cliques.

weighted_clique_num calculates the weight of the largest weighted clique(s).

Value

weighted_cliques and largest_weighted_cliques return a list containing numeric vectors of vertex IDs. Each list element is a weighted clique, i.e. a vertex sequence of class igraph.vs.

weighted_clique_num and count_max_weighted_cliques return an integer scalar.

Author(s)

Tamas Nepusz ntamas@gmail.com and Gabor Csardi csardi.gabor@gmail.com

See Also

ivs

Examples


g <- make_graph("zachary")
V(g)$weight <- 1
V(g)[c(1,2,3,4,14)]$weight <- 3
weighted_cliques(g)
weighted_cliques(g, maximal=TRUE)
largest_weighted_cliques(g)
weighted_clique_num(g)

[Package igraph version 1.3.5 Index]