Modeling Influence Spread in Networks

Modeling How Influence Spreads

At its core, influence propagation is about how a new behavior or belief—an "innovation"—spreads from a small set of initial adopters to a wider population. Given your background in stochastic processes and simulations, you'll recognize that these models are essentially sets of rules that govern how the state of nodes (e.g., 'adopts new rule' vs. 'doesn't adopt') evolves over time within a network.

There are several families of models for this process. We will focus on the two most prominent ones in social network analysis: threshold models and cascading models. To get a high-level overview of this landscape, the following reading provides a useful classification.

The Linear Threshold Model: The Power of Social Proof

The first model we'll explore is based on the intuitive idea of social reinforcement. An individual often decides to adopt a new behavior—whether it's trying a new restaurant, joining a protest, or agreeing to a new term in a relationship agreement—only after they see a sufficient number of their peers do so. This is the essence of a threshold model.

The concept was famously explored by sociologist Mark Granovetter to explain collective behavior. He showed that large-scale social phenomena can be triggered by a small number of initial actors, creating a domino effect that depends critically on the distribution of individual thresholds within a population. The video below provides an excellent explanation of this core idea.

As the video explains, what matters is not the average willingness to change, but whether there's a sequence of people with progressively higher thresholds that can be tipped one by one.

Formalizing the Linear Threshold (LT) Model

Now, let's translate this concept into a formal network model. The Linear Threshold model works as follows:

1. Each node v in the network is assigned a threshold, ${\theta }_v$, often chosen randomly from an interval like [0, 1]. This represents how much convincing v needs to adopt the new behavior.
2. Each directed edge (u, v) is given a weight, $w_{uv}$, representing the strength of u's influence on v. For any given node v, the sum of weights from all its incoming neighbors is typically constrained to be less than or equal to 1 (${\sum }_u{w}_{uv}\le 1$).
3. The process starts with an initial set of "active" nodes.
4. In each subsequent step, an inactive node v becomes active if the sum of the influence weights from its already-active neighbors meets or exceeds its threshold: $$\sum _{u\in \text{ActiveNeighbors}(v)}{w}_{uv}\ge {\theta }_v$$

Once a node becomes active, it stays active. The process continues until no more nodes can be activated.

The following image illustrates a few steps of an LT process. The values in each node are (accumulated influence / threshold), and green nodes are the ones that have become active.

For example, looking at the transition from Panel A to Panel B, we see that an initially active node (off-screen or V) has exerted influence on nodes W and U. In Panel B, W's accumulated influence (0.5) has surpassed its threshold (0.1), so it becomes active. U's influence (0.5) has not yet reached its threshold (0.4) - wait, it has. The diagram shows U's threshold as 0.4 and accumulated influence as 0.5 in panel B. So U should be active. There seems to be an inconsistency in this specific diagram's step-by-step progression, but the principle it illustrates is key: activation occurs when cumulative influence from active neighbors crosses an individual's threshold.

The Independent Cascade Model: A Probabilistic Ripple

The second major model, the Independent Cascade (IC) model, frames influence not as an accumulation of pressure but as a series of probabilistic events. The analogy here is less about social proof and more like the spread of a contagious disease or a piece of gossip.

Formalizing the Independent Cascade (IC) Model

The mechanics of the IC model are quite different from the LT model:

1. Each directed edge (u, v) is assigned a propagation probability, $p_{uv}$, representing the chance that u will successfully transmit the behavior to v.
2. The process starts with an initial set of "active" nodes.
3. In each subsequent step, every node u that just became active in the previous step gets a single chance to activate each of its inactive neighbors v. This attempt succeeds with probability $p_{uv}$.
4. If the attempt is successful, v becomes active in the next step. Whether the attempt succeeds or fails, u cannot try to activate v again.
5. The process continues until no new activations occur in a step.

The video lecture we saw earlier also provides a concise definition of this model.

Comparing the Models and Their Application to Vees

The LT and IC models capture different intuitions about influence.

• Linear Threshold is well-suited for modeling the adoption of costly or risky behaviors that require significant social proof. In a vee, this could represent a decision to adopt a major new relationship rule (e.g., a new communication protocol, a change in living arrangements). A partner might only agree if they feel both the hinge and their metamour (the other partner) are strongly committed, with the combined influence overcoming their personal threshold of hesitation. The activation rule, which sums influence from all active neighbors, naturally models this need for reinforcement from multiple sources.

• Independent Cascade is more appropriate for the spread of simple, low-cost information where each exposure provides an independent chance of adoption. This could model the spread of a piece of news or gossip within a polyamorous network. If the hinge tells P1 a story, there's a certain probability P1 believes it and passes it on. The "one chance" rule captures the idea that hearing the same story again from the hinge doesn't necessarily increase the chance of believing it further; the initial attempt is what matters most.

This table provides a quick summary of the key differences:

Interestingly, despite their conceptual differences, research has shown that these two models are, in a more general sense, equivalent. This means that for any process described by one model, an equivalent process can be constructed using the other. While the technical details are beyond our scope, it's a powerful result that unifies these two perspectives on diffusion.

Conclusion

In this lesson, we have moved from static network analysis to the dynamics of influence propagation. We described the two foundational models used to understand how behaviors and ideas spread through a social structure.

• Key Takeaways:
  • Influence propagation models simulate how a behavior spreads from node to node in a network.
  • The Linear Threshold (LT) model assumes activation occurs when the cumulative influence from active neighbors surpasses a node's personal threshold. It models behaviors requiring social reinforcement.
  • The Independent Cascade (IC) model assumes activation is a probabilistic event where newly active nodes get one chance to "infect" their neighbors. It models the spread of simple information or low-cost behaviors.
  • The choice of model depends on the nature of the "innovation" being spread: LT is for high-threshold, reinforcement-dependent behaviors, while IC is for low-cost, contagious information.

Preview of the next lesson:
Now that we have the theoretical tools, it's time to put them into practice. In our next lesson, we will apply a threshold model to simulate influence propagation in a hypothetical vee network scenario. This will allow us to see how changes in influence weights and individual thresholds can dramatically alter the dynamics of agreement and change within the relationship structure.