Free online reading

Algorithm for Achieving Consensus Over Conflicting

Rumors: Convergence Analysis and Applications

Ismail Elouafiq,

*Student Member, IEEE*, Amine Semma,*Student Member, IEEE*,

**Abstract**--Motivated by the large expansion in the study of**social networks, this paper deals with the problem of multiple**

**messages spreading over the same network using gossip**

**algorithms. Given two messages distributed over some nodes of**

**the graph, we first investigate the final distribution of the**

**messages given an initial state. Then, an algorithm is presented to**

**achieve consensus over one of the messages. Finally, a game**

**theoretical application and an analogy with word-of-mouth**

**marketing are outlined.**

**Index Terms**--Gossip algorithms, consensus, social networks,**game theory, word-of-mouth.**

I. I

NTRODUCTION

In recent years, large decentralized distributed systems such

as sensor and wireless networks require the design of

communication schemes that satisfy scalability, robustness and

graceful degradation. Consequently, information dissemination

and message spreading algorithms have generated a huge

interest.

The problem of broadcasting may be defined as spreading

some information over a graph that is unknown to its nodes.

Gossip algorithms are a set of algorithms that are used to solve

such problems.

*Randomized**gossip*is one of the most widelyused forms of gossip that have gained prominence for the

simplicity of its protocol. In a random gossip based algorithm,

nodes repeatedly call a random neighbor to transfer their

messages. At the end of the process, the information should be

spread across the network structure for the algorithm to

converge.

In this paper, based on gossip algorithms we investigate the

spreading of rumors over a social network. We will start by

describing the case of two conflicting messages spreading by

considering an algorithm that has already been proposed in

literature [1]. Given a state of the graph where the two

messages are held by some of the nodes, we analyze the final

state of the graph based on a deterministic model based on the

expectation of a Markov Chain. After the two messages are

spread over the network a consensus could be achieved over

one of the two messages. For that reason, a simple and efficient

consensus-based algorithm is proposed to attain this goal.

One other important aspect of gossip algorithms is their

ability to model human behavior. For instance, in a social

network where the agents are assumed to make rational

decisions these agents base their belief choices on likelihood

criteria. For this reason, we decided to investigate the use of

the consensus-based gossip algorithm in game theory, more

precisely in a voting scenario where multiple agents act

according to their local knowledge. Based on that scenario, we

propose an application of gossip algorithms in modeling the

Word of Mouth (WoM ) marketing strategy where customers

contribute in the marketing strategy of a given product or

service.

The rest of this paper is organized as follows. In Section II,

a protocol modeling the case of two messages being forwarded

over the same network is proposed and analyzed. Then, an

algorithm for achieving consensus over two spread messages is

described in Section III. Section IV provides two different

applications of gossip algorithms, one in game theory and the

other in marketing . Finally, we finish with some conclusions

and future directions in Section VII.

II. T

WO

C

ONFLICTING

R

UMORS

S

PREADING

OVER

THE

S

AME

N

ETWORK

We investigate the problem of spreading two conflicting

messages

*m1*and*m2*on a social network.For concreteness, let us begin with a review of a message

spreading algorithm. In a social network, represented by a

graph, informed nodes aim at sending their message to their

neighbors. We propose an asynchronous gossip based model.

At each round, a node

*i*is chosen at random over the network.If

*i*is holding one of the two messages, i selects a neighbor*j*uniformly at random and informs it. We point out that this

approach does not give a realistic representation of the problem

since a node may lose interest in spreading the message if it

tries to inform another node already knowing it.

**To tackle this**issue, we propose to study a different model proposed in [1].

*A. Algorithm description :*

Let

*G=(V,E)*be a complete graph where*|V|=n*and*E=V*x

*V*

and let

*l*be a positive integer*l IN**. The algorithm proceeds as*

*follows :*

*In the beginning, two subsets of*

*V*,*I*

*1**and*

*I*

*2*

*,*are*respectively informed by*

*m1*and*m2*. At each round :*·*

*A node*

*i*is chosen at random over*V*. if*i*holds a*message :*

*i*chooses uniformly at random a neighbor*j*with a*probability*

*1/(n-1)*.*If node*

*j*doesn't have the message (*susceptible*

*node*), node*i*informs it (*j*becomes an m1

*infective**node*). Else,*i*increments a counter*C*

