Search

Prisoner's dilemma game is the most commonly used model of spatial evolutionary game which is considered as a paradigm to portray competition among selfish individuals. In recent years, Win-Stay-Lose-Learn, a strategy updating rule base on aspiration, has been proved to be an effective model to promote cooperation in spatial prisoner's dilemma game, which leads aspiration to receive lots of attention. But in many research the assumption that individual's aspiration is fixed is inconsistent with recent results from psychology. In this paper, according to Expected Value Theory and Achievement Motivation Theory, we propose a dynamic aspiration model based on Win-Stay-Lose-Learn rule in which individual's aspiration is inspired by its payoff. It is found that dynamic aspiration has a significant impact on the evolution process, and different initial aspirations lead to different results, which are called Stable Coexistence under Low Aspiration, Dependent Coexistence under Moderate aspiration and Defection Explosion under High Aspiration respectively. Furthermore, a deep analysis is performed on the local structures which cause cooperator's existence or defector's expansion, and the evolution process for different parameters including strategy and aspiration. As a result, the intrinsic structures leading to defectors' expansion and cooperators' survival are achieved for different evolution process, which provides a penetrating understanding of the evolution. Compared to fixed aspiration model, dynamic aspiration introduces a more satisfactory explanation on population evolution laws and can promote deeper comprehension for the principle of prisoner's dilemma., Comment: 17 pages, 13 figures

The graph structure is a commonly used data storage mode, and it turns out that the low-dimensional embedded representation of nodes in the graph is extremely useful in various typical tasks, such as node classification, link prediction , etc. However, most of the existing approaches start from the binary relationship (i.e., edges) in the graph and have not leveraged the higher order local structure (i.e., motifs) of the graph. Here, we propose mGCMN -- a novel framework which utilizes node feature information and the higher order local structure of the graph to effectively generate node embeddings for previously unseen data. Through research we have found that different types of networks have different key motifs. And the advantages of our method over the baseline methods have been demonstrated in a large number of experiments on citation network and social network datasets. At the same time, a positive correlation between increase of the classification accuracy and the clustering coefficient is revealed. It is believed that using high order structural information can truly manifest the potential of the network, which will greatly improve the learning efficiency of the graph neural network and promote a brand-new learning mode establishment., Comment: 7 pages, 4 figures

Community detection is of fundamental significance for understanding the topology characters and the spreading dynamics on complex networks. While random walk is widely used and is proven effective in many community detection algorithms, there still exists two major defects: (i) the maximal length of random walk is too large to distinguish the clustering information if using the average step of all possible random walks; (ii) the useful community information at all other step lengths are missed if using a pre-assigned maximal length. In this paper, we propose a novel community detection method based on the first passage probabilities (FPPM), equipped with a new similarity measure that incorporates the complete structural information within the maximal step length. Here the diameter of the network is chosen as an appropriate boundary of random walks which is adaptive to different networks. Then we use the hierarchical clustering to group the vertices into communities and further select the best division through the corresponding modularity values. Finally, a post-processing strategy is designed to integrate the unreasonable small communities, which significantly improves the accuracy of community division. Surprisingly, the numerical simulations show that FPPM performs best compared to several classic algorithms on both synthetic benchmarks and real-world networks, which reveals the universality and effectiveness of our method.

Social reinforcement mechanism, which characterizes the promoting effects when exposing to multiple sources in social contagion process, is ubiquitous in information-technology ecosystem and has aroused great attention in recent years. While the impacts of social reinforcement on single-layer networks are well-documented, extension to multilayer networks is needed to study how reinforcement from different social circles influences the spreading dynamics. To this end, we incorporate multilayer social reinforcement into ignorant-spreader-ignorant (SIS) model on multiplex networks. Our theoretical analysis combines pairwise method and mean-field theory and agrees well with large-scale simulations. Surprisingly, we find this complex social contagion mechanism triggers the emergence of bistability phenomena, where extinction and outbreak states coexist. In particular, the hysteresis loop of stationary prevalence occurs in this bistable region, explaining why the fight towards the spread of rumors is protracted and difficult in modern society. Further, we show that the final state of bistable regions depends on the initial density of adopters, the critical value of which decreases as the contagion transmissibility or the multilayer reinforcement increases. In particular, we highlight two possible conditions for the outbreak of social contagion: to possess large contagion transmissibility, or to possess large initial density of adopters with strong multilayer reinforcement. Our results unveil the non-negligible power of social reinforcement on multiplex networks, which sheds lights on designing efficient strategies in spreading behaviors such as marketing and promoting innovations.

In recent years, social media has increasingly become an important platform for political campaigns, especially elections. It remains elusive how exactly public discourse is driven by the intricate interplay between individual socio-cognitive biases, dueling campaign efforts, and social media platforms. We examine this complex socio-political process by integrating observed retweet networks from the 2016 political networks with an agent-based model of political opinion formation and network structure. Here we show that the range of political viewpoints individuals are willing to consider is a key determinant in the formation of polarized networks and the emergence of echo chambers. We also find that winning majority support in public discourse is determined by both the effort exerted by campaigns and the relative ideological positioning of opposing campaigns. Our results demonstrate how public discourse and political polarization can be modeled as an interactive process of shifting individual opinions, evolving social networks, and political campaigns.

