Clique covering of large real-world networks

Abstract : The edge clique covering (ecc) problem deals with discovering a set of (possibly overlapping) cliques in a given network, such that each edge is part of at least one of these cliques. We address the ecc problem from an alternative perspective reconsidering the quality of the cliques found, and proposing more structured criteria with respect to the traditional measures such as minimum number of cliques. In the case of real-world networks, having millions of nodes, such as social networks, the possibility of getting a result is constrained to the running time, which should be linear or almost linear in the size of the network. Our algorithm for finding eccs of large networks has linear-time performance in practice, as our experiments show on real-world networks whose number of nodes ranges from thousands to several millions.
Type de document :
Communication dans un congrès
31st Annual ACM Symposium on Applied Computing (SAC 2016), Apr 2016, Pisa, Italy. ACM, pp.1134-1139, 2016, 〈10.1145/2851613.2851816〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01388477
Contributeur : Marie-France Sagot <>
Soumis le : vendredi 16 juin 2017 - 15:31:38
Dernière modification le : mercredi 11 avril 2018 - 01:53:13
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 16:45:06

Fichier

edgeclique.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alessio Conte, Roberto Grossi, Andrea Marino. Clique covering of large real-world networks. 31st Annual ACM Symposium on Applied Computing (SAC 2016), Apr 2016, Pisa, Italy. ACM, pp.1134-1139, 2016, 〈10.1145/2851613.2851816〉. 〈hal-01388477〉

Partager

Métriques

Consultations de la notice

144

Téléchargements de fichiers

31