Information diversity and anomalous scaling in asymmetric social contagion process on low-dimensional static networks.

To understand how competition affects the diversity of information, we study the social contagion model introduced by Halvorsen-Pedersen-Sneppen (HPS) [G. S. Halvorsen, B. N. Pedersen, and K. Sneppen, Phys. Rev. E 103, 022303 (2021)2470-004510.1103/PhysRevE.103.022303] on one-dimensional (1D) and two-dimensional (2D) static networks. By mapping the information value to the height of the interface, we find that the width W(N,t) does not satisfy the well-known Family-Vicsek finite-size scaling ansatz. From the numerical simulations, we find that the dynamic exponent z should be modified for the HPS model. For 1D static networks, the numerical results show that the information landscape is always rough with an anomalously large growth exponent, ß. Based on the analytic derivation of W(N,t), we show that the constant small number of influencers created for unit time and the recruitment of new followers are two processes responsible for the anomalous values of ß and z. Furthermore, we also find that the information landscape on 2D static networks undergoes a roughening transition, and the metastable state emerges only in the vicinity of the transition threshold.

Majority-vote model with degree-weighted influence on complex networks.

We study the phase transition of the degree-weighted majority vote (DWMV) model on Erdos-Rényi networks (ERNs) and scale-free networks (SFNs). In this model, a weight parameter α adjusts the level of influence of each node on its connected neighbors. Through the Monte Carlo simulations and the finite-size scaling analysis, we find that the DWMV model on ERNs and SFNs with degree exponents λ>5 belongs to the mean-field Ising universality class, regardless of α. On SFNs with 3<λ<5 the model belongs to the Ising universality class only when α=0. For α>0 we find that the critical exponents continuously change as α increases from α=0. However, on SFNs with λ<3 we find that the model undergoes a continuous transition only for α=0, but the critical exponents significantly deviate from those for the mean-field Ising model. For α>0 on SFNs with λ<3 the model is always in the disordered phase.

Origin of the log-normal popularity distribution of trending memes in social networks.

We study the origin of the log-normal popularity distribution of trending memes observed in many real social networks. Based on a biological analogy, we introduce a fitness of each meme, which is a natural assumption based on sociological reasons. From numerical simulations, we find that the relative popularity distribution of the trending memes becomes a log-normal distribution when the fitness of the meme increases exponentially. On the other hand, if the fitness grows slowly, then the distribution significantly deviates from the log-normal distribution. This indicates that the fast growth of fitness is the necessary condition for the trending meme. Furthermore, we also show that the popularity of the trending topic grows linearly. These results provide a clue to understand long-lasting questions, such as what causes some memes to become extremely popular and how such memes are exposed to the public much longer than others.

Two order parameters for the Kuramoto model on complex networks.

We investigate the behavior of two different order parameters for the Kuramoto model in the desynchronized phase. Since the primary role of the order parameter is to distinguish different phases, we focus on the ability to discern the desynchronized phase from the synchronized one on complex networks with the size N. From the exact derivation of the difference between two order parameters, Δ, on a star network, we find that these order parameters disagree in the desynchronized phase. We also show that the hub plays an important role and provide an analytic conjecture on the condition that the two order parameters agree with each other as N→∞. The conjecture is numerically confirmed.

Network exploration using true self-avoiding walks.

We study the mean first passage time (MFPT) of true self-avoiding walks (TSAWs) on various networks as a measure of searching efficiency. From the numerical analysis, we find that the MFPT of TSAWs, τ^{TSAW}, approaches the theoretical minimum τ^{th}/N=1/2 on synthetic networks whose degree-degree correlations are positive. On the other hand, for biased random walks (BRWs) we find that the MFPT, τ^{BRW}, depends on the parameter α, which controls the degree-dependent bias. More importantly, we find that the minimum MFPT of BRWs, τ_{min}^{BRW}, always satisfies the inequality τ_{min}^{BRW}>τ^{TSAW} on any synthetic network. The inequality is also satisfied on various real networks. From these results, we show that the TSAW is one of the most efficient models, whose efficiency approaches the theoretical limit in network explorations.

