ELTM: Winning the Viral Marketing War in Competitive Social Networks

TL;DR

In the digital marketplace, products don't exist in a vacuum; they compete. This paper introduces the Extended Linear Threshold Model (ELTM), a framework designed to maximize a brand's reach when a competitor is already present. By proving the objective function is submodular, the authors show that a simple greedy algorithm can capture at least 63% of the optimal influence spread, offering a robust strategy for "underdog" brands to challenge market leaders.

Problem & Motivation: Beyond Single-Product Influence

Most classical research on influence maximization (pioneered by Kempe et al.) assumes a "monopoly" where only one piece of information spreads. In reality, marketing is a battleground.

Current competitive models—mostly based on Independent Cascade (IC) logic—often treat influence as a binary "hit or miss." They ignore the cumulative effect of social pressure. For instance, you might not buy a product after one friend mentions it, but you might after five friends do. The authors identified that existing models lacked:

1. Influence Accumulation: The power of multiple neighbors.
2. Product Strength (Influence Degree): The reality that some brands (like Nike or Apple) have inherently higher persuasion power than others.

Methodology: The Extended Linear Threshold Model (ELTM)

The core innovation is the ELTM, which builds on the classic LT model but adds a competitive layer.

The Mechanics of Persuasion

Each node $v$ in the network has two hidden thresholds ($het{a}_A,het{a}_B$). A node becomes activated by Product A if the weighted sum of its A-activated neighbors, multiplied by A's "influence degree" ($q_A$), exceeds the threshold.

The authors define four decision cases for a node:

• A-only activation: Only Product A's influence exceeds the threshold.
• B-only activation: Only Product B's influence wins.
• Strategic Conflict: If both exceed thresholds, the "bigger weight" or a dominant product (assigned as A in this study) takes the node.
• Inactivity: Neither is strong enough.

The Mathematical Edge: Submodularity

The brilliance of ELTM lies in proving that the influence function $\sigma (S_A,I_B)$ is monotone and submodular. In layman's terms, this means "diminishing returns": adding a seed to a small set helps more than adding it to a large set. This property allows the use of a Greedy Algorithm to find the near-optimal seed set with a guaranteed performance bound of $(1-1/e)$.

Figure 1: The objective function used to solve the NP-hard problem of seed selection.

Experiments & Results

The researchers tested their model on the Cit-HepTh dataset (Arxiv citation network).

1. Greedy vs. The World

As shown in the performance charts, the Greedy algorithm significantly outperformed common heuristics like "Max-Degree" (picking the most connected people) and "Random" selection. This proves that structural influence is more complex than just having many followers; it's about where those followers are positioned relative to the competitor.

Figure 2: Spread of A-activated nodes. The Greedy approach (top line) shows superior growth as more seeds are added.

2. The Power of "Influence Degree"

The study also varied $q_A$ and $q_B$. When Product A had a higher influence degree ($q_A=2/3,q_B=1/2$), its spread grew exponentially faster. This quantifies a vital marketing truth: a better product (higher $q$) requires fewer resources to achieve the same reach.

Figure 3: Impact of relative product strength on total market penetration.

Critical Analysis & Future Outlook

Takeaway: ELTM provides a mathematically sound bridge between social network theory and real-world competitive marketing.

Limitations:

• The model assumes $q_A$ and $q_B$ are static. In reality, a brand's influence degree changes over time due to ad campaigns or scandals.
• The current experiment assumes Product A always wins ties, which is a simplification of market dynamics.

Future Work: The next frontier for this research is Dynamic ELTM, where the competition happens in real-time, and companies can reactively change their seed sets as the "battlefield" shifts.