Enhanced cooperation in multiplayer snowdrift games with random and dynamic groupings.

An analytically tractable generalization of the N-person snowdrift (NSG) game that illustrates how cooperation can be enhanced is proposed and studied. The number of players competing within a NSG varies from one time step to another. Exact equations governing the frequency of cooperation f_{c}(r) as a function of the cost-to-benefit ratio r within an imitation strategy updating scheme are presented. For group sizes g uniformly distributed within the range g∈[1,g_{m}], an analytic formula for the critical value r_{c}(g_{m}), below which the system evolves into a totally cooperative (AllC) state, is derived. In contrast, a fixed group size NSG does not support an AllC state. The result r_{c}(g_{m}) requires the presence of sole-player groups and involves the inverse of the harmonic numbers and, more generally, the inverse first moment of the group size distribution. For r>r_{c}(g_{m}), the equation that determines the dynamical mixed states f_{c}(r) is given, with exact solutions existing for g_{m}≤5. The exact treatment allows the study of the phase boundary between the AllC state and the mixed states. The analytic results are checked against simulation results and exact agreements are demonstrated. The analytic form of the critical r_{c}(g_{m}) illustrates the necessity of having groups of a sole player in the evolutionary process. This result is supported by simulations with group sizes excluding the sole groups for which no AllC state emerges. A physically transparent picture of the importance of the sole players in inducing an AllC state is further presented based on the last surviving pattern before the AllC state is attained. The exact expression r_{c}(g_{m}) turns out to remain valid for nonuniform group-size distributions. Our analytical tractable generalization, therefore, sheds light on how a competing environment with variable group sizes could enhance cooperation and induce an AllC state.

Non-Markovian recovery makes complex networks more resilient against large-scale failures.

Non-Markovian spontaneous recovery processes with a time delay (memory) are ubiquitous in the real world. How does the non-Markovian characteristic affect failure propagation in complex networks? We consider failures due to internal causes at the nodal level and external failures due to an adverse environment, and develop a pair approximation analysis taking into account the two-node correlation. In general, a high failure stationary state can arise, corresponding to large-scale failures that can significantly compromise the functioning of the network. We uncover a striking phenomenon: memory associated with nodal recovery can counter-intuitively make the network more resilient against large-scale failures. In natural systems, the intrinsic non-Markovian characteristic of nodal recovery may thus be one reason for their resilience. In engineering design, incorporating certain non-Markovian features into the network may be beneficial to equipping it with a strong resilient capability to resist catastrophic failures.

Getting closer to the goal by being less capable.

Understanding how systems with many semi-autonomous parts reach a desired target is a key question in biology (e.g., Drosophila larvae seeking food), engineering (e.g., driverless navigation), medicine (e.g., reliable movement for brain-damaged individuals), and socioeconomics (e.g., bottom-up goal-driven human organizations). Centralized systems perform better with better components. Here, we show, by contrast, that a decentralized entity is more efficient at reaching a target when its components are less capable. Our findings reproduce experimental results for a living organism, predict that autonomous vehicles may perform better with simpler components, offer a fresh explanation for why biological evolution jumped from decentralized to centralized design, suggest how efficient movement might be achieved despite damaged centralized function, and provide a formula predicting the optimum capability of a system's components so that it comes as close as possible to its target or goal.

Controlling epidemic outbreak based on local dynamic infectiousness on complex networks.

