Select comparison method

I propose METIS (latest version here): https://github.com/KarypisLab/METIS

Load imbalance is prescribed using -ufactor=int

The input file structure is as follows:

7 11 011 = 7 vertices; 11 edges; vertices and edges have weights 4 5 1 3 2 2 1 = (vertex 1); weight 4; connects to vertex 5 edge weight 1; connects to vertex 3 edge weight 2; connects to vertex 2 edge weight 1 2 1 1 3 2 4 1 = (vertex 2); weight 2; connects to vertex 1 edge weight 1; connects to vertex 3 edge weight 2; connects to vertex 4 edge weight 1 ... etc

Output file structure:

Manual here: https://github.com/KarypisLab/METIS/blob/master/manual/manual.pdf (p. 9 for input file details) Example using Python wrapper (we will use bash or C version): https://stackoverflow.com/questions/50667961/which-algorithm-can-be-used-to-partition-graph-to-make-each-partitioned-groupor

Potential install steps: https://stackoverflow.com/questions/73860660/metis-installation-on-google-colab

Note: After a lot of searching, the Python scikit-learn methods don't seem to support weighted vertices: https://scikit-learn.org/stable/auto_examples/cluster/plot_segmentation_toy.html https://scikit-learn.org/stable/modules/generated/sklearn.cluster.SpectralClustering.html https://scikit-learn.org/stable/auto_examples/cluster/plot_coin_segmentation.html#sphx-glr-auto-examples-cluster-plot-coin-segmentation-py

Other inspiration: https://jchiquet.github.io/MAP566/docs/mixture-models/map566-lecture-graph-clustering-part1.html https://home.ttic.edu/~harry/pdf/balanced_partition_journal.pdf

rs59 / q2

Select comparison method #5

of graph vertices

of graph edges

of partitions