Random Graph
Random Graph
Gossip Algorithms over Different Network Topologies
Gossip Algorithms over Different Network Topologies
A brief description of three different gossip algorithms (probabilistic broadcast, probabilistic edge and fixed fanout) with detailed examples on how do they work over different network topologies (Erdős–Rényi, random geometric graph and scale free).
June 20, 2017—Daniele Baschieri
Gossip algorithms are a system of machine-to-machine communication whose goal is to minimize channel usage and maximize the coverage of a network. The network can be seen as graph of nodes. Nodes represent computers, and edges represent connections.
An example of a random graph:
In[]:=
randomGraph=RandomGraph[{8,20}]
Out[]=
A pure broadcast mechanism sends the message to all the other nodes connected with the source. This method leads to a complete coverage of the message in the graph, but on the other hand causes saturation of the channel.
The source of the message is in red, with mail on the involved edges:
In[]:=
SetPropertySetProperty{randomGraph,EdgeList[randomGraph,1_]},EdgeLabels
,1,VertexStyleRed
Out[]=
Symbols and Functions
Symbols and Functions
Probabilistic Broadcast
Probabilistic Broadcast
Probabilistic Edge
Probabilistic Edge
Fixed Fanout
Fixed Fanout
Erdős–Rényi or Bernoulli Graph
Erdős–Rényi or Bernoulli Graph
Random Geometric Graph
Random Geometric Graph
Example of a Random Geometric Graph
Example of a Random Geometric Graph
Scale-Free Graph
Scale-Free Graph
Example of a Scale-Free Graph
Example of a Scale-Free Graph
Comparison between the Graph Topologies
Comparison between the Graph Topologies
Conclusion
Conclusion
FURTHER EXPLORATIONS
Graph Theory
Social Network
Torrent and Peer-to-Peer
Routing
AUTHORSHIP INFORMATION
Daniele Baschieri
6/20/17