Abstract
In this paper, we propose the Amphibious Influence Maximization (AIM) model, a unified framework that integrates traditional top-down marketing (via content providers) with peer-to-peer viral marketing within social networks. In the AIM model, content providers and consumers form a bipartite network, while consumers are simultaneously embedded in a social network where influence propagates according to the Independent Cascade (IC) model. The objective is to select an optimal subset of seed content providers and seed consumers to maximize the expected total influence spread. We demonstrate that the general AIM problem is NP-hard to approximate within any constant factor. However, by assuming the weighted bi-adjacency matrix representing provider-to-consumer influence is of constant rank—a standard assumption in recommender systems—we develop a polynomial-time algorithm achieving an approximation ratio of $(1-1/e-\epsilon)^3$. Our results extend to any social diffusion model characterized by monotone and submodular functions.
Introduction
Marketing strategies have historically been bifurcated into two distinct domains: traditional marketing and viral marketing. Traditional marketing focuses on "top-down" influence, where advertisers leverage content providers (e.g., media outlets, influential bloggers, or television networks) to reach a broad audience. Conversely, viral marketing focuses on "peer-to-peer" influence, where the goal is to trigger a cascade of information sharing among consumers within a social network.
In the modern digital landscape, these two mechanisms are inextricably linked. A consumer might be exposed to a product via a content provider but only decides to share that information if they are also influenced by their peers, or vice versa. This paper introduces the Amphibious Influence Maximization (AIM) model to bridge this gap, providing a mathematical framework for advertisers to optimize their seeding strategies across both content providers and consumers simultaneously.
The Amphibious Influence Maximization (AIM) Model
The AIM model represents the marketing environment as two interconnected structures:
- A Bipartite Graph: Connecting a set of content providers ($P$) to a set of consumers ($C$). This represents the reach of traditional media.
- A Social Graph: Connecting consumers ($C$) to one another. This represents the viral potential of the consumer base.
Influence propagates in stages. First, an advertiser selects a set of seed providers ($S_P$) and a set of seed consumers ($S_C$). Influence flows from $S_P$ to the consumers in $C$. A consumer is successfully "activated" if they are reached by the providers and are part of the seed set $S_C$, or if they are subsequently reached through the social network via the Independent Cascade (IC) model. The advertiser's goal is to maximize the total number of influenced consumers given fixed budgets for both provider and consumer seeding.
Computational Hardness
The integration of these two marketing channels introduces significant computational complexity. The authors prove that the AIM problem is NP-hard to approximate to within any constant factor. This proof is derived via a reduction from Feige's $k$-prover proof system for 3-SAT5, a sophisticated tool in computational complexity theory.
Furthermore, the paper provides evidence that even in a simplified scenario where the social network has no edges (i.e., no viral component), finding a constant-factor approximation remains unlikely, as the problem remains as difficult as the "densest-$k$-subgraph" problem. This suggests that the interplay between the bipartite influence and the seeding selection is the primary source of hardness.
The Low-Rank Assumption and the SDG Algorithm
To find a tractable solution for real-world applications, the authors introduce a low-rank assumption. In many practical scenarios, such as those modeled by recommender systems (e.g., the Netflix prize), the influence of providers on consumers is not arbitrary but is driven by a small number of latent factors (e.g., genre preferences or demographic alignment). This implies that the bi-adjacency matrix describing provider-consumer influence has a constant rank $r$.
Under this assumption, the authors propose the Sampled Double Greedy (SDG) algorithm. The algorithm operates by:
- Constructing a $(1+\epsilon)$-net over the low-rank subspace to discretize the search space.
- Utilizing greedy optimization techniques to select the most effective seeds for both providers and consumers within this narrowed space.
Key Results and Generalization
The SDG algorithm provides a significant theoretical breakthrough, achieving an approximation ratio of $(1 - 1/e - \epsilon)^3$ in polynomial time. While the algorithm's complexity is exponential in the rank $r$, it remains highly efficient for the low-dimensional structures typically found in consumer behavior data.
Importantly, the paper demonstrates that these algorithmic results are not limited to the Independent Cascade model. The $(1 - 1/e - \epsilon)^3$ approximation holds for any social network diffusion model where the spread function is monotone and submodular. This covers a wide range of popular models used in viral marketing research, making the AIM framework broadly applicable.
Conclusion
The AIM model provides a rigorous foundation for understanding the synergy between traditional and viral marketing. By identifying the "information bottleneck" in the low-rank structure of provider-consumer interactions, the authors offer a path to overcome the inherent computational hardness of the problem. Future research may focus on empirical validation of the low-rank assumption in diverse markets and the development of adaptive seeding strategies where advertisers can react to influence spreads in real-time.
Summary updated