Random Node-Asynchronous Updates on Graphs

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Random Node-Asynchronous Updates on Graphs

By: 
Oguzhan Teke; Palghat P. Vaidyanathan

This paper introduces a node-asynchronous communication protocol in which an agent in a network wakes up randomly and independently, collects states of its neighbors, updates its own state, and then broadcasts back to its neighbors. This protocol differs from consensus algorithms and it allows distributed computation of an arbitrary eigenvector of the network, in which communication between agents is allowed to be directed. (The graph operator is still required to be a normal matrix). To analyze the scheme, this paper studies a random asynchronous variant of the power iteration. Under this random asynchronous model, an initial signal is proven to converge to an eigenvector of eigenvalue 1 (a fixed point) even in the case of operator having spectral radius larger than unity. The rate of convergence is shown to depend not only on the eigenvalue gap but also on the eigenspace geometry of the operator as well as the amount of asynchronicity of the updates. In particular, the convergence region for the eigenvalues gets larger as the updates get less synchronous. Random asynchronous updates are also interpreted from the graph signal perspective, and it is shown that a non-smooth signal converges to the smoothest signal under the random model. When the eigenvalues are real, second order polynomials are used to achieve convergence to an arbitrary eigenvector of the operator. Using second order polynomials the paper formalizes the node-asynchronous communication model. As an application, the protocol is used to compute the Fiedler vector of a network to achieve autonomous clustering.

SPS on Twitter

  • Join us on Friday, 21 May at 1:00 PM EST when Dr. Amir Asif (York University) shares his journey and the importance… https://t.co/SLJGLI3K8u
  • There's still time to apply for PROGRESS! Visit https://t.co/0h4GgRY1Jr to connect with signal processing leaders a… https://t.co/dQNnkxpv8f
  • This Saturday, 8 May, join the SPS JSS Academy of Technical Education Noida Student Branch Chapter in collaboration… https://t.co/lFVmmVucvG
  • The SPACE Webinar Series continues this Tuesday, 4 May at 10:00 AM Eastern when Dr. Lei Tian presents "Modeling and… https://t.co/9emEVjOInK
  • The second annual IEEE SIGHT Day will take place on 28 April! This year’s theme is “Celebrating 10 years of IEEE SI… https://t.co/V18yEHtJJl

SPS Videos


Signal Processing in Home Assistants

 


Multimedia Forensics


Careers in Signal Processing             

 


Under the Radar