Clique Gossiping

By Yang Liu, Bo Li, B.D.O. Anderson, Guodong Shi. 2017

10 citations recorded by the source corpus.

This paper proposes and investigates a framework for clique gossip protocols. As complete subnetworks, the existence of cliques is ubiquitous in various social, computer, and engineering networks. By clique gossiping, nodes interact with each other along a sequence of cliques. Clique-gossip protocols are defined as arbitrary linear node interactions where node states are vectors evolving as linear dynamical systems. Such protocols become clique-gossip averaging algorithms when node states are scalars under averaging rules. We generalize the classical notion of line graph to capture the essential node interaction structure induced by both the underlying network and the specific clique sequence. We prove a fundamental eigenvalue invariance principle for periodic clique-gossip protocols, which implies that any permutation of the clique sequence leads to the same spectrum for the overall state transition when the generalized line graph contains no cycle. We also prove that for a network with <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> nodes, cliques with smaller sizes determined by factors of <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> can always be constructed leading to finite-time convergent clique-gossip averaging algorithms, provided <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is not a prime number. Particularly, such finite-time convergence can be achieved with cliques of equal size <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> if and only if <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is divisible by <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> and they have exactly the same prime factors. A proven fastest finite-time convergent clique-gossip algorithm is constructed for clique-gossiping using size-<inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> cliques. Additionally, the acceleration effects of clique-gossiping are illustrated via numerical examples.

Subfields: Computer Networks and Communications, Public Health, Environmental and Occupational Health

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

  1. Sebastian U. Stich
  2. Martin Jaggi
  3. Anastasia Koloskova
  4. Nicolas Loizou
  5. Sadra Boreiri
  6. Peter Richtárik
  7. Suhas N. Diggavi
  8. Deepesh Data

In Public Health, Environmental and Occupational Health

  1. Nicolas Loizou
  2. Sebastian U. Stich
  3. Martin Jaggi
  4. Anastasia Koloskova
  5. Sadra Boreiri
  6. Peter Richtárik

Citations in the corpus