Inspired by the increasing interest in self-organizing social opportunistic networks, we investigate the problem of distributed detection of unknown communities in dynamic random graphs. As a formal framework, we consider the dynamic version of the well-studied Planted Bisection Model dyn-G(n,p,q) where the node set [n] of the network is partitioned into two unknown communities and, at every time step, each possible edge (u,v) is active with probability p if both nodes belong to the same community, while it is active with probability q (with q≪. p) otherwise. We also consider a time-Markovian generalization of this model.We propose a distributed protocol based on the popular Label-Propagation approach and prove that, when the ratio p/q is larger than nb (for an arbitrarily small constant b>0), the protocol finds the right "planted" partition in O(log n) time even when the snapshots of the dynamic graph are sparse and disconnected (i.e., when p=Θ(1/n)).

Clementi, A., DI IANNI, M., Gambosi, G., Natale, E., & Silvestri, R. (2015). Distributed community detection in dynamic graphs. THEORETICAL COMPUTER SCIENCE, 584, 19-41 [10.1016/j.tcs.2014.11.026].

Distributed community detection in dynamic graphs

CLEMENTI, ANDREA;DI IANNI, MIRIAM;GAMBOSI, GIORGIO;
2015

Abstract

Inspired by the increasing interest in self-organizing social opportunistic networks, we investigate the problem of distributed detection of unknown communities in dynamic random graphs. As a formal framework, we consider the dynamic version of the well-studied Planted Bisection Model dyn-G(n,p,q) where the node set [n] of the network is partitioned into two unknown communities and, at every time step, each possible edge (u,v) is active with probability p if both nodes belong to the same community, while it is active with probability q (with q≪. p) otherwise. We also consider a time-Markovian generalization of this model.We propose a distributed protocol based on the popular Label-Propagation approach and prove that, when the ratio p/q is larger than nb (for an arbitrarily small constant b>0), the protocol finds the right "planted" partition in O(log n) time even when the snapshots of the dynamic graph are sparse and disconnected (i.e., when p=Θ(1/n)).
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - Informatica
English
Distributed computing; Dynamic graphs; Social opportunistic networks; Theoretical Computer Science; Computer Science (all)
http://www.journals.elsevier.com/theoretical-computer-science/
Clementi, A., DI IANNI, M., Gambosi, G., Natale, E., & Silvestri, R. (2015). Distributed community detection in dynamic graphs. THEORETICAL COMPUTER SCIENCE, 584, 19-41 [10.1016/j.tcs.2014.11.026].
Clementi, A; DI IANNI, M; Gambosi, G; Natale, E; Silvestri, R
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
TCS-S-13-01048.pdf

accesso solo dalla rete interna

Descrizione: Articolo principale
Licenza: Non specificato
Dimensione 857.53 kB
Formato Adobe PDF
857.53 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/2108/185797
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 14
social impact