Influence Maximization for Fixed Heterogeneous Thresholds.

Influence Maximization is a NP-hard problem of selecting the optimal set of influencers in a network. Here, we propose two new approaches to influence maximization based on two very different metrics. The first metric, termed Balanced Index (BI), is fast to compute and assigns top values to two kinds of nodes: those with high resistance to adoption, and those with large out-degree. This is done by linearly combining three properties of a node: its degree, susceptibility to new opinions, and the impact its activation will have on its neighborhood. Controlling the weights between those three terms has a huge impact on performance. The second metric, termed Group Performance Index (GPI), measures performance of each node as an initiator when it is a part of randomly selected initiator set. In each such selection, the score assigned to each teammate is inversely proportional to the number of initiators causing the desired spread. These two metrics are applicable to various cascade models; here we test them on the Linear Threshold Model with fixed and known thresholds. Furthermore, we study the impact of network degree assortativity and threshold distribution on the cascade size for metrics including ours. The results demonstrate our two metrics deliver strong performance for influence maximization.

Limits of Predictability of Cascading Overload Failures in Spatially-Embedded Networks with Distributed Flows.

Cascading failures are a critical vulnerability of complex information or infrastructure networks. Here we investigate the properties of load-based cascading failures in real and synthetic spatially-embedded network structures, and propose mitigation strategies to reduce the severity of damages caused by such failures. We introduce a stochastic method for optimal heterogeneous distribution of resources (node capacities) subject to a fixed total cost. Additionally, we design and compare the performance of networks with N-stable and (N-1)-stable network-capacity allocations by triggering cascades using various real-world node-attack and node-failure scenarios. We show that failure mitigation through increased node protection can be effectively achieved against single-node failures. However, mitigating against multiple node failures is much more difficult due to the combinatorial increase in possible sets of initially failing nodes. We analyze the robustness of the system with increasing protection, and find that a critical tolerance exists at which the system undergoes a phase transition, and above which the network almost completely survives an attack. Moreover, we show that cascade-size distributions measured in this region exhibit a power-law decay. Finally, we find a strong correlation between cascade sizes induced by individual nodes and sets of nodes. We also show that network topology alone is a weak predictor in determining the progression of cascading failures.

Effects of communication burstiness on consensus formation and tipping points in social dynamics.

Current models for opinion dynamics typically utilize a Poisson process for speaker selection, making the waiting time between events exponentially distributed. Human interaction tends to be bursty though, having higher probabilities of either extremely short waiting times or long periods of silence. To quantify the burstiness effects on the dynamics of social models, we place in competition two groups exhibiting different speakers' waiting-time distributions. These competitions are implemented in the binary naming game and show that the relevant aspect of the waiting-time distribution is the density of the head rather than that of the tail. We show that even with identical mean waiting times, a group with a higher density of short waiting times is favored in competition over the other group. This effect remains in the presence of nodes holding a single opinion that never changes, as the fraction of such committed individuals necessary for achieving consensus decreases dramatically when they have a higher head density than the holders of the competing opinion. Finally, to quantify differences in burstiness, we introduce the expected number of small-time activations and use it to characterize the early-time regime of the system.

Assortative Mating: Encounter-Network Topology and the Evolution of Attractiveness.

We model a social-encounter network where linked nodes match for reproduction in a manner depending probabilistically on each node's attractiveness. The developed model reveals that increasing either the network's mean degree or the "choosiness" exercised during pair formation increases the strength of positive assortative mating. That is, we note that attractiveness is correlated among mated nodes. Their total number also increases with mean degree and selectivity during pair formation. By iterating over the model's mapping of parents onto offspring across generations, we study the evolution of attractiveness. Selection mediated by exclusion from reproduction increases mean attractiveness, but is rapidly balanced by skew in the offspring distribution of highly attractive mated pairs.

Spatial Competition: Roughening of an Experimental Interface.

