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:

Introduced in 2012
 (9.0)
 |
Updated in 2014
 (10.0)