Distributed Community Detection in Dynamic Graphs

DOI10.1007/978-3-319-03578-9_1zbMATH Open1362.68284arXiv1302.5607OpenAlexW2059665354MaRDI QIDQ2868627FDOQ2868627

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)

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)$).

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)