FindKClique
FindKClique[g,k]
finds a largest k-clique in the graph g.
FindKClique[g,k,n]
finds a k-clique containing at most n vertices.
FindKClique[g,k,{n}]
finds a k-clique containing exactly n vertices.
FindKClique[g,k,{nmin,nmax}]
finds a k-clique containing between nmin and nmax vertices.
FindKClique[g,k,nspec,s]
finds at most s k-cliques.
FindKClique[{g,v},k,…]
finds k-cliques that include the vertex v only.
FindKClique[{vw,…},…]
uses rules vw to specify the graph g.
Details
- A k-clique is a maximal set of vertices that are at a distance no greater than k from each other.
- FindKClique returns a list of k-cliques.
- FindKClique will return an empty list if there is no k-clique.
- FindKClique[…,k,nspec,All] finds all the k-cliques.
- FindKClique works with undirected graphs, directed graphs, multigraphs, and mixed graphs.
Background & Context
- FindKClique finds one or more k-cliques in a graph, returning them as a list of vertices. Here, a k-clique is a maximal set of vertices that are at a distance no greater than k from each other. k-cliques are used in project selection, pattern matching, finance, and network analysis.
- FindKClique can be used to find k-cliques of different sizes, from 1 to the largest possible size (in general n for a graph on n vertices). FindKClique can be used to find a single k-clique of specified size, a specified number of cliques, or all.
- 1-cliques are cliques. All k-clans are k-cliques, but the converse is not always true. Related functions include FindClique, FindKClan, FindKClub, and FindKPlex.
Examples
open allclose allScope (14)
Specification (8)
FindKClique works with undirected graphs:
Find k-cliques for arbitrary k:
Use rules to specify the graph:
FindKClique works with large graphs:
Enumeration (6)
A 2-clique containing exactly 4 vertices:
A 2-clique containing at most 4 vertices:
A 2-clique containing between 3 and 5 vertices:
A largest 2-clique that includes a given vertex:
Find all 2-cliques in a graph:
FindKClique gives an empty list if there is no k-clique:
Applications (4)
Highlight all 2-cliques of size 5:
A friendship network between members of a karate club. Find the size of a largest group of people who are friends or a friend of a friend:
A network of books linked by the same buyers on Amazon.com. Find a largest selection of books including The Clinton Wars that was frequently bought by buyers who previously bought a common book:
To prevent data packets from circulating indefinitely in a mobile ad hoc network, a time to live (TTL—the maximum number of edges traversed) value is set to 3. Find all devices that can be reached from device 1:
Properties & Relations (8)
A k-clique in a graph g is a clique in the graph k
power of g:
A complete graph is a maximum k-clique:
A star graph is a maximum 2-clique:
The (k-1)-clique is contained in a k-clique:
All k-clans are k-cliques. The converse is not always true:
A k-club is contained in a k-clique:
The converse is not always true:
Text
Wolfram Research (2012), FindKClique, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKClique.html (updated 2015).
CMS
Wolfram Language. 2012. "FindKClique." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindKClique.html.
APA
Wolfram Language. (2012). FindKClique. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindKClique.html