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 (i) methods for strongly reducing the search space and (ii) efficient techniques for the computation of maximal cliques. Several experiments show that our strategy is effective and is able to increase the size of the networks for which the computation of large k-plexes is feasible from a few hundred to several hundred thousand nodes.

Conte, A., Firmani, D., Mordente, C., Patrignani, M., Torlone, R. (2017). Fast enumeration of large k-Plexes. In 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (pp.115-124). Association for Computing Machinery [10.1145/3097983.3098031].

Fast enumeration of large k-Plexes

Conte Alessio;Firmani Donatella;Mordente Caterina;Patrignani Maurizio;Torlone Riccardo
2017-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 (i) methods for strongly reducing the search space and (ii) efficient techniques for the computation of maximal cliques. Several experiments show that our strategy is effective and is able to increase the size of the networks for which the computation of large k-plexes is feasible from a few hundred to several hundred thousand nodes.
2017
9781450348874
Conte, A., Firmani, D., Mordente, C., Patrignani, M., Torlone, R. (2017). Fast enumeration of large k-Plexes. In 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (pp.115-124). Association for Computing Machinery [10.1145/3097983.3098031].
File in questo prodotto:
File Dimensione Formato  
KDD17.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 1.62 MB
Formato Adobe PDF
1.62 MB Adobe PDF Visualizza/Apri

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/329437
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 44
  • ???jsp.display-item.citation.isi??? 31
social impact