Maximizing ROI in Social Networks: The gSEIR Model and Cost-Constrained Influence

Executive Summary

TL;DR: This paper tackles the "Influence Maximization with Limit Cost" (IMLC) problem by moving beyond simple seed counting to a budget-aware ecosystem. It introduces gSEIR, a graph-based epidemic model that captures the nuance of information "exposure" vs. "infection," and proposes a Lagrange relaxation heuristic (HILR) that outclasses standard greedy algorithms in maximizing influence within a fixed budget.

Positioning: This work bridges the gap between traditional epidemiology (SIR models) and modern social network mining, transforming a combinatorial optimization problem into a solvable integer programming task.

Motivation: Why "Number of Seeds" is the Wrong Metric

In traditional Influence Maximization (IM), the goal is often to find $k$ nodes that maximize reach. However, in real-world marketing, not all users are equal. A "celebrity" node might have massive reach but requires a significant "cost" (incentive) to activate, whereas a "micro-influencer" is cheaper but less effective.

The authors identify two major gaps:

1. Dynamic Complexity: Existing models like IC (Independent Cascade) don't account for the "Recovered" state—where a user grows tired of information and stops spreading it.
2. Economic Reality: Budget limits are the primary bottleneck in any SNS campaign, requiring a solution to the NP-complete Weighted Set Cover Problem.

Methodology: From Epidemiology to Graph Theory

1. The gSEIR Model

The core of the simulation is the gSEIR (Susceptible-Exposed-Infectious-Recovered) model. Unlike the SIR model which looks at macro-statistics, gSEIR operates on the micro-level of the graph:

• Exposed (E): Nodes that have seen the info but haven't acted on it.
• Infectious (I): Nodes spreading the info.
• Recovered (R): Nodes that have moved on and are immune to further infection.

The Infectious Probability ($p_i$) is modeled as a Poisson process based on the accumulated interaction frequency with infectious neighbors:

2. The HILR Algorithm

Instead of a simple greedy search, the authors frame IMLC as an integer programming problem. They apply Lagrange Relaxation, converting hard budget constraints into a penalty function in the objective. This allows the algorithm to iteratively adjust the "value" of each node based on its cost and marginal influence contribution.

Figure 1: Visualizing how intersections in exposed sets affect total influence.

Experimental Validation

Using the Enron Email Dataset and Hartford Drug User Data, the authors compared gSEIR against traditional SIR and various algorithms (MCF, MIF, MIC, MCE).

Precision in Spreading

gSEIR showed a remarkable ability to predict "peaks" in information flow. In the Enron dataset, for the topic "Bankruptcy," gSEIR predicted a peak of 111.4 nodes, strikingly close to the real-world peak of 105, whereas the SIR model failed completely with a prediction of 7.79.

Efficiency vs. Effectiveness

While Greedy algorithms are faster (lower scalability cost), the HILR (Lagrange) method achieved the highest Infection-Cost Ratio.

Figure 2: HILR (LR) consistently achieves higher reach than greedy counterparts at various cost thresholds.

Critical Insight & Conclusion

The Takeaway: The "Exposed" state is the missing link in social influence modeling. By accounting for the probability that a node sees information but remains dormant until a threshold of social pressure is met, gSEIR provides a much more realistic simulation of viral content than previous "activation" models.

Limitations: The algorithm requires pre-processing the maximum influence set for individuals, which can be computationally expensive for massive graphs (millions of nodes) without further optimization in the Monte Carlo simulation phase.

Future Outlook: This framework paves the way for "Precision Marketing" in SNS, where budgets are allocated not just to the most connected nodes, but to the most "cost-effective" clusters within the community.