WOLFRAM

Wolfram Language & System Documentation Center

FindGraphPartition[g]

gives a partition of vertices of the graph g.

FindGraphPartition[g,k]

gives a partition of vertices into k approximately equal-size parts.

FindGraphPartition[g,{n1,…,nk}]

gives a partition of vertices into parts with sizes n1, …, nk.

FindGraphPartition[g,{α1,…,αk}]

gives a partition of vertices into parts with approximate size proportions α1, …, αk.

FindGraphPartition[{vw,…},…]

uses rules vw to specify the graph g.

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

FindGraphPartition

FindGraphPartition[g]

gives a partition of vertices of the graph g.

FindGraphPartition[g,k]

gives a partition of vertices into k approximately equal-size parts.

FindGraphPartition[g,{n1,…,nk}]

gives a partition of vertices into parts with sizes n1, …, nk.

FindGraphPartition[g,{α1,…,αk}]

gives a partition of vertices into parts with approximate size proportions α1, …, αk.

FindGraphPartition[{vw,…},…]

uses rules vw to specify the graph g.

Details

  • FindGraphPartition finds a partition of vertices such that the number of edges having endpoints in different parts is minimized.
  • FindGraphPartition[g] is equivalent to FindGraphPartition[g,2].
  • FindGraphPartition treats graphs as undirected simple graphs.
  • For a weighted graph, FindGraphPartition finds a partition such that the sum of edge weights for edges having endpoints in different parts is minimized.
  • FindGraphPartition[g,{α1,…,αk}] will give a partition where the size of a part is given by the sum of its vertex weights.
  • The partitions are ordered by their length with the largest part first.

Examples

open all close all

Basic Examples  (1)

Find a partition of a graph:

Wolfram Language code: g = Graph[{12, 23, 31, 24, 45, 56, 64}]
Wolfram Language code: FindGraphPartition[g]

Highlight the partition:

Wolfram Language code: HighlightGraph[g, Map[Subgraph[g, #]&, %]]

Scope  (10)

FindGraphPartition works with undirected graphs:

Wolfram Language code: FindGraphPartition[[image]]

Directed graphs:

Wolfram Language code: FindGraphPartition[[image]]

Weighted graphs:

Wolfram Language code: FindGraphPartition[[image]]

Multigraphs:

Wolfram Language code: FindGraphPartition[[image]]

Mixed graphs:

Wolfram Language code: FindGraphPartition[[image]]

Find a k-way partition of a graph:

Wolfram Language code: FindGraphPartition[[image], 3]

Find a partition with specified sizes:

Wolfram Language code: FindGraphPartition[[image], {1, 2, 3}]

Find a partition with specified proportions:

Wolfram Language code: FindGraphPartition[[image], {0.4, 0.6}]

Use rules to specify the graph:

Wolfram Language code: FindGraphPartition[{1 -> 2, 2 -> 3, 3 -> 1, 2 -> 4, 4 -> 5, 5 -> 6, 6 -> 4}]

FindGraphPartition works with large graphs:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "Internet"}];
Wolfram Language code: FindGraphPartition[g]//Short//Timing

Applications  (4)

Partition an irregular mesh over a three-dimensional structure into four parts:

Wolfram Language code: mesh = AdjacencyGraph[Import["LinearAlgebraExamples/Data/can__229.psa"]]
Wolfram Language code: Short[FindGraphPartition[mesh, 4]]

Highlight the partitioned mesh:

Wolfram Language code: HighlightGraph[mesh, Subgraph[mesh, #]& /@ %]

Reorder the matrix into block-diagonal form with the number of off-diagonal elements minimized:

Wolfram Language code: m = (⁠| | | | | | | | | | | | | | | | | | | | | | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |⁠);
Wolfram Language code: ordering = Flatten[FindGraphPartition[AdjacencyGraph[m]]]

Show the matrix before and after the ordering:

Wolfram Language code: Row[{MatrixPlot[m], MatrixPlot[m[[ordering, ordering]]]}, Spacer[50]]

A sponsored search graph with advertisers and phrases as nodes and links from an advertiser to a phrase he bids on:

Wolfram Language code: g = [image];

Find submarkets and groups of advertisers that do most of their spending on a group of query phrases:

Wolfram Language code: FindGraphPartition[g, 3]

Find communities in social networks using graph partitioning:

Wolfram Language code: club = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}]
Wolfram Language code: FindGraphPartition[club, {0.38, 0.62}]

Highlight the communities:

Wolfram Language code: HighlightGraph[club, Subgraph[club, #]& /@ %]

Properties & Relations  (1)

Use FindGraphCommunities to find communities in a graph:

Wolfram Language code: g = RandomGraph[WattsStrogatzGraphDistribution[20, 0.1, 3]];
Wolfram Language code: FindGraphCommunities[g]
Wolfram Research (2012), FindGraphPartition, Wolfram Language function, https://reference.wolfram.com/language/ref/FindGraphPartition.html (updated 2015).

Text

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

CMS

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

APA

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

BibTeX

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

BibLaTeX

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