Resources are limited in epidemic containment; how to optimally allocate the limited resources in suppressing the epidemic spreading has been a challenging problem. To find an effective resource allocation strategy, we take the infectiousness of each infected node into consideration. By studying the interplay between the resource allocation and epidemic spreading, we find that the spreading dynamics of epidemic is affected by the preferential resource allocation. There are double phase transitions of the fraction of infected nodes, which are different from the classical epidemic model. More importantly, we find that the preferential resource allocation has double-edged sword effects on the disease spreading. When there is a small transmission rate, the infected fraction at the steady state decreases with the increment of degree of resource allocation preference, which indicates that resources of the healthy nodes should be allocated preferentially to the high infectious nodes to constrain the disease spreading. Moreover, when there is a large transmission rate, the fraction of infected nodes at the steady state increases with the increment of the degree of the preference, but the resource allocation is determined by the stage of epidemic spreading. Namely, in the early stage of the disease spreading, resources should be allocated preferentially to the high infectious nodes similar to the case of a small transmission rate. While after the early stage, resources should be allocated to the low infectious nodes. Based on the findings, we propose a simple resource allocation strategy that can adaptively change with the current fraction of infected nodes and the disease can be suppressed to the most extent under the proposed strategy.

Accurate ranking of influential spreaders in networks based on dynamically asymmetric link weights.

We propose an efficient and accurate measure for ranking spreaders and identifying the influential ones in spreading processes in networks. While the edges determine the connections among the nodes, their specific role in spreading should be considered explicitly. An edge connecting nodes i and j may differ in its importance for spreading from i to j and from j to i. The key issue is whether node j, after infected by i through the edge, would reach out to other nodes that i itself could not reach directly. It becomes necessary to invoke two unequal weights w_{ij} and w_{ji} characterizing the importance of an edge according to the neighborhoods of nodes i and j. The total asymmetric directional weights originating from a node leads to a novel measure s_{i}, which quantifies the impact of the node in spreading processes. An s-shell decomposition scheme further assigns an s-shell index or weighted coreness to the nodes. The effectiveness and accuracy of rankings based on s_{i} and the weighted coreness are demonstrated by applying them to nine real-world networks. Results show that they generally outperform rankings based on the nodes' degree and k-shell index while maintaining a low computational complexity. Our work represents a crucial step towards understanding and controlling the spread of diseases, rumors, information, trends, and innovations in networks.

Atypical viral dynamics from transport through popular places.

The flux of visitors through popular places undoubtedly influences viral spreading-from H1N1 and Zika viruses spreading through physical spaces such as airports, to rumors and ideas spreading through online spaces such as chat rooms and social media. However, there is a lack of understanding of the types of viral dynamics that can result. Here we present a minimal dynamical model that focuses on the time-dependent interplay between the mobility through and the occupancy of such spaces. Our generic model permits analytic analysis while producing a rich diversity of infection profiles in terms of their shapes, durations, and intensities. The general features of these theoretical profiles compare well to real-world data of recent social contagion phenomena.

Integrated travel network model for studying epidemics: Interplay between journeys and epidemic.

The ease of travelling between cities has contributed much to globalization. Yet, it poses a threat on epidemic outbreaks. It is of great importance for network science and health control to understand the impact of frequent journeys on epidemics. We stress that a new framework of modelling that takes a traveller's viewpoint is needed. Such integrated travel network (ITN) model should incorporate the diversity among links as dictated by the distances between cities and different speeds of different modes of transportation, diversity among nodes as dictated by the population and the ease of travelling due to infrastructures and economic development of a city, and round-trip journeys to targeted destinations via the paths of shortest travel times typical of human journeys. An example is constructed for 116 cities in China with populations over one million that are connected by high-speed train services and highways. Epidemic spread on the constructed network is studied. It is revealed both numerically and theoretically that the traveling speed and frequency are important factors of epidemic spreading. Depending on the infection rate, increasing the traveling speed would result in either an enhanced or suppressed epidemic, while increasing the traveling frequency enhances the epidemic spreading.

Internal character dictates transition dynamics between isolation and cohesive grouping.

We show that accounting for internal character among interacting heterogeneous entities generates rich transition behavior between isolation and cohesive dynamical grouping. Our analytical and numerical calculations reveal different critical points arising for different character-dependent grouping mechanisms. These critical points move in opposite directions as the population's diversity decreases. Our analytical theory may help explain why a particular class of universality is so common in the real world, despite the fundamental differences in the underlying entities. It also correctly predicts the nonmonotonic temporal variation in connectivity observed recently in one such system.