Reciprocity in spatial evolutionary public goods game on double-layered network.

Spatial evolutionary games have mainly been studied on a single, isolated network. However, in real world systems, many interaction topologies are not isolated but many different types of networks are inter-connected to each other. In this study, we investigate the spatial evolutionary public goods game (SEPGG) on double-layered random networks (DRN). Based on the mean-field type arguments and numerical simulations, we find that SEPGG on DRN shows very rich interesting phenomena, especially, depending on the size of each layer, intra-connectivity, and inter-connected couplings, the network reciprocity of SEPGG on DRN can be drastically enhanced through the inter-connected coupling. Furthermore, SEPGG on DRN can provide a more general framework which includes the evolutionary dynamics on multiplex networks and inter-connected networks at the same time.

The origin of the criticality in meme popularity distribution on complex networks.

Previous studies showed that the meme popularity distribution is described by a heavy-tailed distribution or a power-law, which is a characteristic feature of the criticality. Here, we study the origin of the criticality on non-growing and growing networks based on the competition induced criticality model. From the direct Mote Carlo simulations and the exact mapping into the position dependent biased random walk (PDBRW), we find that the meme popularity distribution satisfies a very robust power- law with exponent α = 3/2 if there is an innovation process. On the other hand, if there is no innovation, then we find that the meme popularity distribution is bounded and highly skewed for early transient time periods, while it satisfies a power-law with exponent α ≠ 3/2 for intermediate time periods. The exact mapping into PDBRW clearly shows that the balance between the creation of new memes by the innovation process and the extinction of old memes is the key factor for the criticality. We confirm that the balance for the criticality sustains for relatively small innovation rate. Therefore, the innovation processes with significantly influential memes should be the simple and fundamental processes which cause the critical distribution of the meme popularity in real social networks.

Percolation in spatial evolutionary prisoner's dilemma game on two-dimensional lattices.

We study the spatial evolutionary prisoner's dilemma game with updates of imitation max on triangular, hexagonal, and square lattices. We use the weak prisoner's dilemma game with a single parameter b. Due to the competition between the temptation value b and the coordination number z of the base lattice, a greater variety of percolation properties is expected to occur on the lattice with the larger z. From the numerical analysis, we find six different regimes on the triangular lattice (z=6). Regardless of the initial densities of cooperators and defectors, cooperators always percolate in the steady state in two regimes for small b. In these two regimes, defectors do not percolate. In two regimes for the intermediate value of b, both cooperators and defectors undergo percolation transitions. The defector always percolates in two regimes for large b. On the hexagonal lattice (z=3), there exist two distinctive regimes. For small b, both the cooperators and the defectors undergo percolation transitions while only defectors always percolate for large b. On the square lattice (z=4), there exist three regimes. Combining with the finite-size scaling analyses, we show that all the observed percolation transitions belong to the universality class of the random percolation. We also show how the detailed growth mechanism of cooperator and defector clusters decides each regime.

Quantifying discrepancies in opinion spectra from online and offline networks.

Online social media such as Twitter are widely used for mining public opinions and sentiments on various issues and topics. The sheer volume of the data generated and the eager adoption by the online-savvy public are helping to raise the profile of online media as a convenient source of news and public opinions on social and political issues as well. Due to the uncontrollable biases in the population who heavily use the media, however, it is often difficult to measure how accurately the online sphere reflects the offline world at large, undermining the usefulness of online media. One way of identifying and overcoming the online-offline discrepancies is to apply a common analytical and modeling framework to comparable data sets from online and offline sources and cross-analyzing the patterns found therein. In this paper we study the political spectra constructed from Twitter and from legislators' voting records as an example to demonstrate the potential limits of online media as the source for accurate public opinion mining, and how to overcome the limits by using offline data simultaneously.

Spatial evolutionary public goods game on complete graph and dense complex networks.

