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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationComputational Science. ICCS 2019
Subtitle of host publication19th International Conference, 2019, Proceedings
EditorsJack J. Dongarra, João M.F. Rodrigues, Pedro J.S. Cardoso, Jânio Monteiro, Roberto Lam, Valeria V. Krzhizhanovskaya, Michael H. Lees, Peter M.A. Sloot
PublisherSpringer Verlag
Pages656-663
Number of pages8
Volume5
ISBN (Print)9783030227494
DOIs
Publication statusPublished - 1 Jan 2019
Event19th International Conference on Computational Science, ICCS 2019 - Faro, Portugal
Duration: 12 Jun 201914 Jun 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11540 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Conference on Computational Science, ICCS 2019
CountryPortugal
CityFaro
Period12/06/1914/06/19

Keywords

  • 2-club maximization
  • Community optimization
  • Genetic algorithms
  • Graphs

Fingerprint Dive into the research topics of 'Top k 2-clubs in a network: A genetic algorithm'. Together they form a unique fingerprint.

Cite this