# FindGraphPartition

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

## Basic Examples(1)

Find a partition of a graph:

Highlight the partition:

## Scope(10)

FindGraphPartition works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Mixed graphs:

Find a k-way partition of a graph:

Find a partition with specified sizes:

Find a partition with specified proportions:

Use rules to specify the graph:

FindGraphPartition works with large graphs:

## Applications(4)

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

Highlight the partitioned mesh:

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

Show the matrix before and after the ordering:

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

Find communities in social networks using graph partitioning:

Highlight the communities:

## Properties & Relations(1)

Use FindGraphCommunities to find communities in a graph:

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_2024_findgraphpartition, author="Wolfram Research", title="{FindGraphPartition}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindGraphPartition.html}", note=[Accessed: 09-September-2024 ]}

#### BibLaTeX

@online{reference.wolfram_2024_findgraphpartition, organization={Wolfram Research}, title={FindGraphPartition}, year={2015}, url={https://reference.wolfram.com/language/ref/FindGraphPartition.html}, note=[Accessed: 09-September-2024 ]}