An efficient immunization strategy for community networks.

An efficient algorithm that can properly identify the targets to immunize or quarantine for preventing an epidemic in a population without knowing the global structural information is of obvious importance. Typically, a population is characterized by its community structure and the heterogeneity in the weak ties among nodes bridging over communities. We propose and study an effective algorithm that searches for bridge hubs, which are bridge nodes with a larger number of weak ties, as immunizing targets based on the idea of referencing to an expanding friendship circle as a self-avoiding walk proceeds. Applying the algorithm to simulated networks and empirical networks constructed from social network data of five US universities, we show that the algorithm is more effective than other existing local algorithms for a given immunization coverage, with a reduced final epidemic ratio, lower peak prevalence and fewer nodes that need to be visited before identifying the target nodes. The effectiveness stems from the breaking up of community networks by successful searches on target nodes with more weak ties. The effectiveness remains robust even when errors exist in the structure of the networks.

Instability in evolutionary games.

BACKGROUND: Phenomena of instability are widely observed in many dissimilar systems, with punctuated equilibrium in biological evolution and economic crises being noticeable examples. Recent studies suggested that such instabilities, quantified by the abrupt changes of the composition of individuals, could result within the framework of a collection of individuals interacting through the prisoner's dilemma and incorporating three mechanisms: (i) imitation and mutation, (ii) preferred selection on successful individuals, and (iii) networking effects. METHODOLOGY/PRINCIPAL FINDINGS: We study the importance of each mechanism using simplified models. The models are studied numerically and analytically via rate equations and mean-field approximation. It is shown that imitation and mutation alone can lead to the instability on the number of cooperators, and preferred selection modifies the instability in an asymmetric way. The co-evolution of network topology and game dynamics is not necessary to the occurrence of instability and the network topology is found to have almost no impact on instability if new links are added in a global manner. The results are valid in both the contexts of the snowdrift game and prisoner's dilemma. CONCLUSIONS/SIGNIFICANCE: The imitation and mutation mechanism, which gives a heterogeneous rate of change in the system's composition, is the dominating reason of the instability on the number of cooperators. The effects of payoffs and network topology are relatively insignificant. Our work refines the understanding on the driving forces of system instability.

Emergence of scale-free close-knit friendship structure in online social networks.

Although the structural properties of online social networks have attracted much attention, the properties of the close-knit friendship structures remain an important question. Here, we mainly focus on how these mesoscale structures are affected by the local and global structural properties. Analyzing the data of four large-scale online social networks reveals several common structural properties. It is found that not only the local structures given by the indegree, outdegree, and reciprocal degree distributions follow a similar scaling behavior, the mesoscale structures represented by the distributions of close-knit friendship structures also exhibit a similar scaling law. The degree correlation is very weak over a wide range of the degrees. We propose a simple directed network model that captures the observed properties. The model incorporates two mechanisms: reciprocation and preferential attachment. Through rate equation analysis of our model, the local-scale and mesoscale structural properties are derived. In the local-scale, the same scaling behavior of indegree and outdegree distributions stems from indegree and outdegree of nodes both growing as the same function of the introduction time, and the reciprocal degree distribution also shows the same power-law due to the linear relationship between the reciprocal degree and in/outdegree of nodes. In the mesoscale, the distributions of four closed triples representing close-knit friendship structures are found to exhibit identical power-laws, a behavior attributed to the negligible degree correlations. Intriguingly, all the power-law exponents of the distributions in the local-scale and mesoscale depend only on one global parameter, the mean in/outdegree, while both the mean in/outdegree and the reciprocity together determine the ratio of the reciprocal degree of a node to its in/outdegree. Structural properties of numerical simulated networks are analyzed and compared with each of the four real networks. This work helps understand the interplay between structures on different scales in online social networks.

Effect of social group dynamics on contagion.