*i**with one (*

*C*

*i**counts the unnecessary calls made*

*by*

*i*, their initial value is 0).*If*

*C*

*i*

*=l*, node*i*stops spreading the message and*becomes a removed node.*

*To start, we will assume that l=1. According to the*

*algorithm description, nodes can be in one of the five following*

*states:*

*·*

*State*1: Has (*m1*) and is spreading it "*m1 infective*".*·*

*State*2: Has (*m2*) and is spreading it "*m2 infective*".*·*

*State*3: Has (*m1*) and stopped spreading it "*m1*

*removed*".*·*

*State*4: Has (*m2*) and stopped spreading it "*m2*

*removed*".*·*

*State*5: Doesn't have a message "*susceptible*"*Following these five states, at each step*

*k*let*I1(k), I2(k),*

*S(k), R1(k)*and*R2(k)*denotes number of nodes in state 1, 2, 3,*4 and 5 respectively.*

*B. Markov Chain Model**If we denote by*

*X(k)*the vector*(I1(k), I2(k), S(k), R1(k),*

*R2(k))*

*T**, the communication step depends only on*

*X(k)*the state*of the nodes at*

*k*, thus*X(k+1)*depends only on*X(k)*. The*process can then be modeled with a DTMC*

*(Discrete Time**Markov Chain).*

*Let us compute its transitions probabilities. Actually, given*

*a state S(k), there are 5 possible transitions :*

*·*

*p*

*0*

*(k)=Pr(X(k)(I(k)+1, I2(k), Y(k)-1, R1(k), R2(k)))*

*p**0*

*(*

*k*)=

*S*(*k*)+*R1*(*k*)+*R2*(*k*)

*N**(1)*

*·*

*p*

*1*

*+*

*(k)=Pr(X(k)(I1(k)+1, I2(k), Y(k)-1,R1(k),R2(k)))*

*p**+(*

*k*)*1*

*=*

*I1*(*k*)*. S*(*k*)

*N*(*N*-1)*(2)*

*·*

*p*

*1*

*-*

*(k)=Pr(X(k)(I1(k)-1, I2(k), Y(k), R1(k)+1,R2(k)))*

*p**+(*

*k*)*1*

*=*

*I1*(*k*)*.*(*N*-*S*(*k*))

*N*(*N*-1)*(3)*

*·*

*p*

*2*

*+*

*(k)=Pr(X(k)(I(k), I2(k)+1, Y(k)-1, R1(k), R2(k)))*

*p**+(*

*k*)*2*

*=*

*I2*(*k*)*. S*(*k*)

*N*(*N*-1)*(4)*

*·*

*p*

*2*

*-*

*(k)=Pr(X(k)(I(k), I2(k)-1, Y(k), R1(k), R2(k)+1))*

*p**+(*

*k*)*2*

*=*

*I2*(*k*)*.*(*N*-*S*(*k*))

*N*(*N*-1)*(5)*

*C. Deterministic model**The*

*DTMC*introduced above is reducible and transient as*states of the form*

*(0, 0, j, r1)*are absorbing states. In order to*have a steady-state distribution, the first*

*DTMC*is modified as*follows: Given an initial state*

*(n1, n2, n-n1-n2, 0)*, and for any

*j*and*r1 = n1*,*p0, 0, j, r1(n1, n2, N-n1-n2, 0) = 1*.*However, the computation of its steady-state has a high*

*complexity and so we will compute its conditional expectation*

*and then deduce a deterministic model.*

*The expectation calculi give :*

*E*[*I1*(*k*+ 1)*I1*(*k*)]=*I1*(*k*)+

*I1*(*k*). (2.S(*k*)-*N*)

*N*(*N*-1)*(6)*

*E*[*I2*(*k*+1)*I2*(*k*)]=*I2*(*k*)+

*I2*(*k*)*.*(2.S (*k*)-*N*)

*N*(*N*-1)*(7)*

*E*[*S*(*k*+1)*S*(*k*)]=*S*(*k*)-

*S*(*k*)*.*(*I1*(*k*)+*I2*(*k*))

*N*(*N*-1)*(8)*

*E*[*R1*(*k*+1)*R1*(*k*)]=*R1*(*k*)+

*I1*(*k*)*.*(*N*-*S*(*k*))

*N*(*N*-1)*(9)*