Limited dispersal distance generates spatial aggregation. Intraspecific interactions are then concentrated within clusters, and between-species interactions occur near cluster boundaries. Spread of a locally dispersing invader can become motion of an interface between the invading and resident species, and spatial competition will produce variation in the extent of invasive advance along the interface. Kinetic roughening theory offers a framework for quantifying the development of these fluctuations, which may structure the interface as a self-affine fractal, and so induce a series of temporal and spatial scaling relationships. For most clonal plants, advance should become spatially correlated along the interface, and width of the interface (where invader and resident compete directly) should increase as a power function of time. Once roughening equilibrates, interface width and the relative location of the most advanced invader should each scale with interface length. We tested these predictions by letting white clover (Trifolium repens) invade ryegrass (Lolium perenne). The spatial correlation of clover growth developed as anticipated by kinetic roughening theory, and both interface width and the most advanced invader's lead scaled with front length. However, the scaling exponents differed from those predicted by recent simulation studies, likely due to clover's growth morphology.

Competing effects of social balance and influence.

We study a three-state (leftist, rightist, centrist) model that couples the dynamics of social balance with an external deradicalizing field. The mean-field analysis shows that there exists a critical value of the external field p_{c} such that for a weak external field (pp_{c}), there is only one (stable) fixed point, which corresponds to an all-centrist consensus state (absorbing state). In the weak-field regime, the convergence time to the absorbing state is evaluated using the quasistationary distribution and is found to be in agreement with the results obtained by numerical simulations.

Building damage-resilient dominating sets in complex networks against random and targeted attacks.

We study the vulnerability of dominating sets against random and targeted node removals in complex networks. While small, cost-efficient dominating sets play a significant role in controllability and observability of these networks, a fixed and intact network structure is always implicitly assumed. We find that cost-efficiency of dominating sets optimized for small size alone comes at a price of being vulnerable to damage; domination in the remaining network can be severely disrupted, even if a small fraction of dominator nodes are lost. We develop two new methods for finding flexible dominating sets, allowing either adjustable overall resilience, or dominating set size, while maximizing the dominated fraction of the remaining network after the attack. We analyze the efficiency of each method on synthetic scale-free networks, as well as real complex networks.

Extreme fluctuations in stochastic network coordination with time delays.

We study the effects of uniform time delays on the extreme fluctuations in stochastic synchronization and coordination problems with linear couplings in complex networks. We obtain the average size of the fluctuations at the nodes from the behavior of the underlying modes of the network. We then obtain the scaling behavior of the extreme fluctuations with system size, as well as the distribution of the extremes on complex networks, and compare them to those on regular one-dimensional lattices. For large complex networks, when the delay is not too close to the critical one, fluctuations at the nodes effectively decouple, and the limit distributions converge to the Fisher-Tippett-Gumbel density. In contrast, fluctuations in low-dimensional spatial graphs are strongly correlated, and the limit distribution of the extremes is the Airy density. Finally, we also explore the effects of nonlinear couplings on the stability and on the extremes of the synchronization landscapes.

Dominating scale-free networks using generalized probabilistic methods.

We study ensemble-based graph-theoretical methods aiming to approximate the size of the minimum dominating set (MDS) in scale-free networks. We analyze both analytical upper bounds of dominating sets and numerical realizations for applications. We propose two novel probabilistic dominating set selection strategies that are applicable to heterogeneous networks. One of them obtains the smallest probabilistic dominating set and also outperforms the deterministic degree-ranked method. We show that a degree-dependent probabilistic selection method becomes optimal in its deterministic limit. In addition, we also find the precise limit where selecting high-degree nodes exclusively becomes inefficient for network domination. We validate our results on several real-world networks, and provide highly accurate analytical estimates for our methods.

Opinion dynamics and influencing on random geometric graphs.

We investigate the two-word Naming Game on two-dimensional random geometric graphs. Studying this model advances our understanding of the spatial distribution and propagation of opinions in social dynamics. A main feature of this model is the spontaneous emergence of spatial structures called opinion domains which are geographic regions with clear boundaries within which all individuals share the same opinion. We provide the mean-field equation for the underlying dynamics and discuss several properties of the equation such as the stationary solutions and two-time-scale separation. For the evolution of the opinion domains we find that the opinion domain boundary propagates at a speed proportional to its curvature. Finally we investigate the impact of committed agents on opinion domains and find the scaling of consensus time.

