- Tytuł:
- Evolutionary approach to obtain graph covering by densely connected subgraphs
- Autorzy:
-
Stańczak, J.
Potrzebowski, H.
Sęp, K. - Tematy:
-
graph
clique
graph clustering
evolutionary algorithms - Pokaż więcej
- Wydawca:
- Polska Akademia Nauk. Instytut Badań Systemowych PAN
- Powiązania:
- https://bibliotekanauki.pl/articles/206170.pdf Link otwiera się w nowym oknie
- Opis:
- This article describes two evolutionary methods for dividing a graph into densely connected structures. The first method deals with the clustering problem, where the element order plays an important role. This formulation is very useful for a wide range of Decision Support System (DSS) applications. The proposed clustering method consists of two stages. The first is the stage of data matrix reorganization, using a specialized evolutionary algorithm. The second stage is the final clustering step and is performed using a simple clustering method (SCM). The second described method deals with a completely new partitioning algorithm, based on the subgraph structure we call α-clique. The α-clique is a generalization of the clique concept with the introduction of parameter α, which imposes for all vertices of the subgraph the minimal percentage (α*100%) of vertices of this subgraph that must be connected with vertices of this α-clique. Traditional clique is an instance of α-clique with α = 1. Application of this parameter makes it possible to control the degree (or strength) of connections among vertices (nodes) of this subgraph structure. The evolutionary approach is proposed as a method that enables finding separate α-cliques that cover the set of graph vertices.
- Dostawca treści:
- Biblioteka Nauki
Artykuł