A review on graphical evolutionary game for information diffusion on social networks

Abstract

Purpose

With the recent development of science and technology, research on information diffusion has become increasingly important.

Design/methodology/approach

To analyze the process of information diffusion, researchers have proposed a framework with graphical evolutionary game theory (EGT) according to the theory of biological evolution.

Findings

Through this method, one can study and even predict information diffusion.

Originality/value

This paper summarizes three existing works using graphical EGT to discuss how to obtain the static state and the dynamics of information diffusion in social network.

Citation

Qiu, B. and Zhang, N. (2018), "A review on graphical evolutionary game for information diffusion on social networks", International Journal of Crowd Science, Vol. 2 No. 3, pp. 259-271. https://doi.org/10.1108/IJCS-06-2018-0011

1. Introduction

Over the past several decades, accompanied by the rapid development of the internet and mobile communications, social networks are becoming increasingly popular among numerous individuals. Every second, millions of users are interacting, which is giving rise to the development of various kinds of information. It is therefore critical to understand how such a huge amount of information diffuses over social networks for the development of social networks.

Many researchers have been studying information diffusion from different perspectives. Originally, information diffusion was proposed to solve the problem of attacks of computer virus (Pastor-Satorras and Vespignani, 2001) (Gruhl et al., 2004). People later realized that information diffusion could be an independent research topic. Early works about information diffusion focused on the dynamics of information diffusion from both the macroscopic and microscopic perspectives (Gruhl et al., 2004). Later, researchers studied how users’ behaviors were affected by social networks (Centola, 2010). Machine learning was used to find the global influence of individuals in diffusion (Yang and Leskovec, 2010). How to restrain private information diffusion by important information links was investigated by Kimura et al. (2009) and Ilyas et al. (2011). The authors discussed how to find the nodes that have more influence over others (Kimura et al., 2007). Recently, as Facebook and Twitter have become increasingly popular, an analysis was conducted to predict future trends on the basis of data obtained from Twitter (Yang and Counts, 2010) (Leskovec). Game theory has also been used to analyze this process (Chen and Liu, 2012). The graphical evolutionary game theory (EGT) framework was proposed to model and analyze interaction among users in social network (Jiang et al., 2014a, 2014b), and the coordination game was utilized to analyze the diffusion process (Vega-Redondo, 2007). The stability of information diffusion was obtained by means of different methods (Wang et al., 2010a, 2010b, 2010c; Kim and Yoneki, 2012). It was shown that users with different number of followers can have different influences (Beevolve, 2012).

Information diffusion over social networks is similar to biological evolution, and thus, the graphical EGT can be used to analyze and model how information diffuses over social networks. EGT has been widely adopted in various areas including image interpolation (Chen et al., 2011), as well as wireless communications and networking (Wang et al., 2010a, 2010b, 2010c; Jiang et al., 2013; Tembine et al., 2010; Wiecek et al., 2011). In this paper, we summarized the key results of studies (Jiang et al., 2014a, 2014b) and (Cao et al., 2016) to illustrate how the graphical EGT can be used to model information diffusion.

The rest of this paper is organized as follows. In Section 2, information diffusion is discussed in detail. Some basic concepts about graphical EGT are given in Section 3. Then in Section 4, the model built with graphical EGT is discussed. Static and dynamic diffusion processes with the corresponding experimental results are shown in Section 5. Section 6 draws the conclusion of this paper.

2. Information diffusion

To understand information diffusion, the information should be defined. When weather prediction tells us it will be sunny tomorrow or teachers solve our confusion about an incomprehensible concept, we instinctively feel that we have received information. It is widely agreed that information is any entity or form that resolves uncertainty or provides an answer for any question. Despite information being present since the birth of humankind, the measurement of information was discussed only in in 1948 by C. E. Shannon in the book A Mathematical Theory of Communication.

Just as the information has been with human for so long, so is the information diffusion. This is because where there is information, there is information diffusion. With the rapid development of the internet and mobile communications, information diffusion over social networks is faster and broader. For example, sham information has great possibilities of becoming a rumor as soon as it is released in a social network. In a traditional social network, there may be adequate time for response and stopping the rumor. However, in contemporary social network, more efforts are needed to stop rumors. Studying information diffusion over social network can help us discover the common characteristics of communities for precise commercial advertisement and pointed political canvassing. In all, the study of information diffusion can be applied to various domains. There are two examples. Donald Trump, the President of the USA, has the habit of tweeting for the country. As the president of the world’s superpower, his words on the internet have the ability of creating waves. If we can predict how the information released by Trump is diffused on the internet or among the people, then we can better evaluate the influence caused of his tweets. What does it mean? It means, in the financial world, we will macroscopically be able to more quickly and accurately predict fluctuations in the stock, which can prove to be financially beneficial. Except predicting the diffusion states, we have the ability to deduce the characteristic of a group of people who are forwarding or not through known diffusion states at any moment. This can be used to tell candidates to give corresponding speeches to different groups of voters. It is also possible that the popularity rating can be raised. Besides this, the model of users, which is obtained by analyzing the existing diffusion actions of users in the past, can be applied to advertise on the internet more accurately, which may create billions of wealth, as it has done for Google.

