Critical Phenomena and Strategy Ordering with Hub Centrality Approach in the Aspiration-based Coordination Game

The Ising model Ising (1925) is represented as the Hamiltonian $H=-J\sum_{\langle i,j\rangle}S_{i}S_{j}$, where the spin $S_{i}$ at node $i$ may take on the values $\pm 1$. The exchange interaction parameter $J$ is set to $1$ and used as the energy unit. It has positive critical temperature $T_{c}$, at which long-range order emerges, in two and higher dimensions.Onsager (1944); Newman and Barkema (1999); Plischke and Bergersen (2006) The critical behavior close to $T_{c}$ is described by the critical exponents, which are exactly known only in two dimensions.Onsager (1944); Newman and Barkema (1999); Plischke and Bergersen (2006) The Ising model can be studied using the Markov-chain Monte Carlo method, where a spin is chosen uniformly at random and the spin is flipped according to a spin-flip probability $P(\mu\rightarrow\nu)$. Any function can be used as the spin-flip probability if it satisfies the detailed balance.Newman and Barkema (1999); Plischke and Bergersen (2006) Among many such functions, we may adopt the heat-bath algorithm:

where $E_{\nu}$ is the energy of state $\nu$ and $T$ is temperature. The Boltzmann constant $k_{B}$ is set to $1$ without loss of generality. The energy change ($E_{\nu}-E_{\mu}$) by the spin-flip is determined by the spin configuration of the neighbors of the chosen spin: $E_{\nu}-E_{\mu}=2D_{s}$, where $D_{s}$ is the number of neighbors with the same spin direction subtracted by the number of neighbors with the opposite spin direction before the spin-flip. Note that $2D_{s}$ is the same as the payoff in the coordination game studied in this paper, and so the spin-flip probability of Eq. (5) is the same as the strategy switch probability of Eq. (1) for $A=0$ if $k_{B}T$ is replaced by $\kappa$. The probability corresponds to Glauber dynamics of kinetic Ising model and potential game with Boltzmann-Gibbs distribution. Glauber (1963); Blume (1993) The logic rule for two strategies in fictitious game is also conceptually equivalent. Fudenberg and Levine (1998); Monderer and Shapley (1996); Koopmans (1951) Therefore, for the specific payoff matrix and aspiration level, the aspiration-based coordination model shows the same results as the Ising model in the critical selection noise (critical temperature), critical exponents, etc.

In the previous subsection, we showed that the aspiration-based coordination game is equal to the Ising model for $A=0$, and it should have the phase transition at finite selection noise. We study the phase transition in the square lattice and RRG in this subsection. The RRG was generated by the algorithm introduced in Ref. Jeong, Jang, and Yu, 2019. The results are averaged over $100\,000$ generations after the system reaches equilibrium and the results of $30$ independent simulations are averaged for the final results.

For each graph, we calculated the critical selection noise ($\kappa_{c}$) and three exponents ($\nu$, $\beta$, and $\gamma$) using finite-size scaling. Physical quantities near the critical selection noise are described by critical exponents: Binder (1981); Ferrenberg and Landau (1991); Yu (2017); Newman and Barkema (1999); Plischke and Bergersen (2006)

where $L$ is the linear size of the lattice ($L=N^{1/2}$ for the square lattice). In the case of complex networks such as RRG, $L$ should be replaced by the number of agents $N$ in Eqs. (6)-(8). Since scaling functions have the same value regardless of the graph size at $\kappa=\kappa_{c}$, critical selection noise $\kappa_{c}$ and critical exponents can be calculated from the values of physical quantities at $\kappa=\kappa_{c}$.Yu (2017); Newman and Barkema (1999); Plischke and Bergersen (2006) According to Eq. (8), $\kappa_{c}$ can be obtained from the intersection of Binder cumulants of different graph sizes. After $\kappa_{c}$ is determined, the critical exponents can be calculated from Eqs. (6), (7), and differentiation of Eq. (8).

