FindKClan
FindKClan[g,k]
finds a largest k-clan in the graph g.
FindKClan[g,k,n]
finds a k-clan containing at most n vertices.
FindKClan[g,k,{n}]
finds a k-clan containing exactly n vertices.
FindKClan[g,k,{nmin,nmax}]
finds a k-clan containing between nmin and nmax vertices.
FindKClan[g,k,nspec,s]
finds at most s k-clans.
FindKClan[{g,v},k,…]
finds k-clans that include the vertex v only.
FindKClan[{vw,…},…]
uses rules vw to specify the graph g.
Details
- A k-clan is a k-clique where the diameter of the corresponding subgraph is at most k.
- FindKClan returns a list of k-clans.
- FindKClan will return an empty list if there is no k-clan.
- FindKClan[…,k,nspec,All] finds all the k-clans.
- FindKClan works with undirected graphs, directed graphs, multigraphs, and mixed graphs.
Background & Context
- FindKClan finds one or more k-clans in a graph, returning them as a list of vertices. Here, a k-clan is a k-clique such that the graph diameter (i.e. the length of the longest possible path between two vertices) of the subgraph induced by the vertices is at most k. k-clans are used in project selection, pattern matching, finance, and network analysis.
- In contrast, FindKClique can be used to find k-cliques of different subgraph diameter, 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 subgraph diameter, a specified number of cliques, or all.
- 1-clans are cliques. All k-clans are k-clubs and k-cliques, but the converse is not always true. Related functions include FindClique, FindKClique, FindKClub, and FindKPlex.
Examples
open all close allBasic Examples (2)
Scope (14)
Specification (8)
FindKClan works with undirected graphs:
FindKClan[[image], 2]FindKClan[[image], 2]FindKClan[[image], 2]FindKClan[[image], 2]FindKClan[[image], 2]Table[FindKClan[[image], k], {k, 1, 4}]Use rules to specify the graph:
FindKClan[{1 -> 2, 1 -> 5, 2 -> 3, 3 -> 4, 4 -> 5, 3 -> 6, 4 -> 6, 6 -> 3, 6 -> 4, 4 -> 3}, 2]FindKClan works with large graphs:
g = RandomGraph[{10000, 10000}];FindKClan[g, 2]//TimingEnumeration (6)
A 2-clan containing exactly 4 vertices:
FindKClan[[image], 2, {4}]A 2-clan containing at most 4 vertices:
FindKClan[[image], 2, 4]A 2-clan containing between 3 and 5 vertices:
FindKClan[[image], 2, {3, 5}]A largest 2-clan that includes a given vertex:
FindKClan[{[image], 6}, 2]FindKClan[[image], 2, Infinity, All]FindKClan gives an empty list if there is no clan:
FindKClan[[image], 2, {3}]Applications (1)
Properties & Relations (8)
Compute k-clans using FindKClique:
g = [image];Select[FindKClique[g, 2, Infinity, All], GraphDiameter[Subgraph[g, #]] ≤ 2&]FindKClan[g, 2, Infinity, All]g = [image];FindKClan[g, 1]CompleteGraphQ[g, First[%]]A complete graph is a maximum k-clan:
CompleteGraph[10]FindKClan[%, 2]A star graph is a maximum 2-clan:
StarGraph[10]FindKClan[%, 2]The (k-1)-clan is contained in a k-clique:
g = [image];FindKClan[g, 1]FindKClique[g, 2, Infinity, All]All k-clans are k-cliques. The converse is not always true:
g = [image];FindKClan[g, 2, Infinity, All]FindKClique[g, 2, Infinity, All]g = [image];FindKClan[g, 2, Infinity, All]FindKClub[g, 2]The converse is not always true:
FindKClub[{g, 6}, 2]FindKClan[{g, 6}, 2, 6, All]Find a largest 2-clan that includes a given vertex:
g = [image];FindKClan[{g, 6}, 2]Compare with 2-clique, 2-club, and 2-plex:
FindKClique[{g, 6}, 2]FindKClub[{g, 6}, 2]FindKPlex[{g, 6}, 2]Text
Wolfram Research (2012), FindKClan, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKClan.html (updated 2015).
CMS
Wolfram Language. 2012. "FindKClan." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindKClan.html.
APA
Wolfram Language. (2012). FindKClan. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindKClan.html