We study the spatial evolutionary public goods game (SEPGG) with voluntary or optional participation on a complete graph (CG) and on dense networks. Based on analyses of the SEPGG rate equation on finite CG, we find that SEPGG has two stable states depending on the value of multiplication factor r, illustrating how the "tragedy of the commons" and "an anomalous state without any active participants" occurs in real-life situations. When r is low (<<), the state with only loners is stable, and the state with only defectors is stable when r is high (>>). We also derive the exact scaling relation for r*. All of the results are confirmed by numerical simulation. Furthermore, we find that a cooperator-dominant state emerges when the number of participants or the mean degree, 〈k〉, decreases. We also investigate the scaling dependence of the emergence of cooperation on r and 〈k〉. These results show how "tragedy of the commons" disappears when cooperation between egoistic individuals without any additional socioeconomic punishment increases.

Complete set of types of phase transition in generalized heterogeneous k-core percolation.

We study heterogeneous k-core (HKC) percolation with a general mixture of the threshold k, with k(min) = 2 on random networks. Based on the local tree approximation, the scaling behaviors of the percolation order parameter P(∞)(p) are analytically obtained for general distributions of the threshold k. The analytic calculations predict that the generalized HKC percolation is completely described by the series of continuous transitions with order parameter exponents ß(n) = 2/n, discontinuous hybrid transitions with ß(H) = 1/2 or ß(A)(4)) = 1/4, and three kinds of multiple transitions. Simulations of the generalized HKC percolations are carried out to confirm analytically predicted transition natures. Specifically, the exponents of the series of continuous transitions are shown to satisfy the hyperscaling relation 2ß(n) + γ(n) = ν(n).

Dimensional dependence of phase transitions in explosive percolation.

To understand the dependence of phase-transition natures in explosive percolations on space dimensions, the number n(cut) of cutting bonds (sites) and the fractal dimension d(CSC) of the critical spanning cluster (CSC) for the six different models introduced in Phys. Rev. E 86, 051126 (2012) are studied on two- and three-dimensional lattices. It is found that n(cut)(L→∞)=1 for the intrabond-enhanced models and the site models on the two-dimensional square lattice with lattice size L. In contrast, n(cut) for the intrabond-suppressed models scales as n(cut)≃L(d(cut)) with d(cut)=1. d(CSC)=2.00(1) is obtained for the intrabond-enhanced models and the site models, while d(CSC)=1.96(1)(<2) is obtained for the intrabond-suppressed models in two dimensions (2D). These results strongly support that the intrabond-enhanced models and the site models undergo the discontinuous transition in 2D, while the intrabond-suppressed models do the continuous transition in 2D. On the three-dimensional cubic lattice, we find that d(cut)>0 and d(CSC)=2.8(1)(<3) for all six models, which indicates that the models undergo the continuous transition. Based on the finite-size scaling analyses of mean cluster size and order parameter, all six models in 3D show nearly the same critical phenomena within numerical errors.

Bayesian inference of natural rankings in incomplete competition networks.

Competition between a complex system's constituents and a corresponding reward mechanism based on it have profound influence on the functioning, stability, and evolution of the system. But determining the dominance hierarchy or ranking among the constituent parts from the strongest to the weakest--essential in determining reward and penalty--is frequently an ambiguous task due to the incomplete (partially filled) nature of competition networks. Here we introduce the "Natural Ranking," an unambiguous ranking method applicable to a round robin tournament, and formulate an analytical model based on the Bayesian formula for inferring the expected mean and error of the natural ranking of nodes from an incomplete network. We investigate its potential and uses in resolving important issues of ranking by applying it to real-world competition networks.

Parallel discrete-event simulation schemes with heterogeneous processing elements.

To understand the effects of nonidentical processing elements (PEs) on parallel discrete-event simulation (PDES) schemes, two stochastic growth models, the restricted solid-on-solid (RSOS) model and the Family model, are investigated by simulations. The RSOS model is the model for the PDES scheme governed by the Kardar-Parisi-Zhang equation (KPZ scheme). The Family model is the model for the scheme governed by the Edwards-Wilkinson equation (EW scheme). Two kinds of distributions for nonidentical PEs are considered. In the first kind computing capacities of PEs are not much different, whereas in the second kind the capacities are extremely widespread. The KPZ scheme on the complex networks shows the synchronizability and scalability regardless of the kinds of PEs. The EW scheme never shows the synchronizability for the random configuration of PEs of the first kind. However, by regularizing the arrangement of PEs of the first kind, the EW scheme is made to show the synchronizability. In contrast, EW scheme never shows the synchronizability for any configuration of PEs of the second kind.

