Labeled Influence Maximization: Precision Targeting in Social Networks

TL;DR

While classic influence maximization focuses on the quantity of people reached, real-world marketing cares about the quality and relevance of the audience. This paper proposes Labeled Influence Maximization (LIM), a framework to find seed nodes that maximize "profit" from specific target segments. By introducing a proximity-based Maximum Coverage algorithm, the authors enable marketers to run complex, target-specific queries in seconds rather than hours.

Problem & Motivation: The "Blind" Viral Marketing Trap

In standard viral marketing models, every node in a social graph is treated as an identical target. However, a luxury watch brand and a fast-food chain target vastly different demographics.

The authors identify a critical flaw in traditional approaches: if you simply ignore nodes that don't match your target criteria, you break the connectivity of the social network. A "cool-hunter" or a popular blogger might not be in your target demographic (e.g., they aren't students), but they are the essential bridges required to reach that demographic. This paper explores how to select seeds that are influential specifically towards nodes with relevant "labels" (interests, demographics, or skills).

Methodology: From Greedy Sims to Proximity Coverage

The authors propose three distinct paths to solve the LIM problem under the Independent Cascade (IC) model:

1. Adaptation of Existing Heuristics

• Labeled New Greedy: Adapts the "New Greedy" approach by sampling the graph and calculating the expected profit from nodes reachable by a seed. While accurate, its computational cost is staggering.
• Labeled Degree Discount: A fast heuristic that discounts a node's influence potential if its neighbors have already been selected as seeds, specifically focusing on neighbors with target labels.

2. The Maximum Coverage Approach (The Innovation)

To solve the efficiency problem, the authors propose a Maximum Coverage strategy. This involves a two-stage process:

• Offline (Precomputation): Use Cycle Free Effective Conductance (CFEC) to calculate the proximity scores between all pairs of nodes. This represents the "influence potential."
• Online (Query): When a marketer specifies a target label (e.g., "Drama fans") and a profit weight, the system uses a Bit-array-based greedy algorithm to find seeds that "cover" the maximum weighted proximity of target nodes.

Figure 1: In this toy network, while v1 is the global influencer, v7 is the optimal seed for target label B.

Experiments & Results: Performance vs. Speed

The authors tested their methods on an IMDb dataset (6,079 nodes, 120,610 edges), where nodes are actors and labels are movie genres.

• Effectiveness: The Labeled New Greedy and Maximum Coverage methods consistently outperformed basic degree-based heuristics, particularly as the number of seeds increased.
• Efficiency: The performance gap in execution time was massive. As shown in the table below, the Labeled New Greedy took 8 hours, making it useless for interactive marketing strategy tools. The Maximum Coverage algorithm achieved similar effectiveness in just 20.3 seconds.

Table 1: The trade-off between speed and accuracy becomes clear—Maximum Coverage is the only viable candidate for online analysis.

Figure 3: Profit achieved when targeting multiple labels (Drama and Comedy) with different weights.

Critical Insight & Conclusion

The significance of this work lies in its Proximity-Profit formulation. By treating influence as a "coverage" problem over precomputed proximities, the authors decouple the expensive graph traversal from the target-specific query.

Limitations: The current model assumes labels are static and edge weights are uniform (0.05). In real-world scenarios, influence probabilities are often edge-dependent and labels may evolve. However, this paper provides a robust foundation for moving Influence Maximization from theoretical graph theory into a practical tool for data-driven marketers.