Beyond Popularity: Maximizing Marketing Profit via Semidefinite Programming in Social Networks

TL;DR

This research shifts the focus of Social Networking Site (SNS) marketing from merely finding "popular" users to identifying "profitable" ones. By modeling social influence as a directed, weighted network (including negative influence like distrust) and solving the target selection problem using Semidefinite Programming (SDP), the authors provide a mathematically rigorous way to maximize net profit—balancing the cost of incentives against the revenue from influenced buyers.

Problem & Motivation: The "Influence" Trap

Most enterprises today use social networks for reputation management and targeted marketing. However, academic research has historically fallen into two traps:

1. The Positivity Bias: Assuming all social links are positive. In reality, "distrust" and "block lists" mean that targeting a specific user might actually alienate others.
2. Breadth vs. Value: Standard algorithms (like Independent Cascade or Linear Threshold) often strive to "activate" the maximum number of nodes. But in business, the goal isn't just reach—it's Profit. If the cost of targeting an influencer exceeds the revenue generated by their followers, the strategy is a failure.

The authors argue that existing Heuristics (like Degree Centrality) and Greedy algorithms often get stuck in local optima, especially when the "threshold" for a user to buy a product is high.

Methodology: Profit-Driven Optimization

The proposed approach follows a structured pipeline: Data Collection $\to$ Influence Network Construction $\to$ SDP Optimization.

1. Mining the Influence Network

The network isn't just a list of followers. It integrates:

• Direct Relationships: Trust (+1) or Block (-1).
• Interaction Sentiment: Using a Sigmoid-like function to map the frequency of helpful/unhelpful ratings and comments into a weight $w\in [-1,1]$.

2. The optimization Model

The core innovation is the formulation of a profit function $au(A)$: $au(A)=r{\sum }_{v\in \bar{A}}g\left({\sum }_{u\in A}{w}_{uv}\right)-c|A|$ Where $r$ is revenue, $c$ is cost, and $g(x)$ is an activation function. To solve this NP-hard combinatorial problem, the authors transform it into an Integer Programming (IP) model and then relax it into a Semidefinite Programming (SDP) problem.

Figure 1: The workflow from SNS data extraction to identifying valuable customers.

Experiments & Results

The authors tested their model on real-world data from Epinions, comparing it against High Weighted-Degree, Weighted-Closeness, and a Greedy Algorithm.

Key Findings:

• Superiority in High-Stakes Scenarios: When the "buy threshold" ($heta$) is high (representing expensive products or skeptical consumers), the benchmark methods often failed to find any profitable solution. The SDP model, meanwhile, consistently identified high-value clusters.
• Sparse vs. Dense Networks: The proposed method showed its greatest relative gains in sparse datasets (new or niche communities), making it ideal for startups or specialized product launches.
• Indirect Influence: Incorporating "friends-of-friends" effects significantly boosted simulated profits, sometimes by over 300% when thresholds were high.

Figure 2: Performance comparison—The SDP model (Basic Model) maintains profitability even as thresholds increase.

Critical Analysis & Conclusion

Takeaway

The shift from "influence spread" to "profit maximization" is a critical evolution for Computational Advertising. By using SDP, researchers can find more globally optimal sets of customers that greedy algorithms might skip because their individual contributions look small in isolation.

Limitations & Future Work

The primary drawback is Computational Complexity. As shown in Table 8, the SDP method is significantly slower than simple heuristics. While the authors suggest this can be handled via offline processing, scaling this to Facebook-scale networks (billions of nodes) remains a challenge. Future improvements should look into Distributed SDP solvers or Graph Neural Networks (GNNs) as a proxy for the optimization step to handle the ever-growing scale of SNS data.

Final Insight: Don't just target the most popular user; target the set of users whose collective influence satisfies the "buying threshold" of the network at the lowest possible cost.