Values of the critical selection noise and critical exponents calculated in this way are presented in Table 1. The results for the square lattice are equal to the exact solutions of the two-dimensional (2D) Ising model Onsager (1944) as expected within the margin of error. As for the RRG, the critical exponents are consistent with the mean-field theory (MFT) due to small average-path-length.Barrat and Weigt (2000); Hong, Kim, and Choi (2002) Furthermore, we show that the scaling functions ($\tilde{m}$, $\tilde{\chi}$, and $\tilde{U}$) collapse independently of graph size in Fig. 1. Due to the critical slowing down,Newman and Barkema (1999); Plischke and Bergersen (2006) which appears close to $\kappa_{c}$ in a local update algorithm, a somewhat large statistical error is unavoidable.

We also studied critical behaviors in the highly clustered RRG, which are generated by the algorithm in Ref. Jeong, Jang, and Yu, 2019. They are not always connected networks, but we verified that the proportion of the giant component is at least $99.9\%$. The degree of clustering is quantified by the clustering coefficient $c$ defined by

where $k_{i}$ and $l_{i}$ are the degree and the number of links among the neighbors of agent $i$, respectively.Watts and Strogatz (1998) Figure 2 shows that critical selection noise ($\kappa_{c}$) decreases as the clustering coefficient ($c$) increases; we conjecture the relation

Parameters $g_{1}$ and $g_{2}$ for a given $k$ are obtained by fitting and they are listed in Table 2. Interestingly, the values of $g_{1}$ and $g_{2}$ are very close to $1/4$ and $7/4$, respectively. Notably, the decrease of the critical temperature by clustering in the Ising model is also observed in other small-world networks.Barrat and Weigt (2000); Pȩkalski (2001) We found that the critical exponents do not depend on the clustering coefficient (see Table 1).

Now we present the results of the aspiration-based coordination game with non-zero aspiration level. The simulation methods are the same as the previous subsections. With varying the aspiration level $A$, we calculated critical selection noise $\kappa_{c}$ and critical exponents in the square lattice and RRGs without clustering. We found that $\kappa_{c}$ decreases as $A$ increases (see Fig. 3), but the values of critical exponents are independent of aspiration level in the square lattice and RRGs (see Table 1). We also confirmed the collapse of scaling functions regardless of the graph size for each value of $A$. Therefore, we conclude that the aspiration-based coordination game belongs to the same universality class as the Ising model in spite of nonequilibrium dynamics, as was conjectured by Ref. Grinstein, Jayaprakash, and He, 1985.

Critical selection noise $\kappa_{c}$ approaches zero at $A=k$ and the long-range order vanishes for higher $A$. Since there is a maximum value in the payoff an agent can obtain, the strategy update probability becomes too high to sustain the long-range order above a specific aspiration level $A$. We found no signature of long-range order at and above $A=k$. Interestingly, the critical aspiration level $A_{c}$ is the same as degree $k$ in both square lattice and RRG. Based on this result, we propose a trend function of

As shown in Fig. 3, Eq. (14) fits well for positive $A$ but underestimates $\kappa_{c}(k,A)$ otherwise.

Up to here, we considered only regular graphs. In many cases, however, networks are highly heterogeneous Broido and Clauset (2019) and the heterogeneous degree distribution may affect the properties of the network dramatically.Newman and Girvan (2004); Newman (2002); Barabási and Albert (1999); Santos and Pacheco (2005); Ebel and Bornholdt (2002); Wu and Hadzibeganovic (2020) For example, the critical temperature of the Ising model is infinite in scale-free networks.Bianconi (2002)

