Precise Persuasion: Routing and Scheduling Social Influence in Online Networks

TL;DR

While most social media research focuses on "going viral" to the masses, this paper tackles the "sniper" approach: how to strategically route a recommendation through a chain of friends to influence one specific target. By introducing the RAS-TOSID problem and the ERASSTO algorithm, the authors prove that timing the "ask" is just as important as choosing the right "asker."

The "Paper Map" Problem in Social Networks

Imagine a salesperson trying to reach a high-profile CEO through mutual connections. Currently, this is done manually—akin to navigating New York with a paper map from 20 years ago. You lack real-time data on when your friends are online or how likely they are to actually pass the message along.

The authors identify two fatal flaws in prior work:

1. Lack of Path Orientation: Most models focus on broadcasting (influence maximization) rather than routing toward a destination.
2. Temporal Blindness: Existing models ignore Inactivity. If a critical link in your chain is only online at 2 AM, sending a request at 2 PM is a recipe for failure.

Methodology: The ERASSTO Framework

The core of the paper is the ERASSTO algorithm (Efficient Routing And Scheduling with Social and Temporal Decomposition).

1. The Social Model (MIIA Adaptation)

Instead of the computationally expensive Independent Cascade (IC) model, the authors use the Maximum Influence In-Arborescence (MIIA). This prunes the social graph into a tree structure of high-probability paths leading to the target.

2. The Temporal Model (Response Probability)

They introduce $r{p}_v^t$, the probability of user $v$ responding at time $t$. The total influence probability isn't just the product of edge weights; it’s a joint event of the intermediate node being influenced AND being active to pass it on.

3. Social and Temporal Decomposition

The problem is solved using dynamic programming. To avoid the exponential complexity of distributing a "node budget" across multiple branches, they use Social Decomposition (iteratively finding the best allocation for $k$ neighbors) and Temporal Decomposition (reusing optimal time-points from previous steps).

The ERASSTO pseudocode illustrates the nested optimization of time (t) and routing budget (x).

Experiments and SOTA Comparison

The authors validated their work with a 123-volunteer user study on Facebook and simulations on massive Flickr datasets (22M links).

Key Findings:

• Manual vs. Algorithmic: Human users are surprisingly bad at selecting long-hop paths. ERASSTO consistently achieved higher target influence probabilities than manual "User" selection.
• Efficiency: While a standard Dynamic Programming approach (RASSTA) might take days to solve for a Facebook-sized graph, ERASSTO delivers results in under a second ($O(n_V{c}^{2}a{u}^2)$).
• Path Quality: Interestingly, ERASSTO tends to find shorter paths than greedy algorithms. By keeping the chain short, it reduces the cumulative risk of a "silent decline" from an inactive user.

The influence probability of ERASSTO (red) significantly outperforms the baseline greedy approach (blue) across different budgets (c) and time scales.

Critical Insight & Conclusion

The true value of this work lies in its Online Adjustment capability. In a real social network, if an intermediate friend refuses to help, the system doesn't just give up; it re-routes the influence budget through an alternative branch in real-time.

Limitations: The model assumes OSN providers (like Meta or LinkedIn) will act as the "navigator." In reality, privacy concerns might limit a provider's ability to automate this chain without explicit user consent at every step.

Future Outlook: This framework opens the door for "Social GPS" services, where AI-guided referrals replace the current trial-and-error method of professional networking.