*E*[*R2*(*k*+1)*R2*(*k*)]=*R2*(*k*)+

*I2*(*k*)*.*(*N*-*S*(*k*))

*N*(*N*-1)*(10)*

*Thus, if we denote by*

*i1, i2, s, r1*and*r2*respectively*"*

*infective m1", "infective m2", "susceptible", "removed m1"**and*

*"removed m2"*nodes,and using (6), (7), (8), (9), (10) and*the two assumptions:*

*·*

*N~N-1*for high*N**·*

*Time intervals between the Poisson clock ticks is*

*neglected (*

*i.e.:**k=t*).*A deterministic model is deduced :*

*di1*(*t*)

*dt**=*

*i1*(*t*)(2s(*t*)-1) (11)

*di2*(*t*)

*dt**=*

*i2*(*t*)(2s(*t*)-1) (12)

*ds*(*t*)

*dt**=-*

*s*(*t*)(*i1*(*t*)+*i2*(*t*)) (13)

*dr1*(*t*)

*dt**=*

*i1*(*t*)(1-*s*(*t*)) (14)

*dr2*(*t*)

*dt**=*

*i2*(*t*)(1-*s*(*t*)) (15)*Furthermore, we can note that :*

*di1*(*t*)

*di2*(*t*)*=*

*i1*(*t*)

*i2*(*t*)*and*

*dr1*(*t*)

*dr2*(*t*)*=*

*i1*(*t*)

*i2*(*t*)*(16)*

*which gives an interesting relation between*

*i1(t)*and*i2(t)*,*r1(t)**and*

*r2(t)*:

*i1*(*t*)=

*i1*( 0)

*i1*(0)+*i2*(0)

*. i*(*t*) (17)

*r1*(*t*)=

*i1*(0)

*i1*( 0)+*i2*(0)

*. r*(*t*) (18)*where*

*i*(t)=*i1(t)+i2(t)*and*r(t)=r1(t)+r2(t).**As a consequence, the problem is reduced to one message*

*spreading over a social network. Then, we reduce (11), (12),*

*(13), (14) and (15) to two equations. Moreover, in [3], it is*

*showed that even if*

*l**1*equations still hold by adding a*multiplying coefficient*

*1/l*. Let*s, i*and*r*denote respectively*the fractions of susceptible, infective, and removed individuals,*

*such that*

*s + i + r = 1*:

*ds*(*t*)

*dt**=-*

*si*(19)

*di*(*t*)

*dt**=*

*si*+*1*

*l**(*

*1-*

*s*)*i*(20)*The solution of this couple of equations is [3]:*

*i*(*s*)=*l*+1

*l**(*

*1-*

*s*)+ 1

*l**log(*

*s*) (21)*This gives us a first indication on how*

*i*changes with*s*(Figure*1).*

*The algorithm stops when all the infective nodes stop*

*spreading the message,*

*i.e:**i = 0*. According to equation (21),

*i(s)*is zero when :

*s*=exp(-(*l*+1)(1-*s*)) (22)*Which gives an implicit solution of the equation. Here are*

*some theoretical results for the reach (number of nodes that*

*end by having the message) given two different values of k :*

*- For*

*l=1, s=20%.**- For*

*l=2, s=6%.**When in the final state, we can deduce easily*

*r1*and*r2*by*multiplying*

*r*by the initial coefficient respectively i1*(0)/i(0)**and*

*i2(0)/i(0)*.

*D. Simulation results:**The first simulation ( Figure 1) shows the evolution of*

*i*as*a function of*

*s*for different*l*values. We can note that as the*value of*

*l*increases the curve gets closer to a linear shape.*This is justified by the fact that (21) becomes*

*i=1-s*which is*in fact a linear function. Moreover, the plot of the theoretical*

*curve fits the simulation results when*

*l*=1 which validates the*deterministic model.*

*Then, using the Monte Carlo method, the simulation*

*results in Figure 2 were obtained. Figure 2 shows the mean of*

*the difference between the two messages sets cardinalities as a*

*function of the initial difference. We can note the linear shape*

*of the curve as expected with the deterministic model in the*

*last section.*

*E. Multiple messages**In the case of multiple messages, we assume that we are*

*concerned by only one of these messages and the rest are*

*considered as disrupting messages. Hence, the problem can be*