Despite the many works on contagion phenomena in both well-mixed systems and heterogeneous networks, there is still a lack of understanding of the intermediate regime where social group structures evolve on a similar time scale to individual-level transmission. We address this question by considering the process of transmission through a model population comprising social groups which follow simple dynamical rules for growth and breakup. Despite the simplicity of our model, the profiles produced bear a striking resemblance to a wide variety of real-world examples--in particular, empirical data that we have obtained for social (i.e., YouTube), financial (i.e., currency markets), and biological (i.e., colds in schools) systems. The observation of multiple resurgent peaks and abnormal decay times is qualitatively reproduced within the model simply by varying the time scales for group coalescence and fragmentation. We provide an approximate analytic treatment of the system and highlight a novel transition which arises as a result of the social group dynamics.

Human group formation in online guilds and offline gangs driven by a common team dynamic.

Quantifying human group dynamics represents a unique challenge. Unlike animals and other biological systems, humans form groups in both real (offline) and virtual (online) spaces-from potentially dangerous street gangs populated mostly by disaffected male youths to the massive global guilds in online role-playing games for which membership currently exceeds tens of millions of people from all possible backgrounds, age groups, and genders. We have compiled and analyzed data for these two seemingly unrelated offline and online human activities and have uncovered an unexpected quantitative link between them. Although their overall dynamics differ visibly, we find that a common team-based model can accurately reproduce the quantitative features of each simply by adjusting the average tolerance level and attribute range for each population. By contrast, we find no evidence to support a version of the model based on like-seeking-like (i.e., kinship or "homophily").

An alternative approach to characterize the topology of complex networks and its application in epidemic spreading.

Based on the mean-field approach, epidemic spreading has been well studied. However, the mean-field approach cannot show the detailed contagion process, which is important in the control of epidemic. To fill this gap, we present a novel approach to study how the topological structure of complex network influences the concrete process of epidemic spreading. After transforming the network structure into hierarchical layers, we introduce a set of new parameters, i.e., the average fractions of degree for outgoing, ingoing, and remaining in the same layer, to describe the infection process. We find that this set of parameters are closely related to the degree distribution and the clustering coefficient but are more convenient than them in describing the process of epidemic spreading. Moreover, we find that the networks with exponential distribution have slower spreading speed than the networks with power-law degree distribution. Numerical simulations have confirmed the theoretical predictions.

Spies in the minority game.

We study the effects of the existence of another type of agents, called spies, in the minority game (MG). Unlike the normal agents in the MG, the spies do not carry any strategy. Instead, they decide their action by scouting some normal agents and take the minority action of the spied group. For a few spies and when there is useful information in the normal agents' actions, the spies can avoid the crowd effect of the normal agents and win more readily. When information becomes less useful and when more spies are present, the spies' crowd effect hurts the success rate of the spies themselves, and the normal agents could have a higher success rate than the spies. More spies actually assist more normal agents to win, as the spies also provide more winning quotas. This leads to a nonmonotonic behavior in the total success rate of the population as a function of the fraction of spies.

Wave characteristics in gratings by linear superposition of retarded fields.

We present a formalism for the wave characteristics in gratings and periodic dielectrics based on the linear superposition of retarded fields. The idea is based on the physical picture that an incident field affects the charges in the material forming the gratings and hence leads to oscillating current and charge densities, which in turn generate more fields via the retarded potential. A set of self-consistent equations for the electric field and current and charge densities is derived. Expressions for the electric field everywhere, including the reflected and transmitted fields, are derived. The formalism is then applied to the calculation of diffraction efficiency so as to illustrate its application and to establish its validity by comparing results with the rigorous coupled-wave method. We further generalize the formalism to include possible anisotropy and nonlinearity in the response of the material forming the grating.

Error-driven global transition in a competitive population on a network.

We show, both analytically and numerically, that erroneous data transmission generates a global transition within a competitive population playing the "Minority Game" on a network. This transition, which resembles a phase transition, is driven by a "temporal symmetry breaking" in the global outcome series. The phase boundary, which is a function of the network connectivity p and the error probability q, is described quantitatively by the crowd-anticrowd theory.