Phase transitions in paradigm shift models.

Two general models for paradigm shifts, deterministic propagation model (DM) and stochastic propagation model (SM), are proposed to describe paradigm shifts and the adoption of new technological levels. By defining the order parameter m based on the diversity of ideas, Δ, it is studied when and how the phase transition or the disappearance of a dominant paradigm occurs as a cost C in DM or an innovation probability α in SM increases. In addition, we also investigate how the propagation processes affect the transition nature. From analytical calculations and numerical simulations m is shown to satisfy the scaling relation m=1-f(C/N) for DM with the number of agents N. In contrast, m in SM scales as m=1-f(α(a)N).

Classification of transport backbones of complex networks.

Transport properties in random and scale-free (SF) networks are studied by analyzing the betweenness centrality (BC) distribution P(B) in the minimum spanning trees (MSTs) and infinite incipient percolation clusters (IIPCs) of the networks. It is found that P(B) in MSTs scales as P(B)∼B(-δ). The obtained values of δ are classified into two different categories, δ≃1.6 and δ≃2.0. Using the mapping between BC and the branch size of tree structures, it is proved that δ in MSTs which are close to critical trees is 1.6. In contrast, δ in MSTs which are supercritical trees is shown to be 2.0. We also find δ=1.5 in IIPCs, which is a natural result because IIPC is physically critical. Based on the results in MSTs, a physical reason why δ≥2 in the original networks is suggested.

Bond-site duality and nature of the explosive-percolation phase transition on a two-dimensional lattice.

To establish the bond-site duality of explosive percolations in two dimensions, the site and bond explosive-percolation models are carefully defined on a square lattice. By studying the cluster distribution function and the behavior of the second largest cluster, it is shown that the duality in which the transition is discontinuous exists for the pairs of the site model and the corresponding bond model which relatively enhances the intrabond occupation. In contrast the intrabond-suppressed models which have no corresponding site models undergo a continuous transition and satisfy the normal scaling ansatz as ordinary percolation.

Explosive percolation on the Bethe lattice.

Based on self-consistent equations of the order parameter P∞ and the mean cluster size S, we develop a self-consistent simulation method for arbitrary percolation on the Bethe lattice (infinite homogeneous Cayley tree). By applying the self-consistent simulation to well-known percolation models, random bond percolation, and bootstrap percolation, we obtain prototype functions for continuous and discontinuous phase transitions. By comparing key functions obtained from self-consistent simulations for Achlioptas models with a product rule and a sum rule to the prototype functions, we show that the percolation transition of Achlioptas models on the Bethe lattice is continuous regardless of details of growth rules.

Explosive site percolation with a product rule.

We study the site percolation under Achlioptas process with a product rule in a two-dimensional square lattice. From the measurement of the cluster size distribution P(s), we find that P(s) has a very robust power-law regime followed by a stable hump near the transition threshold. Based on the careful analysis on the PP(s) distribution, we show that the transition should be discontinuous. The existence of the hysteresis loop in order parameter also verifies that the transition is discontinuous in two dimensions. Moreover, we also show that the transition nature from the product rule is not the same as that from a sum rule in two dimensions.

Optimal topology for parallel discrete-event simulations.

The effect of shortcuts on the task completion landscape in parallel discrete-event simulation (PDES) is investigated. The morphology of the task completion landscape in PDES is known to be described well by the Langevin-type equation for nonequillibrium interface growth phenomena, such as the Kardar-Parisi-Zhang equation. From the numerical simulations, we find that the root-mean-squared fluctuation of task completion landscape, W(t,N), scales as W(t→∞,N)~N when the number of shortcuts, ℓ, is finite. Here N is the number of nodes. This behavior can be understood from the mean-field type argument with effective defects when ℓ is finite. We also study the behavior of W(t,N) when ℓ increases as N increases and provide a criterion to design an optimal topology to achieve a better synchronizability in PDES.