Ewolucyjna metoda znajdowania struktury „hub & spoke” w grafie ważonym

Streszczenie:
Metoda „hub and spoke” w odniesieniu do grafu ważonego, nieskierowanego, polega na podziale skończonego zbioru jego wierzchołków na rozłączne podzbiory – klastry węzłów typu spoke połączone ze swoimi węzłami nadrzędnymi typu hub. Węzły typu hub powinny tworzyć podgraf silnie połączonych między sobą węzłów. Podział na dwa typy podgrafów może uwzględniać różne kryteria powiązania wierzchołków w wyróżnionych klastrach. W rozpatrywanym w tej pracy przypadku, kryterium podziału definiowane jest w taki sposób, że wierzchołki wchodzące w skład klastrów typu spoke są relatywnie silniej powiązane ze swoimi hubami niż z hubami znajdującymi się w innych klastrach. Powiązanie dotyczy zarówno liczby połączeń między wierzchołkami jak i wag połączeń oraz złożenia tych kryteriów. Rozpatrywane zagadnienie rozwiązywane jest przy użyciu specjalizowanego algorytmu ewolucyjnego.

Słowa kluczowe: Hub and spoke, graf ważony, algorytm ewolucyjny

The evolutionary method of finding hub and spoke structure in the weighted graph

Abstract:
In reference to weighted undirected simple graph, hub and spoke method consists in partitioning finite vertices set on disjunctive subsets – spoke type node clusters connected with their superior hub type nodes. Hubs should constitue subgraph of strongly connected nodes. Partitioning on two subgraph types may take into consideration various kinds connections among nodes in distinguish clusters. In this case partitioning criteria is defined that vertices belonged to the spoke clusters are relatively stronger connected with their hubs than with hubs from another clusters. Connection is related to a number of connections among vertices and to the connections weights also the assumptions of these criteria. Considered issue is solved using specialized ewolutionary algorithm.

Key words: Hub and spoke, weighted graph, ewolutionary algorithm

Zamknij okno