Threshold-limited spreading in social networks with multiple initiators.

A classical model for social-influence-driven opinion change is the threshold model. Here we study cascades of opinion change driven by threshold model dynamics in the case where multiple initiators trigger the cascade, and where all nodes possess the same adoption threshold ϕ. Specifically, using empirical and stylized models of social networks, we study cascade size as a function of the initiator fraction p. We find that even for arbitrarily high value of ϕ, there exists a critical initiator fraction pc(ϕ) beyond which the cascade becomes global. Network structure, in particular clustering, plays a significant role in this scenario. Similarly to the case of single-node or single-clique initiators studied previously, we observe that community structure within the network facilitates opinion spread to a larger extent than a homogeneous random network. Finally, we study the efficacy of different initiator selection strategies on the size of the cascade and the cascade window.

Network coordination and synchronization in a noisy environment with time delays.

We study the effects of nonzero time delays in stochastic synchronization problems with linear couplings in complex networks. We consider two types of time delays: transmission delays between interacting nodes and local delays at each node (due to processing, cognitive, or execution delays). By investigating the underlying fluctuations for several delay schemes, we obtain the synchronizability threshold (phase boundary) and the scaling behavior of the width of the synchronization landscape, in some cases for arbitrary networks and in others for specific weighted networks. Numerical computations allow the behavior of these networks to be explored when direct analytical results are not available. We comment on the implications of these findings for simple locally or globally weighted network couplings and possible trade-offs present in such systems.

Accelerating consensus on coevolving networks: the effect of committed individuals.

Social networks are not static but, rather, constantly evolve in time. One of the elements thought to drive the evolution of social network structure is homophily-the need for individuals to connect with others who are similar to them. In this paper, we study how the spread of a new opinion, idea, or behavior on such a homophily-driven social network is affected by the changing network structure. In particular, using simulations, we study a variant of the Axelrod model on a network with a homophily-driven rewiring rule imposed. First, we find that the presence of rewiring within the network, in general, impedes the reaching of consensus in opinion, as the time to reach consensus diverges exponentially with network size N. We then investigate whether the introduction of committed individuals who are rigid in their opinion on a particular issue can speed up the convergence to consensus on that issue. We demonstrate that as committed agents are added, beyond a critical value of the committed fraction, the consensus time growth becomes logarithmic in network size N. Furthermore, we show that slight changes in the interaction rule can produce strikingly different results in the scaling behavior of consensus time, T(c). However, the benefit gained by introducing committed agents is qualitatively preserved across all the interaction rules we consider.

Interference competition and invasion: spatial structure, novel weapons and resistance zones.

Certain invasive plants may rely on interference mechanisms (e.g., allelopathy) to gain competitive superiority over native species. But expending resources on interference presumably exacts a cost in another life-history trait, so that the significance of interference competition for invasion ecology remains uncertain. We model ecological invasion when combined effects of preemptive and interference competition govern interactions at the neighborhood scale. We consider three cases. Under "novel weapons," only the initially rare invader exercises interference. For "resistance zones" only the resident species interferes, and finally we take both species as interference competitors. Interference increases the other species' mortality, opening space for colonization. However, a species exercising greater interference has reduced propagation, which can hinder its colonization of open sites. Interference never enhances a rare invader's growth in the homogeneously mixing approximation to our model. But interference can significantly increase an invader's competitiveness, and its growth when rare, if interactions are structured spatially. That is, interference can increase an invader's success when colonization of open sites depends on local, rather than global, species densities. In contrast, interference enhances the common, resident species' resistance to invasion independently of spatial structure, unless the propagation-cost is too great. The particular combination of propagation and interference producing the strongest biotic resistance in a resident species depends on the shape of the tradeoff between the two traits. Increases in background mortality (i.e., mortality not due to interference) always reduce the effectiveness of interference competition.

Social consensus through the influence of committed minorities.

We show how the prevailing majority opinion in a population can be rapidly reversed by a small fraction p of randomly distributed committed agents who consistently proselytize the opposing opinion and are immune to influence. Specifically, we show that when the committed fraction grows beyond a critical value p(c) ≈ 10%, there is a dramatic decrease in the time T(c) taken for the entire population to adopt the committed opinion. In particular, for complete graphs we show that when p < pc, T(c) ~ exp [α(p)N], whereas for p>p(c), T(c) ~ ln N. We conclude with simulation results for Erdos-Rényi random graphs and scale-free networks which show qualitatively similar behavior.

