PaperlayerView exact revision on arXiv

Source-linked AI summary

Shaping Social Activity by Incentivizing Users

Mehrdad Farajtabar, Nan Du, Manuel Gomez Rodriguez, Isabel Valera, Hongyuan Zha, Le Song

arXiv:1408.0406v2cs.SI

TL;DR

The paper asks how external incentives can steer recurrent social activity toward target levels under budget constraints. It models endogenous and exogenous events with multivariate Hawkes processes, derives a time-dependent linear activity mapping, and optimizes exogenous intensities; experiments on Twitter show more accurate shaping than alternatives.

  • Problem

    The paper asks how to steer recurrent online activity toward target levels, homogeneity, or group-specific goals by incentivizing users under budget constraints.

  • Method

    The method combines multivariate Hawkes processes, a branching-process-derived linear relation between exogenous and overall activity, and convex optimization of incentive intensities.

  • Results

    Held-out Twitter experiments show that the proposed method shapes network behavior more accurately than alternatives.

  • Takeaways & Limitations

    The framework provides fine-grained, time-sensitive control of network activity while accounting for incentive budgets.

  • Takeaways & Limitations

    The current formulation assumes exogenous events are constant over time, although the framework can be generalized to time-varying exogenous events using convolution forms.

Abstract

from arXiv · show

Events in an online social network can be categorized roughly into endogenous events, where users just respond to the actions of their neighbors within the network, or exogenous events, where users take actions due to drives external to the network. How much external drive should be provided to each user, such that the network activity can be steered towards a target state? In this paper, we model social events using multivariate Hawkes processes, which can capture both endogenous and exogenous event intensities, and derive a time dependent linear relation between the intensity of exogenous events and the overall network activity. Exploiting this connection, we develop a convex optimization framework for determining the required level of external drive in order for the network to reach a desired activity level. We experimented with event data gathered from Twitter, and show that our method can steer the activity of the network more accurately than alternatives.

1 Introduction

The paper formulates activity shaping as steering recurrent online behavior by controlling external user drives under budget constraints. It uses multivariate Hawkes processes, a predictive exogenous-to-overall activity relation, and convex optimization, then evaluates the approach on Twitter data.

  • 1 Introduction: Activity shaping targets recurrent usage levels, homogeneous activity, or group-specific usage by incentivizing users under budget constraints.This extends beyond binary adoption decisions and requires prescribing incentive amounts, not merely selecting users.
  • 1 Introduction: Multivariate Hawkes processes model endogenous and exogenous recurrent events, enabling a predictive relation between individual external drives and overall network activity.The relation is derived through a connection between Hawkes and branching processes.
  • 1 Introduction: A convex optimization framework determines incentive intensities for diverse activity-shaping objectives while respecting budget constraints and supporting time-sensitive targets.The framework can specify which users to incentivize, by how much, and when a target should be reached.
  • 1 Introduction: On 60,000 Twitter users and more than 7,500,000 URL-shortening events, held-out data show that the proposed algorithm shapes network behavior more accurately than alternatives.The experiments also use a gradient-based algorithm that scales to networks with tens of thousands of nodes.

2 Modeling Endogenous-Exogenous Recurrent Social Events

The model represents social activity as a multivariate Hawkes process whose intensity combines externally driven events with recurrent self- and peer-excitation. A probabilistic branching representation organizes event generations and supports the link from exogenous activity to total network activity.

  • 2.1 Multivariate Hawkes Process: Each user’s events are represented in a multivariate counting process with history-dependent intensity, separating external drives from within-network interactions.The platform can directly influence exogenous intensity through incentives, while endogenous events arise from user interests and peer influence.
  • 2.1 Multivariate Hawkes Process: The Hawkes influence matrix encodes sparse, nonnegative excitation between users, including diagonal self-excitation, while a decaying kernel models temporal influence.An event in a neighbor can raise a user’s event intensity, with the effect decaying over time.
  • 2.2 Connection to Branching Processes: Branching-process bookkeeping assigns exogenous events to generation zero and recursively groups the endogenous events they trigger into later generations.The genealogy is probabilistic rather than directly observed in actual event data.
  • 2.2 Connection to Branching Processes: The total network activity is decomposed across generations, allowing the expected intensity of each generation—and ultimately the network—to be linked to exogenous intensity.This decomposition forms the basis for deriving the activity-shaping relation.

3 Linking Exogenous Event Intensity to Overall Network Activity