In this subsection, we study the effect of aspiration level at a low selection noise in two kinds of model networks and two real-world networks with scale-free degree distribution. Degree distributions of the four networks follow the power-law, $P(k)\propto k^{-\delta}$. Structural properties of the networks we consider in this subsection are presented in Table 3. The exponent of power-law degree distribution $\delta$ in the BA and HK networks is $3$ as expected. The simulations are performed at various aspiration levels. The selection noise is set to $\kappa=0.01$. Each simulation result was averaged over $10\,000$ generations after the system had reached an equilibrium state, and the final results were averaged over $30$ independent simulations.

The results of $\langle m\rangle$ for the four kinds of networks are shown in Fig. 4. For $A\leq 0$, one of the two strategies dominates the networks, and $\langle m\rangle$ decreases to zero as $A$ increases for positive $A$. The change is very abrupt at $A=k_{\mathrm{avg}}$ in BA and HK networks. It is noteworthy that the BA and HK networks show almost the same behavior in spite of a large difference in clustering coefficient. In contrast, in the case of the real-world networks, $\langle m\rangle$ decreases gradually as $A$ increases. The real-world networks have lower $\langle m\rangle$ than the model networks for $A<k_{\mathrm{avg}}$ while it maintains a nonnegligible level for higher $A$.

To understand the remarkably different behaviors in model networks and real-world networks, we checked $\langle m\rangle$ of the agents with each degree near $A=k_{\mathrm{avg}}$, but we found no clue and we conclude that degree of an agent is not a dominating factor in coordination games in real-world networks. Therefore, we propose a new parameter hub centrality $\phi$, which determines the behavior of each agent in the coordination game beyond the degree. The value of hub centrality of an agent is defined as the proportion of the neighbors that have smaller degree than the agent among all its neighbors. For example, if an agent has five neighbors, three of which have neighbors less than five and the other two neighbors have degree of five or more, $\phi$ of the agent is $0.6$. A high value of $\phi$ means that the degree of the agent is high compared to those of its neighbors and the agent plays a leading role in its local environment. Since the hub centrality is determined solely by the degree of the agents in the network, it does not change in static networks.

We measured $\phi$ of all agents and Fig. 5 shows the histogram of degree for a given hub centrality range. Although the results of only BA scale-free network and airports network are shown, those of HK scale-free network and email network are qualitatively the same as Fig. 5(a) and (b), respectively. In the case of model scale-free networks, the value of $\phi$ is proportional to a degree; the peak of histogram shifts to a higher value of the degree as hub centrality increases and all agents with degree more than $100$ have $\phi$ greater than $0.9$. Hub agents are connected with many low-degree agents and are affected critically by their strategies. In this network, sizable agents have a smaller degree than $k_{\mathrm{avg}}$ and cannot obtain enough payoff for $A\geq k_{\mathrm{avg}}$. They change their strategies so often to prevent their neighbors gain enough payoff. This causes the decrease of $\langle m\rangle$ and high-degree agents connected to them cannot keep their strategies, either.

In real-world networks, to the contrary, the histogram separates into two parts as $\phi$ increases, as shown in Fig. 5(b). In other words, there are a considerable number of agents that have a high $\phi$ and a low degree in real-world networks; some agents of $\phi>0.9$ have a degree lower than $k_{\mathrm{avg}}$. They are not hubs but behave like hubs locally, because a large portion of their neighbors has a lower degree. Therefore, we propose to call them local hubs (L-hubs). Figure 6 shows an example of an L-hub in the airports network; the degree of the agent is as low as $8$, but it is higher than all of its neighbors and the hub centrality of the agent is maximum ($\phi=1$). L-hubs have a relatively low degree and they are surrounded by neighbors of lower degree. Therefore, L-hubs and their neighbors can lose ordering, and $\langle m\rangle$ begins to decrease even for $A<k_{\mathrm{avg}}$. Moreover, agents with a high degree have various $\phi$ values: the agents who have a higher degree than $100$ have a broad range of $\phi$ from $0.6$ to $1.0$. This indicates that at least some agents have a considerable number of high-degree neighbors as well as many low-degree neighbors; the payoff of the agents is less influenced by the strategy of agents with low degrees. Thus, the agents can obtain enough payoff even in high aspiration level conditions to keep their ordering though agents with low degree change their strategies frequently.

