Details

Autor(en) / Beteiligte

• Castelli, Mauro
• Dondi, Riccardo
• Manzoni, Sara
• Mauri, Giancarlo
• Zoppis, Italo

Titel

Top k 2-Clubs in a Network: A Genetic Algorithm

Ist Teil von

• Computational Science – ICCS 2019, p.656-663

Ort / Verlag

Cham: Springer International Publishing

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• The identification of cohesive communities (dense subgraphs) is a typical task applied to the analysis of social and biological networks. Different definitions of communities have been adopted for particular occurrences. One of these, the 2-club (dense subgraphs with diameter value at most of length 2) has been revealed of interest for applications and theoretical studies. Unfortunately, the identification of 2-clubs is a computationally intractable problem, and the search of approximate solutions (at a reasonable time) is therefore fundamental in many practical areas. In this article, we present a genetic algorithm based heuristic to compute a collection of Top k 2-clubs, i.e., a set composed by the largest k 2-clubs which cover an input graph. In particular, we discuss some preliminary results for synthetic data obtained by sampling Erdös-Rényi random graphs.