3. Graphical evolutionary game theory

The basic concepts of graphical EGT will be introduced in this section (Smith, 1982), which will be used to analyze information diffusion in the next section (Jiang et al., 2014a, 2014b) and (Cao et al., 2016).

In EGT, a game is played for many times by players who are chosen randomly from a large population. In this theory, a player changes his strategy according to others’ strategies and his characteristics. We call the dynamics as “replicator dynamics” which is the most important concept in EGT. Replicators, who can represent the population, may reproduce his strategy under some specific rules. For example, there is new information about a football star. One person who is a football fan may originally prefer to forward this information, but when he finds that all of his friends are not concerned about such information, he may change his strategy from forwarding to not forwarding. In this example, we can see that the strategies of neighbors can influence one’s decision. Different from traditional game theory, EGT pays more attention to the dynamics than to stability of the strategies of the whole population. In EGT, all players will have some periods of strategic interactions to reach a final equilibrium, known as the evolutionary stable state (ESS).

In the social network, people may not interact with all users. Therefore, a graph is generally used to represent the relationship among users. In this graph, we use “fitness” (Nowak and Sigmund, 2004) to describe players’ interactions with others, which is relative to their payoff. Players change their strategies according to three strategy update rules (Ohtsukia and Nowak, 2006), including birth–death (BD), death–birth (DB) and imitation (IM) rules. Figure 1 illustrates the general process of these three update rules (Jiang et al., 2014a, 2014b). In Figure 1(a), we can see in the BD update rule, a node is chosen from the population with a probability according to their fitness. Then the strategy of the chosen node will replace one of its neighbor’s strategy. In the DB update rule, we randomly choose a node to abandon its strategy and get one of its neighbor’s strategy with the probability according to their fitness, which is shown in Figure 1(b). In IM update rule, every node chooses one action: either it abandons or retains its strategy with the probability according to their fitness, as shown in Figure 1(c).

4. EGT formulation of information diffusion

Let us consider how to translate a typical social network with the language of graphical EGT. Any users in the social network can be regarded as a node in a graph. The relationship between users corresponds to the edges of graph. In a word, a graph structure can be used to describe the social network topology. Because information diffusion is studied over the social network, it is assumed that any user has only two strategies to choose from: to forwarding information or to not (S_f or S_n). Here, a question can be raised naturally: How do we describe the utility from forwarding or not? As has been done in graphical EGT, fitness (Nowak and Sigmund, 2004) can be used to represent the utility from forwarding or not, which is defined as π = (1 − α)B + αU, where U is the payoff matrix and B is the user’s baseline fitness. In the study of information diffusion, the payoff matrix can be written as: S_f S_n S_f U_ff u_nf S_n u_fn u_nn, where u_ff denotes the payoff when one user and his neighbor both use strategy S_f; u_fn, u_nf and u_nn are defined in a similar way. Note that the payoff matrix is considered symmetric; therefore, the central user and his neighbor both have the same fitness when they use the reverse strategy, i.e. u_fn = u_nf. The payoffs are further normalized within interval (0, 1), which means 0<u_ff, u_fn, u_nn<1. The payoff can be regarded as the popularity of a user or the hit rate of a website by forwarding this information. For example, if the information is about recent hot news, it is known that forwarding it will get more popularity than not forwarding. So under this circumstance, we have u_ff>u_fn>u_nn. On the contrary, if the information is useless for most of us, u_ff<u_fn<u_nn can be obtained. The decision of users is determined by not only the payoff but also by the user’s internal property, i.e. the baseline fitness B. The parameter α in the fitness is a representation of the selection intensity. It is within interval (0, 1). When it is close to 0, the corresponding selection is a weak selection (Ohtsuki et al., 2007), while when α → 1, it denotes a strong selection, in which the payoff determines the fitness. The results shown here are based on the assumption of the weak selection. The reason is that every user is involved in so many games that any game just influences a user a little.

Given a social network, let p_f and p_n denote the percentages of users to forwarding or not, respectively, in the population. Similarly, let p_ff, p_fn and p_nn denote the percentages of edges, where both users are forwarding, one is forwarding and the other is not and both users are not forwarding, respectively. With the basic knowledge of the probability theory, one has: p_n + p_f = 1, p_f|f + p_n|f = 1, p_f|n + p_n|n = 1, p_fp_n|f = p_n|fp_f, p_ff = p_fp_f|f, p_nn = p_np_n|n, p_fn = p_fp_n|f + p_np_f|n. It is obvious that all variables above can be denoted by p_f and p_ff.