In order to examine the detailed behavior of each agent as $A$ changes, we measured the Edwards-Anderson order parameter ($q$),Edwards and Anderson (1975); Krawczyk et al. (2005); Yu (2015) which is defined for agent $i$ as

where $\alpha_{i}(t)=1$ if agent $i$ has the strategy S1 at generation $t$ and $\alpha_{i}(t)=-1$ otherwise. After the system reaches equilibrium, $\alpha_{i}$ is measured for each agent $M$ times, once per generation. We fixed $M$ to be $10\,000$. Large value of $q_{i}$ close to 1 means that the agent $i$ is frozen; if $q_{i}\approx 0$, the agent $i$ is melted. If the agent $i$ is partially frozen, $q_{i}$ is moderate value between $0$ and $1$.

In the melting process as $A$ increases, it is important to observe the change of Edwards-Anderson order parameter of agents with high $\phi$, which have considerably larger degrees than their neighbors and indicate the situation of freezing in their neighborhoods.

Figure 7 shows $q$ as a function of $A$ for four agents with high $\phi$ ($\phi>0.9$) in each of BA scale-free network and airports network. Two agents of airports network are classified as L-hub. There is no L-hub in BA scale-free network, where every agent with high $\phi$ has a higher degree than $k_{\mathrm{avg}}$. In the case of BA scale-free network, according to Fig. 7(a), all the four agents are frozen for $A<k_{\mathrm{avg}}$ and they are melted abruptly for $A$ slightly larger than $k_{\mathrm{avg}}$. Agents with high $\phi$ in the HK scale-free network show the same behavior.

According to Fig. 7(b), the two L-hubs (blue triangles and purple inverted triangles) are melted near $A=6$. This means that the subset consisting of the L-hub and its neighbors is melted. Thus, $\langle m\rangle$ of the network begins to decrease at $A<k_{\mathrm{avg}}$.

Another agent, which is represented by red circles, shows a gradual decrease of $q$. When $A$ is zero, the agent is frozen. As $A$ increases, it becomes partially frozen in a specific range; some of its neighbors with a lower degree are melted and this leads to the increase of the strategy update probability of the agent. For $A>20$, the agent is melted completely. The last agent (black squares in Fig. 7(b)), which has a very high degree, keeps its order up to $A=20$. In this case, although some of its neighbors are melted, the agent keeps its strategy interacting with a considerable number of neighbors with high degrees. Due to the presence of such agents, $\langle m\rangle$ is remarkably high at a high aspiration level. Email network also shows qualitatively the same behaviors.

To take a closer look at the melting process of high-$\phi$ agents ($\phi>0.9$) and their neighbors, we calculated the $q$-difference ($D$) of them, which is defined for agent $i$ as

where $\Omega_{i}$ is the set of neighbors of the agent $i$. If all of agent $i$ and its neighbors are melted or frozen, $D_{i}$ becomes almost zero. During the melting process, $D_{i}$ is expected to be positive since high-$\phi$ agents are melted at a larger $A$ than their neighbors. The average of the $q$-difference of high-$\phi$ agents ($D_{\mathrm{avg}}$) at each network is shown in the insets of Fig. 7.

As shown in the inset of Fig. 7(a), $D_{\mathrm{avg}}$ has non-negligible values only in a very narrow region near $A=k_{\mathrm{avg}}$ in BA scale-free network. Immediately after some agents begin to melt near $A=k_{\mathrm{avg}}$, all agents lose the order abruptly as $A$ increases. In the case of airports network (inset of Fig. 7(b)), to the contrary, $D_{\mathrm{avg}}$ has substantially high values in a wide range of $A$ even up to $A=20$. This implies that a considerable number of high-$\phi$ agents keep frozen or partially frozen states up to high $A$ though some of their neighbors are melted.