k-plexes are a formal yet flexible way of defining communities in networks. They generalize the notion of cliques and are more appropriate in most real cases: while a node of a clique C is connected to all other nodes of C, a node of a k-plex may miss up to k connections. Unfortunately, computing all maximal k-plexes is a gruesome task and state-of-the-art algorithms can only process small-size networks. In this paper we propose a new approach for enumerating large k-plexes in networks that speeds up the search by several orders of magnitude, leveraging on efficient techniques for the computation of maximal cliques.

Conte, A., Firmani, D., Mordente, C., Patrignani, M., Torlone, R. (2018). Cliques are Too Strict for Representing Communities: Finding Large k-plexes in Real Networks. In 26th Italian Symposium on Advanced Database Systems (SEBD). CEUR-WS.

Cliques are Too Strict for Representing Communities: Finding Large k-plexes in Real Networks

Conte Alessio;Firmani Donatella;Mordente Caterina;Patrignani Maurizio;Torlone Riccardo
2018-01-01

Abstract

k-plexes are a formal yet flexible way of defining communities in networks. They generalize the notion of cliques and are more appropriate in most real cases: while a node of a clique C is connected to all other nodes of C, a node of a k-plex may miss up to k connections. Unfortunately, computing all maximal k-plexes is a gruesome task and state-of-the-art algorithms can only process small-size networks. In this paper we propose a new approach for enumerating large k-plexes in networks that speeds up the search by several orders of magnitude, leveraging on efficient techniques for the computation of maximal cliques.
2018
Conte, A., Firmani, D., Mordente, C., Patrignani, M., Torlone, R. (2018). Cliques are Too Strict for Representing Communities: Finding Large k-plexes in Real Networks. In 26th Italian Symposium on Advanced Database Systems (SEBD). CEUR-WS.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11590/355757
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact