Кластеризация Java Jung Graph возвращает неинтуитивные кластеры - PullRequest
Новая
       47

Кластеризация Java Jung Graph возвращает неинтуитивные кластеры

0 голосов
/ 31 октября 2018

Я хочу выполнить некоторую кластеризацию графов, и, поскольку я в значительной степени привязан к Java, решил попробовать java-пакет Jung. В качестве простого графа я создаю два кластера каждой из 5 вершин, которые взаимосвязаны. Я соединяю оба кластера, используя один край. Я ожидаю, что после кластеризации графа будет получено 2 кластера обоих размеров, но я получу разные результаты. Это код: 

import edu.uci.ics.jung.algorithms.cluster.VoltageClusterer;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.SparseGraph;
import java.io.IOException;
import java.util.Collection;
import java.util.Set;

public class CreateGraph {

public static void main(String[] args) throws IOException {

    // Graph<V, E> where V is the type of the vertices
    // and E is the type of the edges
    Graph<Integer, String> g = new SparseGraph<Integer, String>();

    for (int i = 0; i < 5; i++) {
        g.addVertex((Integer) i);
    }

    for (int i = 0; i < 5; i++) {
        for (int ii = 0; ii < 5; ii++) {
            if (i != ii) {
                g.addEdge("EdgeA-" + i + ii, i, ii);
            }
        }
    }
    // cluster 2
    for (int i = 5; i < 10; i++) {
        g.addVertex((Integer) i);
    }

    for (int i = 5; i < 10; i++) {
        for (int ii = 5; ii < 10; ii++) {
            if (i != ii) {
                g.addEdge("EdgeB-" + i + ii, i, ii);
            }
        }
    }
    System.out.println(g.toString());

    g.addEdge("Edge-connector", 1, 5);

    System.out.println("Creating voltageclusterer");

    VoltageClusterer<Integer, String> vc = new VoltageClusterer<Integer, String>(g, 2);

    Collection<Set<Integer>> clusters = vc.cluster(2);

    for (Set<Integer> s : clusters) {
        System.out.println("set is " + s.size());
        for (Integer ss : s) {
            System.out.println("Element " + ss);
        }
    }
}
 }

и вывод: +

  1. набор 1

    • Элемент 8

  2. набор 9

    • Элемент 0
    • Элемент 1
    • Элемент 2
    • Элемент 3
    • Элемент 4
    • Элемент 5
    • Элемент 6
    • Элемент 7
    • Элемент 9

Кто-нибудь есть идеи? (предложения относительно других подходов также приветствуются, если они есть в Java).

1 Ответ

0 голосов
/ 04 ноября 2018

VoltageClusterer имеет случайный элемент: в зависимости от того, как кидаются кости (и сколько раз вы их бросаете - см. Ниже), иногда полученный вами ответ будет довольно странным, как это было в этом случае. Вы можете указать случайное семя, используя setRandomSeed().

Причина, по которой вы столкнулись с этой проблемой, заключается в том, что Javadoc для конструктора VoltageClusterer неверен: передаваемый числовой параметр не является числом кластеров; это число случайных выборок , которые генерируются. Извини за это; мы исправим это.

Вы почти наверняка хотите использовать больше случайных выборок, чем 2.

Другие алгоритмы кластеризации, для которых JUNG имеет реализации, являются детерминированными. EdgeBetweennessClusterer, в частности, разделит график так, как вы ожидаете, если вы скажете ему удалить одно ребро.

...