In this paper, solution space organization of minimum vertex-cover problem is deeply investigated using the K\"{o}nig-Eg\'{e}rvary (KE) graph and theorem, in which a hierarchical decomposition mechanism named KE-layer structure of general graphs is proposed to reveal the complexity of vertex-cover. An algorithm to verify the KE graph is given by the solution space expression of vertex-cover, and the relation between multi-layer KE graphs and maximal matching is illustrated and proved. Furthermore, a framework to calculate the KE-layer number and approximate the minimal vertex-cover is provided, with different strategies of switching nodes and counting energy. The phase transition phenomenon between different KE-layers are studied with the transition points located, and searching of vertex-cover got by this strategy presents comparable advantage against several other methods. The graphical representation and hierarchical decomposition provide a new perspective to illustrate the intrinsic complexity for large-scale graphs/systems recognition., Comment: 20 pages, 6 figures

Competitive information diffusion on large-scale social networks reveals fundamental characteristics of rumor contagions and has profound influence on public opinion formation. There has been growing interest in exploring dynamical mechanisms of the competing evolutions recently. Nevertheless, the impacts of population homophily, which determines powerful collective human behaviors, remains unclear. In this paper, we incorporate homophily effects into a modified competitive ignorant-spreader-ignorant (SIS) rumor diffusion model with generalized population preference. Using microscopic Markov chain approach, we first derive the phase diagram of competing diffusion results and examine how competitive information spreads and evolves on social networks. We then explore the detailed effects of homophily, which is modeled by a rewiring mechanism. Results show that homophily promotes the formation of divided "echo chambers" and protects the disadvantaged information from extinction, which further changes or even reverses the evolutionary advantage, i.e., the difference of final proportions of the competitive information. We highlight the conclusion that the reversals may happen only when the initially disadvantaged information has stronger transmission ability, owning diffusion advantage over the other one. Our framework provides profound insight into competing dynamics with population homophily, which may pave ways for further controlling misinformation and guiding public belief systems. Moreover, the reversing condition sheds light on designing effective competing strategies in many real scenarios.

Leaf-Removal process has been widely researched and applied in many mathematical and physical fields to help understand the complex systems, and a lot of problems including the minimal vertex-cover are deeply related to this process and the Leaf-Removal cores. In this paper, based on the structural features of the Leaf-Removal cores, a method named Core Influence is proposed to break the graphs into No-Leaf-Removal-Core ones, which takes advantages of identifying some significant nodes by localized and greedy strategy. By decomposing the minimal vertex-cover problem into the Leaf-Removal cores breaking process and maximal matching of the remained graphs, it is proved that any minimal vertex-covers of the whole graph can be located into these two processes, of which the latter one is a P problem, and the best boundary is achieved at the transition point. Compared with other node importance indices, the Core Influence method could break down the Leaf-Removal cores much faster and get the no-core graphs by removing fewer nodes from the graphs. Also, the vertex-cover numbers resulted from this method are lower than existing node importance measurements, and compared with the exact minimal vertex-cover numbers, this method performs appropriate accuracy and stability at different scales. This research provides a new localized greedy strategy to break the hard Leaf-Removal Cores efficiently and heuristic methods could be constructed to help understand some NP problems., Comment: 11pages, 6 figures, 2 tables

Models of contagion dynamics, originally developed for infectious diseases, have proven relevant to the study of information, news, and political opinions in online social systems. Modelling diffusion processes and predicting viral information cascades are important problems in network science. Yet, many studies of information cascades neglect the variation in infectivity across different pieces of information. Here, we employ early-time observations of online cascades to estimate the infectivity of distinct pieces of information. Using simulations and data from real-world Twitter retweets, we demonstrate that these estimated infectivities can be used to improve predictions about the virality of an information cascade. Developing our simulations to mimic the real-world data, we consider the effect of the limited effective time for transmission of a cascade and demonstrate that a simple model for slow but non-negligible decay of the infectivity captures the essential properties of retweet distributions. These results demonstrate the interplay between the intrinsic infectivity of a tweet and the complex network environment within which it diffuses, strongly influencing the likelihood of becoming a viral cascade., Comment: 16 pages, 10 figures

When analyzing the statistical and topological characteristics of complex networks, an effective and convenient way is to compute the centralities for recognizing influential and significant nodes or structures, yet most of them are restricted to local environment or some specific configurations. In this paper we propose a new centrality for nodes based on the von Neumann entropy, which allows us to investigate the importance of nodes in the view of spectrum eigenvalues distribution. By presenting the performances of this centrality with network examples in reality, it is shown that the von Neumann entropy node centrality is an excellent index for selecting crucial nodes as well as classical ones. Then to lower down the computational complexity, an approximation calculation to this centrality is given which only depends on its first and second neighbors. Furthermore, in the optimal spreader problem and reducing average clustering coefficients, this entropy centrality presents excellent efficiency and unveil topological structure features of networks accurately. The entropy centrality could reduce the scales of giant connected components fastly in Erdos-Renyi and scale-free networks, and break down the cluster structures efficiently in random geometric graphs. This new methodology reveals the node importance in the perspective of spectrum, which provides a new insight into networks research and performs great potentials to discover essential structural features in networks., Comment: 11 pages, 7 figures, 3 tables

