Pattern Based Graph Generator

Hong-Han Shuai, De-Nian Yang, Philip S. Yu, Chih-Ya Shen, Ming-Syan Chen

Abstract

Viral marketing is different from other marketing strategies since it leverages the influence power in intimate relationship, e.g., close friends, family members, couples. Due to the development and popularity of social networking services, such as Facebook, Twitter, and Pinterest, the new notion of "social media marketing" has appeared in recent years and presents new opportunities for enabling large-scale and prevalent viral marketing online. To boost the growth of their sales, business is embracing social media in a big way. According to USA Today, the sales of software to run corporate social networks will grow 61% a year and be a $6.4$ billion business by 2016.

Introduction

Traditional Influence Maximization (IM) research typically focuses on a simplified objective: identifying a fixed set of $k$ "seed" users who can trigger the largest cascade of information or adoption within a social network. While this theoretical framework has provided significant insights into network topology and information flow, it often fails to capture the complexities of real-world marketing campaigns. In practice, companies do not operate in a vacuum of single-channel social influence. Instead, they manage fluid budgets across multiple advertising channels—such as television, digital billboards, and direct social media engagement—simultaneously.

Furthermore, the ultimate goal of a commercial campaign is rarely "reach" for its own sake; rather, it is the maximization of total revenue relative to the costs of acquisition. To bridge this gap, this paper introduces the CAMAIX (Cost-Aware Multi-Way Influence Maximization) framework. CAMAIX moves beyond simple seed selection to address the more realistic challenge of allocating budgets across diverse channels to maximize net profit in a multi-way influence environment.

The CAMAIX Problem

The CAMAIX problem is fundamentally more complex than standard IM for three primary reasons:

  1. Multi-Channel Integration: It accounts for "external" influence (traditional advertising) and "internal" influence (peer-to-peer social effects) working in tandem.
  2. Variable Budgets: Rather than a fixed number of seeds, the model assumes a financial budget that must be distributed to activate seeds through various "ways," each with different costs and success probabilities.
  3. Economic Realism: It incorporates a sophisticated revenue model that considers the cost of incentives (like discounts) and the expected return from each activated user.

Because the number of seeds is not fixed and the search space for budget allocation is massive, the problem is #P-hard, necessitating a highly efficient algorithmic approach.

Methodology: The ISSBA Framework

To solve the CAMAIX problem, the authors propose the ISSBA (Intermediate Seeds Selection with Budget Allocation) framework. ISSBA is designed to provide a balance between computational efficiency and theoretical rigor through three core components:

Social Influence Pruning (SIP)

In a network of $n$ users, there are $2^n$ possible seed combinations. SIP avoids this combinatorial explosion by incrementally constructing the seed set. It maintains a collection of high-potential intermediate subsets and expands them iteratively. By pruning less promising candidates early in the process, SIP keeps the computation manageable even for massive social graphs.

Adaptive Budget Allocation (ABA)

Once potential seeds are identified, the framework must determine the most cost-effective way to activate them. ABA utilizes Dynamic Programming to optimize the split of the total budget across different advertising channels. This ensures that the probability of activating the chosen seed nodes is maximized for every dollar spent.

Maximum Influence Arborescence (MIA)

Traditional IM algorithms often rely on Monte-Carlo simulations to estimate influence spread, which is computationally prohibitive for large-scale applications. ISSBA integrates the MIA model, which approximates influence by focusing on the most likely paths of transmission within the social graph. This allows for rapid estimation without sacrificing significant accuracy.

Experimental Evaluation

The proposed framework was evaluated using diverse datasets, including Telecom Call Detail Records (CDRs). These real-world logs provided a high-fidelity social network to study intra-network influence and the effectiveness of discount-based activation models.

Key Results

  • Scalability: ISSBA demonstrated the ability to handle large-scale datasets where traditional greedy algorithms, such as CELF, often fail due to the lack of a fixed seed constraint.
  • Performance: Experimental results indicate that ISSBA consistently outperforms baseline algorithms in both total revenue generation and computational runtime.
  • Theoretical Guarantee: One of the paper's most significant contributions is the proof of a 1/2 approximation ratio. This ensures that the solution provided by ISSBA is guaranteed to be at least half as effective as the theoretical optimum, providing a reliable safety net for commercial applications.

Conclusion and Future Work

CAMAIX represents a significant step toward making influence maximization practical for the modern marketing landscape. By recognizing that ads and social influence are complementary, and that budget is a fluid resource, the framework provides a robust tool for revenue-driven decision-making.

Future research directions include adapting the framework for dynamic networks where influence levels and social ties evolve over time. Additionally, the authors suggest exploring more complex interplays between advertising channels—for instance, how a television advertisement might create a "priming effect" that increases the conversion rate of a subsequent social media recommendation.

Summary updated

Abstract

Viral marketing is different from other marketing strategies since it leverages the influence power in intimate relationship, e.g., close friends, family members, couples. Due to the development and popularity of social networking services, such as Facebook, Twitter, and Pinterest, the new notion of "social media marketing" has appeared in recent years and presents new opportunities for enabling large-scale and prevalent viral marketing online. To boost the growth of their sales, business is embracing social media in a big way. According to USA Today, the sales of software to run corporate social networks will grow 61\% a year and be a $6.4$ billion business by 2016.
BibTeX
@misc{shuai2013pattern,
  author = {Hong-Han Shuai and De-Nian Yang and Philip S. Yu and Chih-Ya Shen and Ming-Syan Chen},
  title = {{Pattern Based Graph Generator}},
  year = {2013},
  eprint = {1303.0157},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1303.0157},
}
Figure