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-(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 Algorithm and prove that, when the ratio p/q is larger than n b (for an arbitrarily small constant b > 0), the protocol finds the right “planted” partition in O(logn) time even when the snapshots of the dynamic graph are sparse and disconnected (i.e. in the case p = Θ(1/n)).

Clementi, A., DI IANNI, M., Gambosi, G., Natale, E., & Silvestri, R. (2013). Distributed Community Detection in Dynamic Graphs. In 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013) (pp.--). Springer [10.1007/978-3-319-03578-9_1].

Distributed Community Detection in Dynamic Graphs

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

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-(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 Algorithm and prove that, when the ratio p/q is larger than n b (for an arbitrarily small constant b > 0), the protocol finds the right “planted” partition in O(logn) time even when the snapshots of the dynamic graph are sparse and disconnected (i.e. in the case p = Θ(1/n)).
Structural Information and Communication Complexity - 20th International Colloquium, SIROCCO 2013
Ischia, Italy
2013
20
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
Settore MAT/06 - Probabilita' e Statistica Matematica
English
Distributed Algorithms; Community Detection; Random Graphs
Intervento a convegno
Clementi, A., DI IANNI, M., Gambosi, G., Natale, E., & Silvestri, R. (2013). Distributed Community Detection in Dynamic Graphs. In 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013) (pp.--). Springer [10.1007/978-3-319-03578-9_1].
Clementi, A; DI IANNI, M; Gambosi, G; Natale, E; Silvestri, R
File in questo prodotto:
File Dimensione Formato  
CDGNS13-SIROCCO13.pdf

non disponibili

Licenza: Copyright dell'editore
Dimensione 366.62 kB
Formato Adobe PDF
366.62 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: https://hdl.handle.net/2108/89877
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 14
social impact