DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2020.42

Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model

Authors: Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract

We analyze the binary-state (either ℛ or ℬ) k-majority dynamics in a biased communication model where nodes have some fixed probability p, independent of the dynamics, of being seen in state ℬ by their neighbors. In this setting we study how p, as well as the initial unbalance between the two states, impact on the speed of convergence of the process, identifying sharp phase transitions.

Cite as

Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cruciani_et_al:LIPIcs.DISC.2020.42,
  author =	{Cruciani, Emilio and Mimun, Hlafo Alfie and Quattropani, Matteo and Rizzo, Sara},
  title =	{{Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{42:1--42:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.42},
  URN =		{urn:nbn:de:0030-drops-131200},
  doi =		{10.4230/LIPIcs.DISC.2020.42},
  annote =	{Keywords: Biased Communication, Consensus, Majority Dynamics, Markov Chains, Metastability}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2019.20

Step-By-Step Community Detection in Volume-Regular Graphs

Authors: Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden k partition and characterized by a milder form of volume-regularity. We show that the class of k-volume regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits k "stepwise" eigenvectors (i.e., vectors that are constant over each set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first k eigenvalues and the gap between the k-th and the (k+1)-th eigenvalues is sufficiently large, the Averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.

Cite as

Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo. Step-By-Step Community Detection in Volume-Regular Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:LIPIcs.ISAAC.2019.20,
  author =	{Becchetti, Luca and Cruciani, Emilio and Pasquale, Francesco and Rizzo, Sara},
  title =	{{Step-By-Step Community Detection in Volume-Regular Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.20},
  URN =		{urn:nbn:de:0030-drops-115163},
  doi =		{10.4230/LIPIcs.ISAAC.2019.20},
  annote =	{Keywords: Community detection, Distributed algorithms, Dynamics, Markov chains, Spectral analysis}
}

Search Results

Documents authored by Rizzo, Sara

Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model

Abstract

Cite as

Step-By-Step Community Detection in Volume-Regular Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message