Signal Processing - January 2016 - 43
the payoff can be either the popularity of a user in a social network
or the hit rate of a website. These three parameters will be learned
from the data and then used for decision making. Under different
application scenarios, the values of the payoff matrix may be different. For example, if the information is related to recent hot topics
and forwarding of the information can attract more attentions
from other users or websites, the payoff matrix should have the
following characteristic: u ff $ u fn $ u nn . According to (1), the fitness of forwarding is larger, and, thus, the probability of forwarding will be higher. On the other hand, if the information is about
useless advertisements, the payoff matrix would exhibit
u nn $ u fn $ u ff, i.e., the fitness of not forwarding is higher, and,
thus, users tend not to forward the information. Furthermore, if
the information is supposed to be shared only within a circle, i.e., a
small group with the same interest, the payoff matrix could exhibit
u fn $ u ff $ u nn .
Since the player's payoff is determined by both his or her own
strategy and the opponent's strategy, to characterize the global
population dynamics, we need to first derive the local influence
dynamics as well as the corresponding influence equilibria. We
find in [15] that the local network states, i.e., the neighbors' strategy distribution given a player's strategy, evolve with a rate of
order 1, while the global network state, i.e., the strategy distribution of the whole population, evolves with a rate at the order of the
selection intensity a, which is much smaller than one due to the
weak selection [23]. In such a case, the local network states will
converge to equilibria at a much faster rate than the global network state. This is because the dynamics of local network states
are only in terms of a local area, which contains only the neighbors. At such a small scale, the local dynamics can change and
converge quite fast. On the other hand, if the dynamics of the
global network state are associated with all users, i.e., the whole
network, the dynamics would be much slower. Therefore, the
global network state can be regarded as constant during the convergence of influence dynamics. By doing so, the equilibria of the
local influence dynamics can be obtained, which are found to be
linear functions of the global network state.
With the equilibria of the local influence dynamics, the global
population dynamics can be derived through analyzing the strategy updating rules specified in the graphical evolutionary game
[25]. It is found that the global population dynamics can be represented as a two-parameter, third-order polynomial function of the
global network state [15]
a (kr - 1) ( k 2 - 2kr )
p f (t) 61 - p f (t)@6ap f (t) + b@,
po f (t) =
( k 2 - kr ) 2
(3)
where p f (t) is the proportion of the population forwarding the
information, po f (t) is the corresponding dynamics, kr = E [k] is
the average degree of the network, k 2 = E [k 2] is the second
moment of the degree of the network, and a and b are two
parameters determined by the payoff matrix shown in (2).
From (3), we can see that, given the characteristic of the network, i.e., the average degree kr and the second moment of the
degree k 2, the evolution dynamics of the information diffusion
can be modeled by a simple two-parameter, third-order
polynomial function, where the two parameters a and b are
determined by the payoff in the payoff matrix, i.e., u ff, u fn and
u nn . Therefore, by learning the payoff from the data, we are able
characterize the evolution dynamics of information diffusion
using the evolutionary game-theoretic framework.
By evaluating the global population dynamics at the steady
state, the global population equilibria can be found [16], which is
zero (no user shares the information with the neighbors), one
(all users share the information with their neighbors), or only a
portion of users share the information with their neighbors
where the amount of such users is purely determined by the payoff matrices as follows:
Z
if u nn 2 u fn 2 u ff;
] 0,
p = ] 1,
if u ff 2 u fn 2 u nn;
[ 2 r
(
k
/
k
)
(
u
2
fn - u nn) + (u ff - u nn)
]
] ( k 2 /kr - 2) (2u fn - u ff - u nn) , else.
(4)
\
*
f
From (4), we can see that neither user forwarding the information can gain the most payoff, while both forwarding gains the
least payoff, p *f = 0. This corresponds to the scenario where the
released information is useless or a negative advertisement, forwarding that can only incur unnecessary cost. On the contrary,
both users forwarding the information can gain the most payoff,
while not forwarding gains the least payoff, p *f = 1. This corresponds to the scenario where the released information is an
extremely hot topic, and forwarding it can attract more attention.
For other cases, p *f lies between zero and one. For this third ESS,
some approximations can be made as follows:
( k 2 /kr - 2) (u fn - u nn) + (u ff - u nn)
,
( k 2 /kr - 2) (2u fn - u ff - u nn)
1
,
0
1 + u fn - u ff
u fn - u nn
p *f =
(5)
where the last approximation is due to k 2 /kr $ kr and the assumption that the average network degree kr & 2 in real social
Graphical EGT
Social Network
Graph Structure
Social Network Topology
Players
Users in the Social Network
Strategy
Sf : Forward the Information
Sn: Not Forward the Information
Sf Sn
Sf
uff ufn
Sn ufn unn
Fitness
Utility from Forwarding or Not
ESS
Stable Information-Diffusion State
[FIG6] Information diffusion as a graphical evolutionary game.
IEEE SIGNAL PROCESSING MAGAZINE [43] jANuARy 2016
Table of Contents for the Digital Edition of Signal Processing - January 2016
Signal Processing - January 2016 - Cover1
Signal Processing - January 2016 - Cover2
Signal Processing - January 2016 - 1
Signal Processing - January 2016 - 2
Signal Processing - January 2016 - 3
Signal Processing - January 2016 - 4
Signal Processing - January 2016 - 5
Signal Processing - January 2016 - 6
Signal Processing - January 2016 - 7
Signal Processing - January 2016 - 8
Signal Processing - January 2016 - 9
Signal Processing - January 2016 - 10
Signal Processing - January 2016 - 11
Signal Processing - January 2016 - 12
Signal Processing - January 2016 - 13
Signal Processing - January 2016 - 14
Signal Processing - January 2016 - 15
Signal Processing - January 2016 - 16
Signal Processing - January 2016 - 17
Signal Processing - January 2016 - 18
Signal Processing - January 2016 - 19
Signal Processing - January 2016 - 20
Signal Processing - January 2016 - 21
Signal Processing - January 2016 - 22
Signal Processing - January 2016 - 23
Signal Processing - January 2016 - 24
Signal Processing - January 2016 - 25
Signal Processing - January 2016 - 26
Signal Processing - January 2016 - 27
Signal Processing - January 2016 - 28
Signal Processing - January 2016 - 29
Signal Processing - January 2016 - 30
Signal Processing - January 2016 - 31
Signal Processing - January 2016 - 32
Signal Processing - January 2016 - 33
Signal Processing - January 2016 - 34
Signal Processing - January 2016 - 35
Signal Processing - January 2016 - 36
Signal Processing - January 2016 - 37
Signal Processing - January 2016 - 38
Signal Processing - January 2016 - 39
Signal Processing - January 2016 - 40
Signal Processing - January 2016 - 41
Signal Processing - January 2016 - 42
Signal Processing - January 2016 - 43
Signal Processing - January 2016 - 44
Signal Processing - January 2016 - 45
Signal Processing - January 2016 - 46
Signal Processing - January 2016 - 47
Signal Processing - January 2016 - 48
Signal Processing - January 2016 - 49
Signal Processing - January 2016 - 50
Signal Processing - January 2016 - 51
Signal Processing - January 2016 - 52
Signal Processing - January 2016 - 53
Signal Processing - January 2016 - 54
Signal Processing - January 2016 - 55
Signal Processing - January 2016 - 56
Signal Processing - January 2016 - 57
Signal Processing - January 2016 - 58
Signal Processing - January 2016 - 59
Signal Processing - January 2016 - 60
Signal Processing - January 2016 - 61
Signal Processing - January 2016 - 62
Signal Processing - January 2016 - 63
Signal Processing - January 2016 - 64
Signal Processing - January 2016 - 65
Signal Processing - January 2016 - 66
Signal Processing - January 2016 - 67
Signal Processing - January 2016 - 68
Signal Processing - January 2016 - 69
Signal Processing - January 2016 - 70
Signal Processing - January 2016 - 71
Signal Processing - January 2016 - 72
Signal Processing - January 2016 - 73
Signal Processing - January 2016 - 74
Signal Processing - January 2016 - 75
Signal Processing - January 2016 - 76
Signal Processing - January 2016 - 77
Signal Processing - January 2016 - 78
Signal Processing - January 2016 - 79
Signal Processing - January 2016 - 80
Signal Processing - January 2016 - 81
Signal Processing - January 2016 - 82
Signal Processing - January 2016 - 83
Signal Processing - January 2016 - 84
Signal Processing - January 2016 - 85
Signal Processing - January 2016 - 86
Signal Processing - January 2016 - 87
Signal Processing - January 2016 - 88
Signal Processing - January 2016 - 89
Signal Processing - January 2016 - 90
Signal Processing - January 2016 - 91
Signal Processing - January 2016 - 92
Signal Processing - January 2016 - 93
Signal Processing - January 2016 - 94
Signal Processing - January 2016 - 95
Signal Processing - January 2016 - 96
Signal Processing - January 2016 - 97
Signal Processing - January 2016 - 98
Signal Processing - January 2016 - 99
Signal Processing - January 2016 - 100
Signal Processing - January 2016 - 101
Signal Processing - January 2016 - 102
Signal Processing - January 2016 - 103
Signal Processing - January 2016 - 104
Signal Processing - January 2016 - 105
Signal Processing - January 2016 - 106
Signal Processing - January 2016 - 107
Signal Processing - January 2016 - 108
Signal Processing - January 2016 - 109
Signal Processing - January 2016 - 110
Signal Processing - January 2016 - 111
Signal Processing - January 2016 - 112
Signal Processing - January 2016 - 113
Signal Processing - January 2016 - 114
Signal Processing - January 2016 - 115
Signal Processing - January 2016 - 116
Signal Processing - January 2016 - 117
Signal Processing - January 2016 - 118
Signal Processing - January 2016 - 119
Signal Processing - January 2016 - 120
Signal Processing - January 2016 - 121
Signal Processing - January 2016 - 122
Signal Processing - January 2016 - 123
Signal Processing - January 2016 - 124
Signal Processing - January 2016 - 125
Signal Processing - January 2016 - 126
Signal Processing - January 2016 - 127
Signal Processing - January 2016 - 128
Signal Processing - January 2016 - 129
Signal Processing - January 2016 - 130
Signal Processing - January 2016 - 131
Signal Processing - January 2016 - 132
Signal Processing - January 2016 - 133
Signal Processing - January 2016 - 134
Signal Processing - January 2016 - 135
Signal Processing - January 2016 - 136
Signal Processing - January 2016 - 137
Signal Processing - January 2016 - 138
Signal Processing - January 2016 - 139
Signal Processing - January 2016 - 140
Signal Processing - January 2016 - 141
Signal Processing - January 2016 - 142
Signal Processing - January 2016 - 143
Signal Processing - January 2016 - 144
Signal Processing - January 2016 - 145
Signal Processing - January 2016 - 146
Signal Processing - January 2016 - 147
Signal Processing - January 2016 - 148
Signal Processing - January 2016 - 149
Signal Processing - January 2016 - 150
Signal Processing - January 2016 - 151
Signal Processing - January 2016 - 152
Signal Processing - January 2016 - 153
Signal Processing - January 2016 - 154
Signal Processing - January 2016 - 155
Signal Processing - January 2016 - 156
Signal Processing - January 2016 - 157
Signal Processing - January 2016 - 158
Signal Processing - January 2016 - 159
Signal Processing - January 2016 - 160
Signal Processing - January 2016 - 161
Signal Processing - January 2016 - 162
Signal Processing - January 2016 - 163
Signal Processing - January 2016 - 164
Signal Processing - January 2016 - 165
Signal Processing - January 2016 - 166
Signal Processing - January 2016 - 167
Signal Processing - January 2016 - 168
Signal Processing - January 2016 - Cover3
Signal Processing - January 2016 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com