The branching decomposition yields a time-dependent linear mapping from exogenous event intensity to expected overall network intensity. This mapping generalizes the stationary result and provides the analytical basis for choosing incentives to reach target activity patterns.

  • 3 Linking Exogenous Event Intensity to Overall Network Activity: The expected intensity at generation k is obtained from exogenous intensity through the kth auto-convolution of the influence kernel.Summing these generation-level contributions produces the network-wide expected intensity.
  • 3 Linking Exogenous Event Intensity to Overall Network Activity: At any time t, expected network activity satisfies µ(t) = Ψ(t)λ(0), where Ψ(t) summarizes propagation from exogenous intensity across users and generations.The entry Ψ_uv(t) represents expected activity at node u from unit exogenous intensity at node v.
  • 3 Linking Exogenous Event Intensity to Overall Network Activity: The linear relation enables convex programs that choose exogenous intensities to achieve diverse target activity objectives at specified times.Its time-dependent form supports more than stationary activity control.
  • 3 Linking Exogenous Event Intensity to Overall Network Activity: Under stationarity, the time-dependent relation reduces in the limit to µ = (I − Γ)^−1λ(0).Stationarity requires the spectral radius condition stated in the paper.

4 Convex Activity Shaping Framework

The activity-shaping framework optimizes exogenous intensities through a concave utility of expected activity, subject to budget and nonnegativity constraints. Its instances cover capped maximization, minimum-activity improvement, target matching, and homogenization, with scalable gradient computation.

  • 4 Convex Activity Shaping Framework: The general program maximizes a concave utility of expected activity subject to µ(t) = Ψ(t)λ(0), a total budget bound, and λ(0) ≥ 0.User-specific costs determine how exogenous intensity consumes the available budget.
  • 4 Convex Activity Shaping Framework: Additional regularization can limit the number of incentivized users, promote sparsity, or encourage smooth incentive allocations.The paper associates these goals with ℓ0, ℓ1, and ℓ2 terms, respectively.
  • 4 Convex Activity Shaping Framework: The framework instantiates capped maximization, minimax shaping, least-squares target matching, and entropy-based activity homogenization.These objectives address upper activity limits, minimum activity, prescribed profiles, and homogeneous activity distributions.
  • 4 Convex Activity Shaping Framework: The implementation uses matrix-exponential products and sparse linear systems, with a truncated Taylor approximation available for efficient gradient computation.The algorithmic procedure supports scalable optimization for the framework’s objectives.

5 Scalable Algorithm

The scalable algorithm exploits matrix-vector products to evaluate intensities and gradients efficiently, enabling convex activity-shaping optimization on large sparse networks.

  • 5 Scalable Algorithm: Sparse matrix-vector operations and iterative numerical methods make the activity-shaping framework tractable for large networks.The approach computes matrix-exponential products efficiently and solves sparse linear systems with GMRES.
  • 5 Scalable Algorithm: The framework computes gradients for multiple shaping objectives by selecting an appropriate vector and reusing the efficient matrix-exponential procedure.This covers activity maximization, minimax shaping, least-squares shaping, and activity homogenization.
  • 5 Scalable Algorithm: Least-squares and homogenization gradients require two matrix-exponential products and two sparse linear-system solves when the interaction matrix is sparse.Least-squares gradients also use two sparse matrix-vector multiplications.
  • 5 Scalable Algorithm: Projected gradient descent solves the resulting convex optimization problem for each activity-shaping task.
  • 5 Scalable Algorithm: Algorithms 2 and 3 implement gradient computation for least-squares activity shaping and activity homogenization using these reusable operations.

6 Experimental Evaluation

