networkx 2.8.2 Pypi GitHub Homepage
Other Docs
NotesParametersReturnsBackRef
max_weight_clique(G, weight='weight')

A clique in a graph is a set of nodes such that every two distinct nodes are adjacent. The weight of a clique is the sum of the weights of its nodes. A maximum weight clique of graph G is a clique C in G such that no clique in G has weight greater than the weight of C.

Notes

The implementation is recursive, and therefore it may run into recursion depth issues if G contains a clique whose number of nodes is close to the recursion depth limit.

At each search node, the algorithm greedily constructs a weighted independent set cover of part of the graph in order to find a small set of nodes on which to branch. The algorithm is very similar to the algorithm of Tavares et al. , other than the fact that the NetworkX version does not use bitsets. This style of algorithm for maximum weight clique (and maximum weight independent set, which is the same problem but on the complement graph) has a decades-long history. See Algorithm B of Warren and Hicks and the references in that paper.

Parameters

G : NetworkX graph

Undirected graph

weight : string or None, optional (default='weight')

The node attribute that holds the integer value used as a weight. If None, then each node has weight 1.

Returns

clique : list

the nodes of a maximum weight clique

weight : int

the weight of a maximum weight clique

Find a maximum weight clique in G.

Examples

See :

Back References

The following pages refer to to this document either explicitly or contain code examples using this.

networkx.algorithms.clique.MaxWeightClique

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them


GitHub : /networkx/algorithms/clique.py#726
type: <class 'function'>
Commit: