Insert
Sample

Gossip Algorithms over different network topologies

A brief description of three different gossip algorithms, Probabilistic Broadcast, Probabilistic Edge, Fixed Fanout, with detailed example on how do they work over different network topologies, Erdős–Rényi, Random Geometric Graph, scale free.

Random Graph

Gossip algorithms are a system of machine-to-machine communication whose goal is to minimize the channel usage and maximise the coverage of the network. Network can be seen as graph of nodes, nodes represent computers and edges represent connections.
◼
Example of a random graph:
In[1]:=
randomGraph=RandomGraph[{8,20}]
Out[1]=
A pure mechanism of broadcast send the message to all the other node connected with the source, this method leads to a complete coverage of the message in the graph but on the other hand cause the saturation of the channel.
◼
In red the source of the message, mails on involved edges
In[2]:=
SetPropertySetProperty{randomGraph,EdgeList[randomGraph,1_]},EdgeLabels
,1,VertexStyleRed
Out[2]=

Symbols and Functions

There are three famous gossip algorithm, their difference is mostly related on how do they choose the node to whom forward the messages. They are named in literature: Probabilistic Broadcast (PB), Probabilistic Edge (PE) e Fixed Fanout (FF).
In order to better understand the algorithms it’s important to introduce some notation
◼
Λ
= set of node adjacent to node i.
In[3]:=
Λ[graph_,i_]:=Map[Last,EdgeList[graph,i_]]​​1Λ[randomGraph,1]​​SetProperty[{SetProperty[randomGraph,VertexLabels"Name"],Λ[randomGraph,1]},VertexStyleYellow]
Out[4]=
1{2,4,5,8}
Out[5]=
◼
V
= cardinality of
Λ
i
In[6]:=
V[graph_,i_]:=Length[Λ[graph,i]]​​V[randomGraph,1]
Out[7]=
4
◼
msg
= the message received
​
p
v
,
p
e
, fanout = probabilistic value related with the algorithm, PB,PE,EF.
​

Probabilistic Broadcast

The first algorithm is Probabilistic Broadcast, the value
p
v
is the threshold that decide if the message will be send in broadcast or dropped from the node i .
◼
example of Probabilistic Broadcast with
p
v
= 0.3
In[8]:=
ProbabilisticBroadcast[graph_,i_,msg_,pv_]:=With[​​{r=RandomReal[]},If[​​r≤pv,​​SetProperty[{SetProperty[{SetProperty[{graph,EdgeList[graph,i_]},EdgeLabelsmsg],i},VertexStyleRed],i},VertexLabels{SetPrecision[r,2]}],​​SetProperty[{SetProperty[{graph,i},VertexStyleRed],i},VertexLabels{SetPrecision[r,2]}]​​]]​​TableProbabilisticBroadcastrandomGraph,1,
,.3,{x,1,10}
Out[9]=

,
,
,
,
,
,
,
,
,


Probabilistic Edge

The second algorithm is Probabilistic Edge, the value
p
e
is the threshold that decide if the message will be send on a specific arc or not, from the node i.
◼
example of edge selection with Probabilistic Edge with
p
e
= 0.3
In[10]:=
GetEdge[graph_,i_,pe_]:=Map[First,Select[Map[With[{r=RandomReal[]≤pe},{#,r}]&,Map[i#&,Λ[graph,1]]],Last[#]True&]]​​GetEdge[randomGraph,1,.3]
Out[11]=
{14,15}
◼
example Probabilistic Edge with
p
e
= 0.4
In[12]:=
Clear[ProbabilisticEdge]​​ProbabilisticEdge[graph_,i_,msg_,pe_]:=​​SetProperty[{SetProperty[{SetProperty[{graph,GetEdge[graph,i,pe]},EdgeLabelsmsg],i},VertexStyleRed],i},VertexLabels{SetPrecision[pe,2]}]​​TableProbabilisticEdgerandomGraph,1,
,.4,{x,1,10}
Out[14]=

,
,
,
,
,
,
,
,
,


Fixed Fanout

The last algorithm is Fixed Fanout the node choose a number of random node connected with him to whom send the message.

Erdős–Rényi or Bernulli graph

The variance of vertex degree represent the variance of number of edge that each node are linked with.
It’s an important parameter that can impact in the spreading of the message a low variance in vertex degree can cause the dropping of a message before the coverage is complete.
The edge connectivity represent the minimum number of edge that should be deleted from a graph to make it disconnected.

Random Geometric Graph

◼
Variance of the vertex degree of a Random Geometric graph
◼
Edge connectivity of a Random Geometric graph

Example of Random Geometric graph

A typical example of Random Geometric graph are rails or highways, they share the same structure due two the fact that nears cities are commonly connected with a path.
◼
An example of highways graph of Italy city:
◼
The vertex degree is strictly related with political or economical influence and also with centrality in the map:
◼
An example of map of Italy highways with names of most connected city:

Scale Free graph

◼
Variance of the vertex degree of a Scale Free graph:
◼
Edge connectivity of a Scale Free graph:

Example of Scale Free graph

◼
Internet is an example of Scale Free graph, here the info.cern.ch hyperlinks network:

Comparison between the graph topology

It’s important to check the comparison between different aspect of each graph.
◼
Comparison of variance of the vertex degree between Erdős–Rényi, Random Geometric, and Scale Free graph:
◼
Comparison of edge connectivity between Erdős–Rényi, Random Geometric, and Scale Free graph
It can be seen in the previous graphs that each network has different behaviour over those important aspects.
Studying the mean of variation of vertex degree it can be understand better which graph has a more peculiar topology with high isolated nodes and cluster.
◼
Random Geometric graph due to its unique topology shuld have the higher Variation of Vertex Degree, followed by Scale Free due to the presence of hub’s nodes, Erdős–Rényi on the other hand has a very low Vertex Degree variation.
It can also be compared the edge connectivity in order to properly understand the fault tolerance of those network and the reliability of the infrastructure.
◼
Scale Free graph do the presence of macro hub and clique has the higher edge connectivity, followed by Erdős–Rényi , and Random Geometric due to the isolated nodes.

Conclusion

Gossip Algorithms could be really useful in situation of network instability where the network topology change really fast, they can also be used to simulate human spreading of information and virus diffusion over population.
Further Explorations
Social Network
Torrent and Peer To Peer
Routing
Authorship information
Daniele Baschieri
20/06/2017
daniele.baschieri@gmail.com