The evolution of network structure and the spreading of epidemic are common coexistent dynamical processes. In most cases, network structure is treated either static or time-varying, supposing the whole network is observed in a same time window. In this paper, we consider the epidemic spreading on a network consisting of both static and time-varying structures. At meanwhile, the time-varying part and the epidemic spreading are supposed to be of the same time scale. We introduce a static and activity driven coupling (SADC) network model to characterize the coupling between static (strong) structure and dynamic (weak) structure. Epidemic thresholds of SIS and SIR model are studied on SADC both analytically and numerically with various coupling strategies, where the strong structure is of homogeneous or heterogeneous degree distribution. Theoretical thresholds obtained from SADC model can both recover and generalize the classical results in static and time-varying networks. It is demonstrated that weak structures can make the epidemics break out much more easily in homogeneous coupling but harder in heterogeneous coupling when keeping same average degree in SADC networks. Furthermore, we show there exists a threshold ratio of the weak structure to have substantive effects on the breakout of the epidemics. This promotes our understanding of why epidemics can still break out in some social networks even we restrict the flow of the population.

Information spreading in online social communities has attracted tremendous attention due to its utmost practical values in applications. Despite that several individual-level diffusion data have been investigated, we still lack the detailed understanding of the spreading pattern of information. Here, by comparing information flows and social links in a blog community, we find that the diffusion processes are induced by three different spreading mechanisms: social spreading, self-promotion and broadcast. Although numerous previous studies have employed epidemic spreading models to simulate information diffusion, we observe that such models fail to reproduce the realistic diffusion pattern. In respect to users behaviors, strikingly, we find that most users would stick to one specific diffusion mechanism. Moreover, our observations indicate that the social spreading is not only crucial for the structure of diffusion trees, but also capable of inducing more subsequent individuals to acquire the information. Our findings suggest new directions for modeling of information diffusion in social systems and could inform design of efficient propagation strategies based on users behaviors.

Detecting spreading outbreaks in social networks with sensors is of great significance in applications. Inspired by the formation mechanism of human's physical sensations to external stimuli, we propose a new method to detect the influence of spreading by constructing excitable sensor networks. Exploiting the amplifying effect of excitable sensor networks, our method can better detect small-scale spreading processes. At the same time, it can also distinguish large-scale diffusion instances due to the self-inhibition effect of excitable elements. Through simulations of diverse spreading dynamics on typical real-world social networks (facebook, coauthor and email social networks), we find that the excitable senor networks are capable of detecting and ranking spreading processes in a much wider range of influence than other commonly used sensor placement methods, such as random, targeted, acquaintance and distance strategies. In addition, we validate the efficacy of our method with diffusion data from a real-world online social system, Twitter. We find that our method can detect more spreading topics in practice. Our approach provides a new direction in spreading detection and should be useful for designing effective detection methods.

Identifying highly susceptible individuals in spreading processes is of great significance in controlling outbreaks. In this paper, we explore the susceptibility of people in susceptible-infectious-recovered (SIR) and rumor spreading dynamics. We first study the impact of community structure on people's susceptibility. Despite that the community structure can reduce the infected population given same infection rates, it will not deterministically affect nodes' susceptibility. We find the susceptibility of individuals is sensitive to the choice of spreading dynamics. For SIR spreading, since the susceptibility is highly correlated to nodes' influence, the topological indicator k-shell can better identify highly susceptible individuals, outperforming degree, betweenness centrality and PageRank. In contrast, in rumor spreading model, where nodes' susceptibility and influence have no clear correlation, degree performs the best among considered topological measures. Our finding highlights the significance of both topological features and spreading mechanisms in identifying highly susceptible population.

A number of predictors have been suggested to detect the most influential spreaders of information in online social media across various domains such as Twitter or Facebook. In particular, degree, PageRank, k-core and other centralities have been adopted to rank the spreading capability of users in information dissemination media. So far, validation of the proposed predictors has been done by simulating the spreading dynamics rather than following real information flow in social networks. Consequently, only model-dependent contradictory results have been achieved so far for the best predictor. Here, we address this issue directly. We search for influential spreaders by following the real spreading dynamics in a wide range of networks. We find that the widely-used degree and PageRank fail in ranking users' influence. We find that the best spreaders are consistently located in the k-core across dissimilar social platforms such as Twitter, Facebook, Livejournal and scientific publishing in the American Physical Society. Furthermore, when the complete global network structure is unavailable, we find that the sum of the nearest neighbors' degree is a reliable local proxy for user's influence. Our analysis provides practical instructions for optimal design of strategies for "viral" information dissemination in relevant applications., Comment: 12 pages, 7 figures