Интерпретация ufactor на кластеризации игрушечных графов

Question

Я пытаюсь сделать несбалансированный раздел METIS. Мне не нужно равное количество вершин в каждом кластере (что делается по умолчанию в METIS). Мой график не имеет ограничений, это неориентированный невзвешенный граф. Вот пример игрушечного графа, сгруппированного METIS без ufactor параметр.

Затем я попробовал с разными ufactor и при значении 143, METIS начинает делать ожидаемый кластер, как показано ниже:

Кто-нибудь может истолковать это. В конце концов, я хочу найти способ угадать ufactor от любого несбалансированного и ненаправленного графика, который минимизирует нормализованный разрез без необходимости какого-либо баланса.

Answer 1

Imbalance=1+(ufactor/1000), По умолчанию imbalance=1, Номер вершины в наибольшем кластере

 imbalance*(number of vertex/number of cluster)

Для первого изображения (кластеризация по умолчанию) - номер вершины в крупном кластере.1*(14/2)=7поэтому второй кластер также 14-7=7На втором рисунке (фактор 143)-

imbalance=1+143/1000=1.143

so, 1.143*(14/2)=8.001

Это позволяет наибольшему кластеру иметь 8 вершин.