5. Theorems for information diffusion over social networks

To characterize the information diffusion over social network with graphical EGT, the two most important things are the evolutionary stable states (ESSs) and the evolutionary dynamics. As discussed above, the states of a social network can be determined by p_f and p_ff. Thus, the following analysis will focus on p_f, p_ff, ṗ_f and ṗ_ff. The first result is about the population dynamics (Jiang et al., 2014a, 2014b).

Theorem 1: The population dynamics of information diffusion over a uniform degree network under BD strategy update rule and weak selection scenario can be described as follows:

(1) pḟ=αk-2k-1pf1-pfa1pf+b1+oα2, 

where a1=k-2uff-2ufn+unn,b1=uff+k-2ufn-k-1unn.

Theorem 2: The population dynamics of information diffusion over non-uniform degree networks under the BD strategy update rule and weak selection scenario can be described as follows:

(2) ṗf=αk−− 1k2−− 2k−k2−−k−2pf1−pfa2pf+b2+oα2, 

where a2=k2−− 2k−uff−2ufn+unn,b2=k−uff+k2−− 2k−ufn−(k2−− k−)unn.

From equations (1) and (2), it can be seen that ṗ_f is not related with N, i.e. the network has the scale-free property, which indicates that the results do not depend on the number of users in the whole network as long as it is large enough. It can be seen that the population dynamics in the uniform and non-uniform degree networks are similar. The only difference between them is k and k² are changed to k− and k−² in the non-uniform network, which means that the non-uniform network can be treated as a uniform network. Although the above two theorems are based on the BD update rule, it has been shown that the population dynamics of information diffusion over uniform degree networks under the BD strategy update rule, the DB strategy update rule and the imitation strategy update rule are equivalent when the network degree is sufficiently large and under the weak selection scenario (Jiang et al., 2014a, 2014b).

To validate the theorems over a homogeneous social network, the following payoff matrices PM1, PM2, PM3 and PM4 are used to derive the theoretical results and compare with simulation results.

Case 1:

PM1: uff>ufn>unn

SfSnSf0.80.6Sn0.60.4

Case 2:

PM2: ufn>uff>unn

SfSnSf0.60.8Sn0.80.4

Case 3:

PM3: ufn>unn>uff

SfSnSf0.40.8Sn0.80.6

Case 4:

PM4: unn>ufn>uff

SfSnSf0.40.6Sn0.60.8

For Case 1: u_ff > u_fn > u_nn, the user and his neighbor who both forward information can achieve the largest payoff, so it can be predicted that the users will choose the forwarding strategy, making all users in the network forward it gradually. For Case 4, u_nn > u_fn > u_ff, the final state of the network will be the complete opposite to that of Case 1, i.e. nobody will choose to forward information. The final stable states of Case 2 and Case 3 are between those of Case 1 and Case 4. The network state of the two cases will gradually converge to a final state which is between 0 and 1.

In Figure 2, the four continuous curves and four groups of discrete points represent the population dynamics derived by the theory and simulation, respectively. It can be seen that the simulations agree with the theoretical results. The small gaps are due to the ignorance of the dependence between network states and network degree. In all four cases, the global network states all converge to the stable state, known as the ESSs.

When the population dynamics equals to zero, the whole network reaches a stable state. Therefore, making equations (1) and (2) equal to 0, one can get the expression of ESSs of both uniform and non-uniform degree networks, which are shown below (Jiang et al., 2014a, 2014b).

Theorem 3: In an N-users social network which can be characterized by a graph with uniform degree k, if each user updates his/her information forward strategy using the IM update rules, the evolutionary stable network states can be summarized as follows:

(3) pf*= 1,                                  ifuff>ufn>unn 0,                                 ifunn>ufn>uffk-2ufn+uff-(k-1)unn2ufn-(k-2)(uff-unn), else. 

Similarly, for non-uniform degree network, we can obtain the following theorem (Jiang et al., 2014a, 2014b).

Theorem 4: In an N-users social network which can be characterized by a graph with degree distribution λ(k), if each user updates his/her information forward strategy using the BD update rule, the evolutionary stable network states can be summarized as follows:

(4) pf*1,                                          ifuff>ufn>unn,0,                                         ifunn>ufn>uff,k2−k−− 2ufn−unn+(uff−unn)(k2−k−− 2)(2ufn−uff−unn), else 

The results are consistent with the intuition. If one can get more utility from forwarding information regardless of the neighbors’ strategies, he will definitely forward this information, i.e. the probability of forwarding is one in the steady state. Similarly, a steady loss will make nobody want to forward information, which is described by pf*=0. For the situations between two extremities above, the ESS will be determined by the exact value of u_ff, u_fn and u_nn, and one can have a general impression through the simulation results as shown below.

