IM-RW: Maximizing Social Influence by Unleashing the Power of Online Activities

TL;DR

Most social influence models focus only on who your "friends" are. This paper argues that what you do (online activities) is just as important. By modeling social networks as hypergraphs—where activities are shared edges among groups—and using a clever Random Walk (IM-RW) algorithm, the authors achieved higher influence spread with a fraction of the computing power required by current SOTA methods like IMM.

Background: The "Activity" Blind Spot

In the world of viral marketing, finding the "seed set" (the most influential users) is the holy grail. For a decade, the academic community has optimized the Influence Maximization Problem (IMP) using friendship graphs.

However, modern Online Social Networks (OSNs) are driven by activities:

• Joining the same discussion group on Facebook.
• Commenting on the same product page.
• Liking the same brand.

These are Social-Activity Networks (SANs). If you and I both comment on the same niche product, we might influence each other even if we aren't "friends." Previous models either ignored this or tried to turn every activity into a "virtual friendship," making the graph so dense that algorithms crashed or took hours to run.

Methodology: Hypergraphs and Random Walks

The authors propose a shift from simple graphs to Hypergraphs. In this model, an activity is a "hyperedge" containing all participating users.

1. The Influence Centrality

Instead of calculating exact influence spread (which is NP-hard), they define Influence Centrality ($I(S)$). This measure is based on the decayed hitting probability: the likelihood that a random walker starting at user $j$ will hit a "seed" user in $S$ within a certain number of steps, with the probability decreasing ($c$) as the path gets longer.

2. The Influence Model

The probability of user $i$ influencing user $j$ ($g_{ij}$) is split:

• Friendship Influence: A fraction $(1-\alpha )$ comes from direct neighbors.
• Activity Influence: A fraction $\alpha$ comes from shared hyperedges.

3. Optimization: Parallel Walks and Reuse

The real "secret sauce" is the Optimized Greedy Algorithm. Standard greedy selection is slow because it recalculates influence for every possible new seed. The authors use:

• Parallel Computation: Estimating the marginal gain of all nodes simultaneously during a single set of random walks.
• Walk Reuse: Storing random walk paths in memory to update influence scores instantly when a new seed is added, rather than starting from scratch.

Experimental Showdown

The authors tested IM-RW against IMM (the gold standard) on datasets like Yelp and Flixster.

Efficiency Gains

IM-RW is shockingly fast. In many cases, while IMM took tens or hundreds of seconds to find influential nodes (after a long preprocessing phase), IM-RW finished in less than 1 second.

Figure: IM-RW consistently stays below the time cost of IMM across various seed sizes.

Influence Spread

By taking activities into account, the "quality" of the seeds found was much higher. The "Improvement Ratio" (the extra people reached vs. friendship-only models) grew rapidly as the importance of activities ($\alpha$) increased.

Figure: The benefit of incorporating activities is undeniable, showing massive improvements in total network coverage.

Critical Insight

The brilliance of this work lies in the Inductive Bias that activities are the primary bridge for influence in modern networks. By avoiding the "densification" of the graph (turning hyperedges into many simple edges), they kept the math sparse and the computation tractable.

Conclusion & Future Look

IM-RW proves that you don't need a supercomputer to find influential people if you model the context of their interactions correctly.

• Takeaway: Viral marketing campaigns should target "Activity Hubs" (groups/comments) rather than just "Popular People" (high-degree friendship nodes).
• Limitation: The model assumes we know the weight ($\alpha$) of how much activities matter. In the real world, these weights might change dynamically over time.
• Future Work: Applying this hypergraph-walk approach to Multi-modal networks (where activities could be images, text, or purchases) is the next logical step.

Paper: Rui Wang et al., "On Modeling Influence Maximization in Social Activity Networks under General Settings," ACM TKDD 2021.