Distributed Community Detection in Dynamic Graphs

DOI10.1007/978-3-319-03578-9_1MaRDI QIDQ2868627zbMATH OpenOpenAlexFDO

Authors Miriam Di Ianni, Giorgio Gambosi, Andrea Clementi, Emanuele Natale, Riccardo Silvestri

Publication date 17 December 2013

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.5607

zbMATH Keywords

distributed computingdynamic graphssocial opportunistic networks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distributed algorithms (68W15)

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 emph{Planted Bisection Model} $sdG(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 emph{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=Theta(1/n)$).

Recommendations

• Distributed community detection in dynamic graphs
• On Detection of Community Structure in Dynamic Social Networks
• A distributed community detection algorithm for large scale networks under stochastic block models
• Dynamic Communities and their Detection
• scientific article; zbMATH DE number 6962251

Cites work

• Algorithms for graph partitioning on the planted partition model
• Community structure in social and biological networks
• Complex networks: structure and dynamics
• Distributed community detection in dynamic graphs
• Flooding time in edge-Markovian dynamic graphs
• On the Analysis of a Label Propagation Algorithm for Community Detection
• Parsimonious flooding in dynamic graphs
• The solution of some random NP-hard problems in polynomial expected time

Cited in

(11)

• An efficient generator for clustered dynamic random networks
• Average whenever you meet: opportunistic protocols for community detection
• Eigenvector Computation and Community Detection in Asynchronous Gossip Models
• Min-max communities in graphs: complexity and computational properties
• Distributed community detection in dynamic graphs
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Dynamic community detection based on network structural perturbation and topological similarity
• scientific article; zbMATH DE number 6962251 (Why is no real title available?)
• On Detection of Community Structure in Dynamic Social Networks
• Find your place: simple distributed algorithms for community detection
• Joint Community and Anomaly Tracking in Dynamic Networks

This page was built for publication: Distributed Community Detection in Dynamic Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868627)