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

Basic Examples  (1)

Find a largest 2-club in a graph:

Show the 2-club:

Scope  (3)

FindKClub works with undirected graphs:

Multigraphs:

A largest 2-club that includes a given vertex:

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:

Properties & Relations  (6)

1-club is a clique:

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

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

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

The converse is not always true:

All k-clans are k-clubs:

The converse is not always true:

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

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

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_2024_findkclub, author="Wolfram Research", title="{FindKClub}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/FindKClub.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findkclub, organization={Wolfram Research}, title={FindKClub}, year={2014}, url={https://reference.wolfram.com/language/ref/FindKClub.html}, note=[Accessed: 18-November-2024 ]}