*reduced to a two conflicting messages spreading over the same*

*network (one for the valid message and the other englobing all*

*the adversary messages). All the results presented in this*

*section could be applied.*

*III. C*

*ONSENSUS*

*OVER*

*TWO*

*DIFFUSED*

*MESSAGES*

*We assume that the initial state of the graph is as follows :*

*-*

*n1*nodes received message (*g1*).*-*

*n2*nodes received message (*g2*).*- All the nodes received a message :*

*n1 + n2 = n*.*Then, we want all the nodes to agree on one of the*

*messages. We start by considering an asynchronous algorithm*

*that uses two increasing counters and we show that it is*

*equivalent to a seemingly simpler algorithm that only uses one*

*counter averaged at each step.*

*First, we assume that each node*

*i*holds two counters for*received messages (a counter*

*C*

*i**for the messages*

*corresponding to his own message, and a second counter*

*C'*

*i**for*

*those corresponding to the other message).*

*All the counters start by a value of zero. At each step*

*k*, a*randomly chosen node*

*i*is woken up. Then, a neighbor*j*is*chosen uniformly at random. Both nodes exchange messages*

*and counters, then update their counters as follows :*

*- if the received message is different from the held*

*message, its counter is incremented by the value of the*

*received counter (*

*C'*

*i*

*(k+1)=C'*

*j*

*(k+1)=C'*

*i*

*(k)+C*

*'j*

*(k*)). The new*message is stored.*

**Fig. 1**Infective nodes ratio as a function of susceptible nodes*ratio (Theoretical result for l= 1 and simulation results for*

*l=1,2,4,5)*

**Fig. 2**Mean of the difference between the two messages sets*as a function of the initial difference : comparison between*

*simulation and theoretical results (n=5000 and n1+n2=200).*

*- if the received message corresponds to the held message,*

*the counter corresponding to the held message is incremented*

*by the value of the received counter (*

*C*

*j*

*(k+1)=C*

*i*

*(k+1)=C*

*i*

*(k)*

*+C*

*j*

*(k)*).*For a node*

*i*at step*k*, to choose the most relevant message,

*i*simply compares his two counters. Comparing the counters is*equivalent to subtracting the value of*

*C'*

*i**from that of*

*C*

*i**.*

*Thus we propose the following algorithm to study. We give*

*to each node*

*i*a counter*C*

*i*

*and proceed by averaging the**counters to achieve consensus as described below.*

*A. Algorithm description :**Initialization step :*

*for*

*i*in {*1,..,n*}

*C*

*i**=*

*{*

*1,*

*if iholds*(*g1*)*-*

*1,*

*if iholds*(*g2*)*}*

*Communication step :*

*At the rate of a Poisson process (step*

*k*) , for each node*i*:*-*

*i*wakes up.*-*

*i*chooses a neighbor*j*uniformly at random.*- Both nodes update their counters :*

*C*

*j*

*(k+1)=C*

*i*

*(k+1)=(1/2)( C*

*i*

*(k)+C*

*j*

*(k))**- Both*

*i*and*j*sleep.

*B. Convergence analysis :**In this section, we will study the convergence of the*

*randomized gossip algorithm. In the algorithm described above*

*nodes proceed by updating their local counter at each step. Let*

*N**i*

*be the set of*

*i'*s neighbors,*n**i*

*=|*

*N**i*

*| the number of*

*i*'s neighbors*and*

*C*(*k*) the vector for which entries are the counters*C**i*

*(*

*k*) at*each time slot*

*k*. Thus, the update can be modeled linearly by*the following equation:*

*C*(*k*+1)=*W*(*k*).*C*(*k*) (23)*where, when node*

*i*chooses node*j*from*N*

*i**:*

*W*(*k*)=*I*-*(*

*e*

*i**-*

*e*

*j**)(*

*e*

*i**-*

*e*

*j**)*

*T**2*

*(24)*

*with probability*

*1*

*n.n*

*i**, where*

*e*

*i**is an*

*n x 1*unit vector with*the*

*i*

*th**component equal to one.*

*W (k)*must satisfy some constraints according to [2]. These*constraints are imposed by the gossip algorithm and the graph*

*topology.*

*If nodes*

*i*and*j*are not neighbors,*W*

*ij*

*(k)*must be zero.*Further, since every node can communicate with only one of its*

