WOLFRAM

Wolfram Language & System Documentation Center

FindKClub[g,k]

finds a largest k-club in the graph g.

Details
Details and Options Details and Options
Background & Context
Examples  
Basic Examples  
Scope  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

FindKClub

FindKClub[g,k]

finds a largest k-club in the graph g.

Details

  • A k-club is a maximal set of vertices where the diameter of the corresponding subgraph is at most k.
  • FindKClub returns a list of k-clubs.
  • FindKClub will return an empty list if there is no k-club.
  • FindKClub works with undirected graphs and multigraphs.

Background & Context

  • FindKClub finds one or more largest k-clubs in a graph, returning them as a list of vertices. Here, a k-club is a maximal set of vertices for which the 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-clubs 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).
  • 1-clubs are cliques. While all k-clans are k-clubs, the converse is not always true. However, a k-club is always contained in a k-clique. Related functions include FindClique, FindKClan, FindKClique, and FindKPlex.

Examples

open all close all

Basic Examples  (1)

Find a largest 2-club in a graph:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClub[g, 2]

Show the 2-club:

Wolfram Language code: HighlightGraph[g, Subgraph[g, %], GraphHighlightStyle -> "Thick"]

Scope  (3)

FindKClub works with undirected graphs:

Wolfram Language code: FindKClub[[image], 2]

Multigraphs:

Wolfram Language code: FindKClub[[image], 2]

A largest 2-club that includes a given vertex:

Wolfram Language code: FindKClub[{[image], 6}, 2]

Applications  (1)

A friendship network between members of a karate club. Find the largest group of people who are friends or a friend of a friend within the group:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}]
Wolfram Language code: FindKClub[g, 2]

Properties & Relations  (6)

1-club is a clique:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClub[g, 1]
Wolfram Language code: CompleteGraphQ[g, First[%]]

All k-clubs of a complete graph g are exactly the vertex list of g:

Wolfram Language code: g = CompleteGraph[10]
Wolfram Language code: Table[FindKClub[g, k], {k, 1, 4}]

A (k-1)-club is contained in a k-club:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClub[g, 1]
Wolfram Language code: FindKClub[{g, 6}, 2]

A k-club is contained in a k-clique:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClub[g, 2]
Wolfram Language code: FindKClique[g, 2]

The converse is not always true:

Wolfram Language code: FindKClique[{g, 6}, 2]
Wolfram Language code: GraphDiameter[Subgraph[g, %]]

All k-clans are k-clubs:

Wolfram Language code: g = [image];
Wolfram Language code: FindKClan[g, 2, Infinity, All]
Wolfram Language code: FindKClub[g, 2]

The converse is not always true:

Wolfram Language code: FindKClub[{g, 6}, 2]
Wolfram Language code: FindKClan[{g, 6}, 2, 6, All]

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

Wolfram Language code: g = [image];
Wolfram Language code: FindKClub[{g, 6}, 2]

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

Wolfram Language code: FindKClique[{g, 6}, 2]
Wolfram Language code: FindKClan[{g, 6}, 2]
Wolfram Language code: FindKPlex[{g, 6}, 2]
Wolfram Research (2012), FindKClub, Wolfram Language function, https://reference.wolfram.com/language/ref/FindKClub.html (updated 2014).

Text

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

CMS

Wolfram Language. 2012. "FindKClub." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/FindKClub.html.

APA

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

BibTeX

@misc{reference.wolfram_2026_findkclub, author="Wolfram Research", title="{FindKClub}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/FindKClub.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_findkclub, organization={Wolfram Research}, title={FindKClub}, year={2014}, url={https://reference.wolfram.com/language/ref/FindKClub.html}, note=[Accessed: 13-June-2026]}