The framework is evaluated on Twitter data using theoretical, simulated, and held-out objectives across three activity-shaping tasks. It consistently outperforms heuristic alternatives, supports sparse incentives, and scales to large networks.

  • Activity Shaping Results: Across capped maximization, minimax shaping, and least-squares shaping, the proposed methods consistently outperform their heuristic alternatives on the reported objectives.The evaluations use theoretical, simulated, and held-out schemes, with Figure 2 summarizing the three task rows.
  • Activity Shaping Results: 11% better than DEG on the theoretical capped-maximization objective, with an estimated monthly increase of about 34,560 events.The held-out comparison also reports an almost 0.1 rank-correlation difference between CAM and DEG.
  • Activity Shaping Results: 2× better than LP on the theoretical minimax objective, increasing the least-active user’s average monthly activity by 4.3 actions.On simulated and held-out objectives, the algorithms’ performance becomes more similar.
  • Activity Shaping Results: Longer horizons produce larger differences from alternatives because endogenous activity accumulates and the framework models both endogenous and exogenous events.This pattern is reported across all three activity-shaping tasks.
  • Sparsity and Activity Shaping: An l1 regularization term trades off incentive sparsity against shaping performance, with larger γ producing fewer nonzero intensities and potentially unused budget.Cross-validation is suggested for selecting the trade-off in unfamiliar application domains.
  • Scalability: On the 60K dataset, the large-scale algorithm again outperforms heuristic baselines; MMASH improves minimum activity by 0.864 monthly actions, equivalent to about 51,840 monthly adoptions.The dataset contains 60,000 Twitter users and more than 7,500,000 URL-shortening-service uses; held-out experiments also favor the approach.

7 Summary and Discussion

The paper frames activity shaping as a generalization of influence maximization and connects exogenous incentives to overall network activity through a convex optimization framework.

  • 7 Summary and Discussion: The framework uses a linear connection between exogenous activity and overall network activity to derive incentives for reaching global activity patterns.The connection comes from modeling social activity with multivariate Hawkes processes and branching processes.
  • 7 Summary and Discussion: The method is evaluated on synthetic and real-world held-out data and outperforms several heuristics.
  • 7 Summary and Discussion: Time-varying exogenous events require convolution-form theoretical results, although the framework can be generalized to them.The current formulation assumes exogenous events are constant over time.
  • 7 Summary and Discussion: Simple parametrized incentive functions preserve linear closed-form mappings, while nonparametric functions retain linearity but require functional gradient methods.
  • 7 Summary and Discussion: Future work includes competing incentives, explicit branching-structure discovery, and alternative or learned kernel functions.

A Proofs

The proofs establish generation-wise and time-dependent relations for Hawkes-process activity, then derive the stationary network intensity under a stability condition.

  • A Proofs: The generation-k expected activity equals the k-fold kernel convolution applied to the exogenous intensity.
  • A Proofs: The time-dependent mapping uses matrix exponentials and inverse Laplace transforms to obtain a closed form for the activity response.
  • A Proofs: The stationary intensity is μ = (I − Γ)^−1 λ^(0), obtained as the long-time limit of the time-dependent mapping.

B More on Experimental Setup

The experiments compare activity-shaping methods with heuristic baselines across multiple objectives and use Twitter data at both moderate and large scale.

  • B More on Experimental Setup: The evaluation uses six URL-shortening services and reports 7,566,098 events collected over an eight-month period.
  • B More on Experimental Setup: The study compares capped maximization, minimax shaping, and least-squares shaping against heuristics based on activity, influence, degree, PageRank, proportional allocation, and greedy allocation.
  • B More on Experimental Setup: For minimax shaping, baselines include uniform allocation, allocation to low-activity users, linear programming, and greedy allocation.
  • B More on Experimental Setup: For least-squares shaping, PROP allocates budget proportionally to the target shape, whereas LSGRD greedily funds users with the largest current-target gaps.
  • B More on Experimental Setup: The proposed framework is presented as addressing both how many users to incentivize and how much to allocate, whereas baselines rely on heuristics.

C Temporal Properties

Temporal experiments compare empirical and theoretical intensity over time, showing that empirical activity follows the theoretical trajectory and approaches stationarity.

  • C Temporal Properties: The average empirical intensity follows the theoretical instantaneous intensity, while estimate variability increases with time from the starting point.The experiment averages empirical activity over 100 independent runs.
  • C Temporal Properties: The instantaneous intensity tends toward the stationary intensity after the network runs sufficiently long.

D Visualization of Least-squares Activity Shaping

Figure 6 visualizes least-squares activity shaping on the 2K and 60K datasets at t = 1, comparing a target activity shape with profiles after theoretical-objective incentivization.

  • D Visualization of Least-squares Activity Shaping: Figure 6 compares target activity shapes with post-incentivization user activity profiles for the 2K and 60K datasets at t = 1.The red line denotes the target, while the blue curves show activity profiles computed using the theoretical objective.
  • D Visualization of Least-squares Activity Shaping: The resulting activity behavior resembles the targeted shape after users are incentivized.
  • D Visualization of Least-squares Activity Shaping: The visualization evaluates least-squares activity shaping using the same target shape as the experiments section.
Loading 1408.0406v2…