Signal Processing - January 2016 - 42

Random
Selection

Imitation

Co
m
Fit put
ne e
ss

on
cti tion
e
l
a
Se Imit
l
r
na
fo
tr io ss
o e
op itn
Pr o F
t

[FIG4] the imitation strategy updating rule.

and homogeneous, the proportion of players adopting a certain
strategy is equivalent to the probability of one individual player
adopting such a strategy, i.e., the strategy distribution over the
whole population can be interpreted as each player's mixed
strategy, and the replicator dynamics can be interpreted as each
player's mixed strategy update.
Graphical EGT studies the strategies' evolution in such a
structured population [24]. In the EGT, in addition to the entities of players, strategy, and fitness matrix, each game model is
associated with a graph structure, where the vertices represent
players and the edges determine which player to interact with.
Since the players only have limited connections with others,
each player's fitness is locally determined from interactions
with all adjacent players.

The commonly used strategy updating rules [25] are originated from the evolutionary biology field and used to model the
mutant evolution process. Figure 4 illustrates the detailed evolution procedures of the imitation strategy update rule. In the first
step, a user is randomly chosen from the population for imitation. Then, the fitness of the chosen user and all corresponding
neighbors is computed. Finally, the user will, in all probability,
either be imitated by one of the neighbors or remain with the
current strategy, with the probability being proportional to fitness. There are also other rules, such as the birth-death strategy
update rule and death-birth strategy update rule, but through
theoretical analysis [15], we find that these rules are equivalent
when the network degree is sufficiently large.
INFORMATION-DIFFuSION
FORMuLATION AND ANALySIS
A social network is usually illustrated by a graph, e.g., a Facebook
subnetwork is shown in Figure 5, where each node represents a user,
and lines represent the relationships between users. When some
new information is originated from one user, the information may be
propagated over the network, depending on other users' actions to
forward the information or not. For each user, whether he or she forwards the information is determined by several factors, including the
user's own interest in the information and the neighbor's actions, in
the sense that, if all the neighbors forward the information, the user
may also forward the information with a relatively high probability.
In such a case, the users' actions are coupled with each other
through their social interactions. This is very similar to the player's
strategy update in the graphical evolutionary game, where players'
strategies are also influenced with each other through the graph
structure. In the graphical evolutionary
game, a user's strategy can influence one of
the neighbors when the fitness of adopting
this strategy is high. Similarly, in the information-diffusion process, when forwarding
the information can bring a user more utility,
the user's neighbors may also be influenced
to forward the information in the near
future. Therefore, the information-diffusion
process can be well modeled by the graphical
evolutionary game, as illustrated in Figure 6.
There are two possible actions for each
user, i.e., to forward (S f ) or not forward
(S n), and the corresponding users' payoff
matrix can be written as

[FIG5] a Facebook subnetwork [16], [26].

u ff u fn
o,
u fn u nn

(2)

where a symmetric payoff structure is considered, i.e., when a user with strategy S f
meets a user with strategy S n, each of
them receives the same payoff u fn . Note
that the payoff matrix is related to the fitness in the graphical evolutionary game
according to (1). The physical meaning of

IEEE SIGNAL PROCESSING MAGAZINE [42] jANuARy 2016

Table of Contents for the Digital Edition of Signal Processing - January 2016