*neighbors per time slot, each column of*

*W (k)*can have only*one non-zero entry other than the diagonal entry.*

*In each iteration, the averaging computation impose the*

*preservation of the sums : this means that*

*1*

*T*

*.W (k) =***1**

*T**, where*

*denotes the vector of all ones. Also, the vector of averages***1***must be a fixed point of the iteration,*

*i.e*.*W (k).*.**1**=**1***Since the choice of*

*i*and*j*are independent of the time slot,

*W(k)*matrices are*IID*. Secondly, from (23), we can find by*iteration that :*

*C*(*k*)=(

*l*=0

*l*=*k*-1

*W*(*l*))*. C*( 0)=*P*(*k*-1)*. C*(0) (25)*Hence, if*

*C(k)*must converge to*C*

*ave*

*.*we must have :**1***lim*

*k*

*P*(*k*)=**1.1**

**T**

*n**(26)*

*In the next sections, the convergence to the initial counters*

*mean will be proven.*

*1) Convergence in expectation:**Let*

*W = E[W(k)]*. Under the following conditions :*(a1)-*

*1*

*T*

*.W =***1**

*T**(a2)*

*- W .***1**=**1***(a3)-*

*(**W*- 1.1

*T*

*n*

*)*

*1 where**(.)*is the spectral

*radius of a matrix.*

*We have :*

*lim*

*k*

*E*(*P*(*k*))= 1.1

*T*

*n*

*(27)*

*Then: lim*

*k*

*E*(*P*(*k*))=

*i*=1

*i*=*n*

*C*

*i*

*(*

*0)*

*n*

*(28)*

*2) Convergence of the second moment :*

*The convergence of the second moment is investigated in*

*this section to quantify the convergence rate of**C(k)*to*C*

*ave*

*.*

*To obtain it, lets consider the error :**N(k)=C(k) C*

*ave*

*.*.**1**

*Considering the evolution of**N(k)*, we can easily demonstrate

*that :*

*N*(*k*+1)=*W*(*k*)*. N*(*k*) (29)

*So,**N(k)*evolves with the same linear system as*C(t)*. Hence

*we can write :*

*E*[*N*(*k*+1)

*T*

*.**N*(*k*+1)*N*(*k*)] =

*N*(*k*)

*T.*

*E*[*W*(*k*)

*T*

*.**W*(*k*)].*N*(*k*) (30)

*Using the fact that**W(k)*is doubly stochastic and so is*W*,

*and the orthogonality between**N(t)*and*1*, we can demonstrate

*that :*

*E*[*N*(*k*)

*T*

*N*(*k*)]

*2*

*2t*

*(*

*E*[*W*

*TW*

*])*

*N*(0) (31)

*Hence, since*

*2*

*1*(second largest*eigen value*of*W*), the

*expectation of the error converge to zero when**k*approaches

*infinity*.

*3) High probability bounds on averaging time :*

*In [2], an upper and lower bounds are demonstrated.*

**Theorem 1 :[2]**Having a gossip algorithms with an initial

*state**C(0)*:

*For**k 6.K*()*

*:**Pr*(

*C*(*k*)-*C*

*ave*

*C*(0)

*) (32)*

*For**k K*()*:*Pr*(

*C*(*k*)-*C*

*ave*

*C*(0)

*) (33)*

*Where :**K*

*.*

*.*

*(*

*)=*

*log(*

*-*

*1*

*)*

*2.log(*

*2*

*(*

*W*)

*-*

*1*

*)*

*(34)*

*These are results for averaging consensus. However, the*

*consensus studied her is to reach all the nodes to have the same*

*decision on the message they spread. It's clearly a consensus as*

*it's a fixed point of the algorithm.*

*To reach that, a sufficient but not necessary condition can*

*be implemented as a stopping criterion :*

*C*(*k*)-*C*

*ave*

*C*

*ave*

*(35)*

*This means that :*

*1**i**n ,*

*C*

*i*

*(*

*k*)-*C*

*ave*

*C*

*ave*

*(36)*

*Hence, with (4), we can obtain the corresponding**for the*

*convergence. For =*

*C*

*ave*

*C*(*o*)

*=*

*i*=0

*n*

*C*

*i*

*(*

*0)*

*n*

*(*

*n*)

*=*

*n*

*1*

*-*

*n*

*2*

*n*

*(*

*n*)

*(37)*

*Note that*

*is an increasing linear function of the initial*

*difference between the number of**g1*and*g2*holders. We have:

*Pr*(*C*

*i*

*(*

*k*)*have the same sign*)1-

*n*

*1*

*-*

*n*

*2*

*n*

*(*

*n*)

*(38)*

*for every**k*

*3.log(*

*C*(*o*)

*C*

*ave*

*)*

*log(*

*2*

*(*

*W*)

*-*

*1*

*)*

*(39)*

*and :*

*Pr*(*All C*

*i*

*(*

*k*)*have the same sign*)1-

*n*

*1*

*-*

*n*

*2*

*n*

*(*

*n*)

*(40)*

*for every**k*

*log(*

*C*(*o*)

*C*

*ave*

*)*

*2.log (*

*2*

*(*

*W*)

*-*

*1*

*)*

*(41)*

*Which gives the consensus reach bounds of the algorithm.*

*C. Simulation results*

*First, we simulate (Figure 3) the evolution of the number of*

*nodes holding each one of the two messages (**g1*) and (*g2*).The

*two simulations concern a complete graph with 1000 nodes.*

*This simulation shows that the algorithm converges and the*

*nodes end up agreeing on the most relevant message (**i.e*: the

*one with the higher initial number of holders).*

*Secondly, the curves in Figure 4 show the evolution of the*

*distance*

*C*(*k*)-*C*

*ave*

*. Foremost, we can see that the*

*convergence is reached even before getting a distance of zero*

*between the counter's vector and**C*

*ave*

*, which can be justified by*

*(26). In fact, the convergence is a convergence of the signs of*

*the counters rather than the counters themselves. Then, it is*

*also clear ( Figure 4) that when the initial settings of**n1*and*n2*

*are farther from each other the convergence rate is higher,*

*which matches the theoretical results.*

*IV. A*

*PPLICATION*

*A. A repeated game of distributed voting:*

*We consider a repeated game where players can vote for*

*one of two possible candidates. Each agent prefers one of the*

*two candidates over the other. However, a player is better off*

*voting for the candidate that is going to win anyway. Hence,*

*we define**u*

*k*

*(**i*), the payoff of each player*i*at a step k, as

*follows:*

**u**

**k**

*(*

*i*)=(*Sum of all the agents agreeing with i*)

*Thus, the set of agents**N*is partitioned so that we have two

*subsets**N*

*1*

*and**N*

*2*

*containing respectively the agents agreeing*

*over the choice*

*1*

*or*

*2*

*.*

*Since the agents are unaware of the choices of other agents*

*they cannot know what their payoffs are at a certain step.*

*Moreover, we assume that at each step, to agents are able to*

*contact each other. The goal is to find a strategy that will help*

*all the agents maximize their payoffs.*

*Proceeding as shown in the algorithm provided in Section*

*III. All the players hold a counter that is initialized at the*

*beginning of the game.*

*At a step**k*, we assume that no agent is able to observe his

*payoff. Instead, each couple of agents**i*and*j*who came in

*contact with each other can observe the state of their counters.*

*According to the results of the previous section, consensus*

*over the choice of a candidate is reached with high*

*probability.*

**Fig. 3**Evolution of holders of each message (g1: lower curve,

*g2: upper curve) at each round (initial values: n1=400 and*

*n2=600)*

**Fig. 4**Distance to the expected average at each round k(i.e.:

*C*(*k*)-*C*

*ave*

*). Three initial settings are distinguished*

*B. Application to word-of-mouth marketing*

*Direct marketing deals with separate events: each email or*

*advertisement is considered as a separate deal. But in a*

*community where people are related to each other, all of these*

*notions are connected.*

*We analyze the case where two conflicting products are*

*spreading in a community. There aren't many distinct*

*thresholds for spreading two products in a community: one of*

*the products will win at the very end. But in general, the*

*spreading of the products stops before this state is achieved.*

*The individuals proceed as shown in the algorithm*

*described in Section III. We start by considering that all the*

*nodes (individuals) are connected to each other. If the graph is*

*not complete, the counters will be weighted proportionally to*

*the centrality of the nodes. We can choose**betweenness*as a

*measure of centrality. The intuition behind this approach is*

*that a node by which transits more information is more likely*