Social influencing and associated random walk models: Asymptotic consensus times on the complete graph.

We investigate consensus formation and the asymptotic consensus times in stylized individual- or agent-based models, in which global agreement is achieved through pairwise negotiations with or without a bias. Considering a class of individual-based models on finite complete graphs, we introduce a coarse-graining approach (lumping microscopic variables into macrostates) to analyze the ordering dynamics in an associated random-walk framework. Within this framework, yielding a linear system, we derive general equations for the expected consensus time and the expected time spent in each macro-state. Further, we present the asymptotic solutions of the 2-word naming game and separately discuss its behavior under the influence of an external field and with the introduction of committed agents.

Network synchronization in a noisy environment with time delays: fundamental limits and trade-offs.

We study the effects of nonzero time delays in stochastic synchronization problems with linear couplings in an arbitrary network. Using the known exact threshold value from the theory of differential equations with delays, we provide the synchronizability threshold for an arbitrary network. Further, by constructing the scaling theory of the underlying fluctuations, we establish the absolute limit of synchronization efficiency in a noisy environment with uniform time delays, i.e., the minimum attainable value of the width of the synchronization landscape. Our results also have strong implications for optimization and trade-offs in network synchronization with delays.

Interplay between structural randomness, composite disorder, and electrical response: resonances and transient delays in complex impedance networks.

We study the interplay between structural and conductivity (composite) disorder and the collective electrical response in random network models. Translating the problem of time-dependent electrical response (resonance and transient relaxation) in binary random composite networks to the framework of generalized eigenvalues, we study and analyze the scaling behavior of the density of resonances in these structures. We found that by controlling the density of shortcuts (topological randomness) and/or the composite ratio of the binary links (conductivity disorder), one can effectively shape resonance landscapes or suppress or enhance long transient delays in the corresponding random impedance networks.

Preemptive spatial competition under a reproduction-mortality constraint.

Spatially structured ecological interactions can shape selection pressures experienced by a population's different phenotypes. We study spatial competition between phenotypes subject to antagonistic pleiotropy between reproductive effort and mortality rate. The constraint we invoke reflects a previous life-history analysis; the implied dependence indicates that although propagation and mortality rates both vary, their ratio is fixed. We develop a stochastic invasion approximation predicting that phenotypes with higher propagation rates will invade an empty environment (no biotic resistance) faster, despite their higher mortality rate. However, once population density approaches demographic equilibrium, phenotypes with lower mortality are favored, despite their lower propagation rate. We conducted a set of pairwise invasion analyses by simulating an individual-based model of preemptive competition. In each case, the phenotype with the lowest mortality rate and (via antagonistic pleiotropy) the lowest propagation rate qualified as evolutionarily stable among strategies simulated. This result, for a fixed propagation to mortality ratio, suggests that a selective response to spatial competition can extend the time scale of the population's dynamics, which in turn decelerates phenotypic evolution.

Ecological invasion, roughened fronts, and a competitor's extreme advance: integrating stochastic spatial-growth models.

Both community ecology and conservation biology seek further understanding of factors governing the advance of an invasive species. We model biological invasion as an individual-based, stochastic process on a two-dimensional landscape. An ecologically superior invader and a resident species compete for space preemptively. Our general model includes the basic contact process and a variant of the Eden model as special cases. We employ the concept of a "roughened" front to quantify effects of discreteness and stochasticity on invasion; we emphasize the probability distribution of the front-runner's relative position. That is, we analyze the location of the most advanced invader as the extreme deviation about the front's mean position. We find that a class of models with different assumptions about neighborhood interactions exhibits universal characteristics. That is, key features of the invasion dynamics span a class of models, independently of locally detailed demographic rules. Our results integrate theories of invasive spatial growth and generate novel hypotheses linking habitat or landscape size (length of the invading front) to invasion velocity, and to the relative position of the most advanced invader.