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.

Leseprobe

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 widely

used 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

ONFLICTING

UMORS

PREADING

OVER

THE

AME

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

and let l be a positive integer l IN

. The algorithm proceeds as

follows :

In the beginning, two subsets of V, I

and I

, 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

with one (C

counts the unnecessary calls made

by i, their initial value is 0).

If C

=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))

, 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 :

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

(

k )=

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

(1)

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

I1(k) . S(k)

N ( N-1)

(2)

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

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

N (N -1)

(3)

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

I2(k ). S( k)

N ( N-1)

(4)

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

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)

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

di2 (t)

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

ds(t )

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

dr1 (t)

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

dr2 (t)

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 l1 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 )

si (19)

di (t)

si+

(

1- s)i (20)

The solution of this couple of equations is [3]:

i(s)= l+1

(

1- s)+ 1

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

for the messages

corresponding to his own message, and a second counter C'

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'

(k+1)=C'

(k)+C

(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

(k+1)=C

(k)

(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'

from that of C

Thus we propose the following algorithm to study. We give

to each node i a counter C

and proceed by averaging the

counters to achieve consensus as described below.

A. Algorithm description :

Initialization step :

for i in {1,..,n}

{

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 :

(k+1)=C

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

(k)+C

(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

be the set of i's neighbors, n

=|N

| the number of i's neighbors

and C(k) the vector for which entries are the counters C

(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

W (k )= I -

(

)(

)

(24)

with probability

n.n

, where e

is an n x 1 unit vector with

the i

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

(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

.W (k) = 1

, where

1 denotes the vector of all ones. Also, the vector of averages

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

.1 we must have :

lim

P(k )=1.1

(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

.W = 1

(a2)- W .1 = 1

(a3)- (W - 1.1

)

1 where (.) is the spectral

radius of a matrix.

We have :

lim

E( P( k))= 1.1

(27)

Then: lim

E( P( k))=

i=1

i=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)

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

N ( k )

E [W (k)

. 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)

N ( k)]

(

E[W

])

N (0) (31)

Hence, since

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(

)

2.log(

(

W )

)

(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

(35)

This means that :

1in ,

(

k )-C

ave

(36)

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

convergence. For =

ave

C (o)

i=0

(

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

(

k)have the same sign)1-

(

(38)

for every k

3.log(

C ( o)

ave

)

log(

(

W )

)

(39)

and :

Pr ( All C

(

k) have the same sign)1-

(

(40)

for every k

log(

C (o)

ave

)

2.log (

(

W )

)

(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

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

follows:

(

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

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

subsets N

and N

containing respectively the agents agreeing

over the choice

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

UTURE

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.

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.

Frequently Asked Questions: Algorithm for Achieving Consensus Over Conflicting Rumors

What is the core problem addressed in this paper?

The paper explores the problem of multiple conflicting messages spreading over a social network using gossip algorithms. Specifically, it deals with the scenario where two rumors compete for acceptance within the same network.

What are gossip algorithms in the context of this paper?

Gossip algorithms are decentralized communication schemes used for information dissemination in networks. In this context, they are employed to model how rumors spread through a social network, with nodes (individuals) repeatedly contacting random neighbors to transfer their messages.

What is the main focus of the algorithm presented for two conflicting rumors?

The algorithm analyzes the final distribution of two conflicting messages (rumors) spread over a network, given an initial state. It also proposes an algorithm to achieve consensus over one of the messages. This means the goal is to have most nodes agree on which rumor is true or more believable.

How does the algorithm model the spread of rumors?

The algorithm uses a deterministic model based on the expectation of a Markov Chain. This model takes into account factors like the number of nodes holding each rumor and the rate at which nodes share information.

What are the different states a node can be in, according to the model?

Nodes can be in one of five states: 1) Has (m1) and is spreading it (m1 infective), 2) Has (m2) and is spreading it (m2 infective), 3) Has (m1) and stopped spreading it (m1 removed), 4) Has (m2) and stopped spreading it (m2 removed), and 5) Doesn't have a message (susceptible).

How does the model use Markov Chains to describe the rumor spreading process?

The spreading process is modeled as a Discrete Time Markov Chain (DTMC), where the state of the nodes at a particular time (k+1) depends only on their state at the previous time (k). This allows tracking the probability of transitions between different states of the nodes (e.g., from susceptible to infective).

What is the purpose of the consensus-based algorithm?

The consensus-based algorithm aims to get all the nodes to agree on one of the two messages. It uses counters that nodes update through interaction with neighbors, eventually leading to a situation where most nodes favor one message over the other.

What is the difference between the two counter approach and the averaging approach for consensus?

The two counter approach tracks two separate counters for each message, where the difference guides consensus. The averaging approach simplifies this by averaging a single counter across neighbors until consensus is achieved, this simpler approach is proven to be equivalent.

What are the assumptions made in deriving the deterministic model?

The assumptions are: N is approximately equal to N-1 for high N, and time intervals between Poisson clock ticks are neglected (i.e., k=t).

What is the role of the parameter 'l' in the algorithm?

The parameter 'l' represents the number of times a node will attempt to spread a message to already informed neighbors before giving up and becoming a "removed" node. This affects the reach and spread of the rumor.

How is the consensus algorithm applied to distributed voting?

In a distributed voting scenario, agents vote for one of two candidates. They use the consensus-based algorithm (averaging counters through local interaction) to converge on a choice, even if they don't have complete information about other agents' preferences. This allows them to maximize payoffs by voting for the anticipated winner.

How can gossip algorithms and these models be applied to word-of-mouth marketing?

The models can simulate how two conflicting products or ideas spread in a community through word-of-mouth. The algorithm can predict the likely winner of this "marketing battle" and identify which product or idea will dominate the conversation. Initialization values such as a higher valued counter means that this product or idea is more convincing.

What are some potential areas for future research?

Future work includes considering other types of graphs, studying the impact of node position, considering non-cooperating agents, influence from weighted graphs, and exploring the influence of various parameters.

Ende der Leseprobe aus 6 Seiten - nach oben

PDF-Version für nur US$ 0,99

Sofort herunterladen. Inkl. MwSt.
Format: PDF – für alle Geräte

Buch für nur US$ 16,99

Versand weltweit

Details

Titel

Algorithm for Achieving Consensus over Conflicting Rumours

Note

bac+4

Autoren

Ismail Elouafiq (Autor:in), Amine Semma (Autor:in)

Erscheinungsjahr

2014

Seiten

6

Katalognummer

V278179

ISBN (eBook)

9783656713975

ISBN (Buch)

9783656713586

Sprache

Englisch

Schlagworte

algorithm consensus rumours gossip algorithms social networks game theory word-of-mouth.

Produktsicherheit

GRIN Publishing GmbH

Arbeit zitieren

Ismail Elouafiq (Autor:in), Amine Semma (Autor:in), 2014, Algorithm for Achieving Consensus over Conflicting Rumours, München, GRIN Verlag, https://www.grin.com/document/278179

Blick ins Buch

Leseprobe aus 6 Seiten