Current approaches to community detection in social networks usually neglect nodes, which we call taboo, whose neighborhood does not fit into main memory. In this paper, we model communities as cliques and present a distributed approach that is able to detect maximal cliques in social networks with taboo nodes. Our technique relies on a two-level decomposition algorithm. The first level aims at recursively identifying and isolating tractable portions of the network. The second level further decomposes the tractable portions into small blocks. This process is able to detect all maximal cliques provided that the sparsity of the network is bounded, as it happens in real-world social networks.

Conte, A., DE VIRGILIO, R., Maccioni, A., Patrignani, M., Torlone, R. (2016). Community detection in social networks: Breaking the taboos. In Proceedings of the 24th Italian Symposium on Advanced Database Systems, SEBD 2016 (pp.118-125). Sistemi Evoluti per Basi di Dati (SEBD).

Community detection in social networks: Breaking the taboos

Conte, Alessio;DE VIRGILIO, ROBERTO;MACCIONI, ANTONIO;PATRIGNANI, Maurizio;TORLONE, Riccardo
2016-01-01

Abstract

Current approaches to community detection in social networks usually neglect nodes, which we call taboo, whose neighborhood does not fit into main memory. In this paper, we model communities as cliques and present a distributed approach that is able to detect maximal cliques in social networks with taboo nodes. Our technique relies on a two-level decomposition algorithm. The first level aims at recursively identifying and isolating tractable portions of the network. The second level further decomposes the tractable portions into small blocks. This process is able to detect all maximal cliques provided that the sparsity of the network is bounded, as it happens in real-world social networks.
2016
9788896354889
Conte, A., DE VIRGILIO, R., Maccioni, A., Patrignani, M., Torlone, R. (2016). Community detection in social networks: Breaking the taboos. In Proceedings of the 24th Italian Symposium on Advanced Database Systems, SEBD 2016 (pp.118-125). Sistemi Evoluti per Basi di Dati (SEBD).
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/315511
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact