Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Distributed Community Detection in Dynamic Graphs
(Extended Abstract)
verfasst von : Andrea Clementi, Miriam Di Ianni, Giorgio Gambosi, Emanuele Natale, Riccardo Silvestri
Erschienen in: Structural Information and Communication Complexity
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mbox{dyn-}\mathcal{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 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
(log
n
) time even when the snapshots of the dynamic graph are sparse and disconnected (i.e. in the case
p
= Θ(1/
n
)).