Figure 3 illustrates the graph structure and the degree characteristics of a Facebook sub-network, which consists of ten subgraphs. With the payoff matrix given above, the simulation results and theoretical results of the ten subgraphs are shown in Figure 4. The horizontal red line and the cyan line show the ESSs of Case 1 and Case 4, while the green one and the brown one show the ESSs of Case 2 and Case 3.The gaps between simulation and theoretical results of Case 2 and Case 3 are from the neglected dependence between the network state and the network degree. From the results, it can be seen that the theory is consistent with the simulation.

The theorems above characterize the social networks with the same type of users. The study of the information diffusion over heterogeneous social network is also conducted (Cao et al., 2016). Two different situations need to be considered: the unknown user type model and the known user type model. For the unknown user type model, each user does not know the exact type of the neighbors and tends to consider them the same as itself. For the known user type model, each user knows the exact type of the neighbors and thus their decisions.

For the unknown user type model over heterogeneous social network, the following theorem can be derived (Cao et al., 2016).

Theorem 5: (Evolutionary dynamics): In the unknown user type model, the evolutionary dynamics for the network states p_f(i) and p_f are given in the equations as follows:

(5) ṗfi=1Npf−1Npfi+αNpfpf−1×Δik−− 3+2k−1¯pf+1−k−1¯+Δnik−− 1,

(6) ṗf=αNpfpf−1Δ−k−− 3+2k−1¯pf+1−k−1¯+Δn−k−− 1, 

where Δ−≔∑i=1MqiΔi and Δn−≔∑i=1MqiΔni.

Theorem 6: (ESSs): In the unknown user type model, the ESSs of the network are as follows:

(7) p f * = 0 ,   i f u - n n > u - f n 1 ,   i f u - f f > u - f n Δ n - 1 - k - + Δ - ( k - 1 - - 1 ) Δ - ( k - - 3 + 2 k - 1 - ) ,   i f max ⁡ u - f f   , u - n n < u - f n ,  

(8) pf*i=pf*+αpf*pf*−1[Δik−− 3+2k−1¯pf*+1−k−1¯)+Δn(i)(k−− 1)], 

where u−ff=∑i=1Mq(i)uff(i) and u−fn, u−nn are sinilarly defined.

For the known user type model, the following theorems can be obtained (Cao et al., 2016).

Theorem 7: In the known user type model, the population dynamics p_f(i) and the relationship dynamics p_ff(i,l) for i ≠ l and i = l are given as follows:

(9) ṗfi≈αk−Npfipn|fi, ipn|ni, i+pf|fi, i×∑j=1Mqjpf|fj, iuffi, j+pn|fj, iufni, j− pf|nj, iunfi, j−pn|nj, iunni, j, 

(10) ṗffi, l=2Nqiqlpfi1-pf|fi, i×pflpni1-pf|fi, l-pf|fl, i+2Nqiqlpfl1-pf|fl, l×pfipnl1-pf|fl, i-pf|fi, l, 

(11) ṗffi, l=2Npniq2ipfi1-pf|fi, ipfi-pf|fi, i. 

Figure 5 shows the simulation results of the population dynamics for unknown user type model, where it can be seen that theoretical results are consistent with the simulation results. The small gap is probably because of the ignorance of higher orders of α. These results are based on the parameters: uff1=0.4, uff2=0.2, ufn1=0.6, ufn2=0.4, unn1=0.3, unn2=0.5, N=1000, k=20, q1=q2=0.5, α=0.05.

Figure 6 shows the results for the known user type model. As one can see, the population dynamics of known type users make a very large difference than those of unknown type users, which indicates the necessity of type classification. In this simulation, the payoff matrix is chosen as follows with other parameters N = 1,000, k = 20, q(1) = 0.5518, q(2) = 0.4482, α = 0.05.

uff=0.58820.01160.86880.1590, ufn=0.96190.73700.55950.7180,

unf=0.93390.98640.32880.4593, unn=0.24790.33850.65700.2437,

The prediction of the future diffusion dynamics is also illustrated in Figure 7. It can be seen that the graphical EGT can well predict the diffusion dynamics in the future based on past data.

6. Conclusion

In this paper, we summarized three papers (Jiang et al., 2014a, 2014b and Cao et al., 2016) to discuss how to use the graphical evolutionary game theory to analyze the static state and the dynamics of information diffusion in social network.

Figures

Figure 1.

(a) BD update rule; (b)DB update rule and (c) IM update rule

Figure 2.

Simulation results for the real-world Facebook network.

Figure 3.

Graph structure and degree characteristic of the Facebook network used for experiment

Figure 4.

Experiment results of ESSs for Facebook network

Figure 5.

Simulation results of the evolution dynamics for the unknown user type

Figure 6.

Simulation results of the evolution dynamics for the known user type

Figure 7.

Prediction of future diffusion dynamics