*to have an impact on the other nodes. The only thing that*

*changes is the initialization step and we are brought back to*

*the complete graph structure. Thus, we consider a set of agents*

*V*connected in a complete undirected graph*G*= (*V*,*E*).

*Instead of initializing all the nodes at the same value of the*

*counter, a higher value should be assigned to the counters of*

*the nodes that are more convincing.*

*First, we assume that more or less convincing nodes are*

*distributed according to a normal distribution. In other words,*

*in the initialization step: the random variable that assigns a*

*value to a counter follows a Gaussian distribution.*

*According to Section III, at each step, each counter is a*

*linear combination of the initial values of the counters.*

*Consequently, at each step, the vector**C(k)*follows a normal

*distribution. Moreover, the values of the counters converge to*

*the mean of the initial distribution. Hence, the mean of the*

*final distribution is equal to the initial mean. However, the*

*closer this initial mean is to zero, the slower is the*

*convergence of the algorithm.*

**Simulation results:**

*Experimental results (figure 5) show that the final*

*distribution is as expected a normal distribution.*

*Changing the initial variance of the distribution only*

*impacts the convergence rate.*

*We simulate a graph where the distribution has a mean that*

*has a negative value close to zero. As shown in Figure 5, the*

*individuals end up having the same preference,**i.e.:*all the

*counters are negative.*

*However, in the real world the spreading process stops*

*before convergence is reached since new products come out.*

**Fig. 5:**Last distribution of the counters (the values are

*condensed around a value close to -0.0112)*

*V. C*

*ONCLUSION*

*AND*

*F*

*UTURE*

*W*

*ORK*

*Gossip algorithms are an efficient tool to model rumor*

*spreading over network structures. The results presented in this*

*paper give an overview of the way rumor forwarding proceeds*

*in a social network.*

*In the case of multiple conflicting messages, our main*

*result is that the number of holders of a given message evolves*

*almost proportionally to the sum of all the messages holders*

*with a coefficient that is equal to the initial number of holders.*

*Furthermore, the consensus based gossip algorithm makes*

*it possible to lead the nodes towards choosing the same belief.*

*Of course, this is does not represent realistic scenarios as many*

*parameters were not considered. For instance, there might exist*

*some non-cooperating agents among the nodes.*

*A game theoretical approach shows that agents can*

*maximize their payoffs based only on their local knowledge*

*and agree on the same choice in a voting game.*

*A word-of-mouth marketing model shows how, in a*

*community where two conflicting ideas start spreading, only*

*one idea remains in the end.*

*There are more issues to be explored. In multiple rumor*

*spreading the consideration of other types of graphs may lead*

*to important practical results. So far we have avoided the*

*impact of the position of nodes, their study could optimize the*

*spreading by getting through strategical nodes. In the*

*consensus-based approach more work could be realized on the*

*influence of weighted graphs on the convergence of the*

*algorithm. In other words, the updating step could be realized*

*with multiplying the counters by a factor that illustrates the*

*influence of each one of the two communicating nodes.*

*VI. A*

*CKNOWLEDGMENT*

*We would like to thank Vincent Gripon and Michael*

*Rabbat for their supprot and supervision. We would also like*

*to thank Samir Saoudi for his time and consideration. Finally,*

*many thanks to the host laboratory in the electronics*

*departement at Télécom Bretagne.*

*R*

*EFERENCES*

*[1] A.J. Demers, D.H. Greene, C. Hauser, W. Irish, J. Larson, S.*

*Shenker, H.E. Sturgis, D.C. Swinehart, and D.B. Terry,*

*"Epidemic algorithms for replicated database maintenance",*

*Proceedings of the Sixth Annual ACM Symposium on*

*Principles of Distributed Computing (PODC'87), 1987, pp. 112.*

*[2] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, Gossip*

*algorithms: Design, analysis, and applications,**Proc. IEEE*

*INFOCOM*, 2005

*[3] J. C. Frauenthal, "Mathematical Modeling in Epidemiology" p.*

*12-24 Springer-Verlag 1980.*

6 of 6 pages

- Quote paper
- Ismail Elouafiq (Author)Amine Semma (Author), 2014, Algorithm for Achieving Consensus over Conflicting Rumours, Munich, GRIN Verlag, https://www.grin.com/document/278179

6 pages
Publish now - it's free

Comments