The identification of cohesive communities (dense sub-graphs) 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.

Castelli, M., Dondi, R., Manzoni, S., Mauri, G., Zoppis, I. (2019). Top k 2-clubs in a network: A genetic algorithm. In 19th Int Conf on Computational Science (pp.656-663). Springer Verlag [10.1007/978-3-030-22750-0_63].

Top k 2-clubs in a network: A genetic algorithm

Manzoni S.;Mauri G.;Zoppis I.
2019

Abstract

The identification of cohesive communities (dense sub-graphs) 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.
slide + paper
2-club maximization; Community optimization; Genetic algorithms; Graphs
English
International Conference on Computational Science, ICCS 2019
2019
19th Int Conf on Computational Science
978-3-030-22749-4
2019
11540
656
663
https://www.springer.com/series/558
reserved
Castelli, M., Dondi, R., Manzoni, S., Mauri, G., Zoppis, I. (2019). Top k 2-clubs in a network: A genetic algorithm. In 19th Int Conf on Computational Science (pp.656-663). Springer Verlag [10.1007/978-3-030-22750-0_63].
File in questo prodotto:
File Dimensione Formato  
Castelli2019_Chapter_TopK2-ClubsInANetworKAGeneticA.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 249.69 kB
Formato Adobe PDF
249.69 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/240258
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact