Abstract
Traditional influence maximization models often overlook the reality that individuals have finite resources, such as time and money, which limit their ability to adopt multiple behaviors. This paper introduces a novel Multiple Behavior Diffusion Model that incorporates these constraints using a "knapsack" optimization approach. We demonstrate that finding the optimal set of early adopters to maximize network-wide engagement is NP-complete. To address this, we propose several heuristics, including Expected Immediate Adoption (EIA), which significantly outperform naive methods. Our results across synthetic and real-world networks show that these heuristics can increase resource utilization by up to 51% and effectively guide a network toward a specific target distribution of behaviors.
Introduction
Influence maximization research typically focuses on identifying key individuals to trigger a viral trend. Most existing models assume that social influence is the primary driver of adoption: if enough peers adopt a behavior, an individual is likely to follow. However, real-world adoption—whether it's joining a gym, commuting by bike, or installing solar panels—is often constrained by limited resources like time and money.
This paper addresses this gap by proposing a model where individuals must choose a subset of behaviors that maximize their personal utility without exceeding a fixed budget. The objective is to identify the optimal "seeds" (early adopters) to either maximize total network participation or steer the community toward a specific target distribution of behaviors.
The Multiple Behavior Diffusion Model
The authors propose a model based on the classic Linear Threshold (LT) model, enhanced with a resource-constraint mechanism. In this framework, each behavior has an associated cost and intrinsic utility. Each node in the network possesses a fixed resource budget. A node adopts a behavior only if the social signal from its neighbors exceeds a threshold, the behavior offers high utility, and the node has sufficient remaining resources.
Because finding the optimal seed set is NP-complete, the researchers developed several heuristics to pick seeds:
- Naive Degree: Selecting the most connected individuals.
- Degree and Resource Ranked: Selecting individuals whose neighbors have the highest total resources.
- Expected Immediate Adoption (EIA): A sophisticated approach calculating the expected number of neighbors who would adopt a behavior in the subsequent time step.
- Hill Climbing: An iterative version of EIA that accounts for the influence of previously selected seeds.
Experimental Results
The model was evaluated on synthetic networks (Preferential Attachment, Small World, and Spatially Clustered) and a real-world collaboration network (ca-GrQc).
Heuristic Performance
The Expected Immediate Adoption (H6 and H7) heuristics consistently outperformed random and degree-based selection methods. As shown in Figure 3, H6 and H7 achieved significantly higher performance metrics across all tested network topologies, representing a 15-51% increase in resource utilization over naive approaches.
Targeting and Distribution
A key finding is that the "Proportional" strategy—distributing behaviors among initial seeds in the same proportion as the final target—is highly effective. The researchers measured success using KL-divergence, where lower values indicate a closer match to the target distribution. As seen in Figure 4, the low divergence values across various target ratios demonstrate the model's ability to effectively "guide" the network.
Furthermore, the study revealed that low-cost behaviors spread more widely than high-cost ones, even when the latter offer higher utility. In this resource-constrained environment, a "hub" is only influential if its neighbors possess the resources to adopt the suggested behaviors.
Conclusion and Future Work
This research highlights the critical role of resource constraints in social diffusion. While the proposed heuristics show strong performance, several areas remain for future exploration. These include accounting for behavioral inertia, where individuals resist change despite meeting adoption criteria, and modeling "noisy" social signals. Additionally, moving from static to dynamic resource budgets and integrating epidemic models like SIR could provide deeper insights into long-term behavioral trends and decay.
Summary updated