WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

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 allclose all

Basic Examples  (2)Summary of the most common use cases

Find a largest 2-clan in a graph:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-co2cc7
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-gd1l6
Out[2]=2

Show the 2-clan:

In[3]:=3
✖
https://wolfram.com/xid/0puvb41dwu-b7463e
Out[3]=3

Find all 4-clans:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-fsbe1v
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-ch2v1f
Out[2]=2

Scope  (14)Survey of the scope of standard use cases

Specification  (8)

FindKClan works with undirected graphs:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-jt6j3
Out[1]=1

Directed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-gf7u2v
Out[1]=1

Multigraphs:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-15kl6n
Out[1]=1

Mixed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-czvddh
Out[1]=1

Find a largest 2-clan:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-c4jban
Out[1]=1

Find k-clans for arbitrary k:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-ugqya
Out[1]=1

Use rules to specify the graph:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-t96r7
Out[1]=1

FindKClan works with large graphs:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-lkg873
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-eap0s9
Out[2]=2

Enumeration  (6)

A 2-clan containing exactly 4 vertices:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-eygfi
Out[1]=1

A 2-clan containing at most 4 vertices:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-cvu45g
Out[1]=1

A 2-clan containing between 3 and 5 vertices:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-qrclv
Out[1]=1

A largest 2-clan that includes a given vertex:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-ibhxh8
Out[1]=1

Find all 2-clans in a graph:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-n7v6gc
Out[1]=1

FindKClan gives an empty list if there is no clan:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-bmmbtb
Out[1]=1

Applications  (1)Sample problems that can be solved with this function

Highlight all 2-clans of size 5:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-bzuyww
In[9]:=9
✖
https://wolfram.com/xid/0puvb41dwu-f4oa
Out[9]=9

Properties & Relations  (8)Properties of the function, and connections to other functions

Compute k-clans using FindKClique:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-ebwdq5
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-giqa0o
Out[2]=2

All 2-clans:

In[3]:=3
✖
https://wolfram.com/xid/0puvb41dwu-041vz
Out[3]=3

A 1-clan is a clique:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-ctqp1j
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-eiscnm
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0puvb41dwu-em7dv9
Out[3]=3

A complete graph is a maximum k-clan:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-bwz5yn
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-brgzyy
Out[2]=2

A star graph is a maximum 2-clan:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-bxp7of
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-hj3f9m
Out[2]=2

The (k-1)-clan is contained in a k-clique:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-jbgjkc
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-uk5iu
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0puvb41dwu-uv465
Out[3]=3

All k-clans are k-cliques. The converse is not always true:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-e39ewp
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-eprqgz
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0puvb41dwu-bxe7fd
Out[3]=3

All k-clans are k-clubs:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-d5tv18
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-dg6sqm
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0puvb41dwu-lnjyak
Out[3]=3

The converse is not always true:

In[4]:=4
✖
https://wolfram.com/xid/0puvb41dwu-fcosz
Out[4]=4
In[5]:=5
✖
https://wolfram.com/xid/0puvb41dwu-b4ps8u
Out[5]=5

Find a largest 2-clan that includes a given vertex:

In[1]:=1
✖
https://wolfram.com/xid/0puvb41dwu-h5fwg
In[2]:=2
✖
https://wolfram.com/xid/0puvb41dwu-cos5jm
Out[2]=2

Compare with 2-clique, 2-club, and 2-plex:

In[3]:=3
✖
https://wolfram.com/xid/0puvb41dwu-62th8
Out[3]=3
In[4]:=4
✖
https://wolfram.com/xid/0puvb41dwu-sd5jt
Out[4]=4
In[5]:=5
✖
https://wolfram.com/xid/0puvb41dwu-cwvztx
Out[5]=5
Wolfram Research (2012), FindKClan, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKClan.html (updated 2015).
✖
Wolfram Research (2012), FindKClan, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKClan.html (updated 2015).

Text

Wolfram Research (2012), FindKClan, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKClan.html (updated 2015).

✖
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.

✖
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

✖
Wolfram Language. (2012). FindKClan. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindKClan.html

BibTeX

@misc{reference.wolfram_2025_findkclan, author="Wolfram Research", title="{FindKClan}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindKClan.html}", note=[Accessed: 16-April-2025 ]}

✖
@misc{reference.wolfram_2025_findkclan, author="Wolfram Research", title="{FindKClan}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindKClan.html}", note=[Accessed: 16-April-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_findkclan, organization={Wolfram Research}, title={FindKClan}, year={2015}, url={https://reference.wolfram.com/language/ref/FindKClan.html}, note=[Accessed: 16-April-2025 ]}

✖
@online{reference.wolfram_2025_findkclan, organization={Wolfram Research}, title={FindKClan}, year={2015}, url={https://reference.wolfram.com/language/ref/FindKClan.html}, note=[Accessed: 16-April-2025 ]}