Abstract
We study the problem of online influence maximization in social networks. In this problem, a learner aims to identify the set of "best influencers" in a network by interacting with it, i.e., repeatedly selecting seed nodes and observing activation feedback in the network. We capitalize on an important property of the influence maximization problem named network assortativity, which is ignored by most existing works in online influence maximization. To realize network assortativity, we factorize the activation probability on the edges into latent factors on the corresponding nodes, including influence factor on the giving nodes and susceptibility factor on the receiving nodes. We propose an upper confidence bound based online learning solution to estimate the latent factors, and therefore the activation probabilities. Considerable regret reduction is achieved by our factorization based online influence maximization algorithm. And extensive empirical evaluations on two real-world networks showed the effectiveness of our proposed solution.
Introduction
Influence Maximization (IM) is a critical task in social network analysis, aimed at identifying a small set of "seed" users who can trigger the largest possible cascade of information or influence. While traditional IM assumes known activation probabilities between users, the "Online" Influence Maximization (OIM) setting is more realistic: these probabilities are unknown and must be learned through iterative interactions.
Existing OIM solutions often treat every edge (connection) in a network independently. In large-scale social networks with millions of edges, this approach leads to extremely slow learning rates. Furthermore, it ignores a fundamental biological and social property: network assortativity. Influential individuals and susceptible individuals tend to exhibit consistent traits across their various interactions. This paper introduces IMFB (Influence Maximization with Factorization-Bandits), which leverages these latent node-level traits to accelerate learning and improve influence outcomes.
Methodology: Factorization-Bandits
The core innovation of IMFB is the low-rank factorization of edge activation probabilities. Instead of learning a unique probability $p_{u,v}$ for every edge $(u, v)$, the model decomposes this probability into the inner product of two $d$-dimensional latent vectors: $$p_{u,v} = \theta_u^T \beta_v$$ Here, $ heta_u$ represents the influence factor of the sender (node $u$), and $eta_v$ represents the susceptibility factor of the receiver (node $v$).
Online Learning and Observation Propagation
IMFB employs an Upper Confidence Bound (UCB) framework to balance exploration and exploitation. By maintaining optimistic estimates of $\theta$ and $\beta$, the algorithm can select seeds that are either known to be effective or have high potential for providing new information.
A key advantage of this node-centric approach is observation propagation. When an interaction is observed on a single edge, the algorithm updates the latent factors of the involved nodes. Because these factors are shared across all edges connected to those nodes, a single observation provides information about many unobserved connections.
As shown in Figure 1, traditional algorithms like CUCB only update the specific edge $(v_0, v_1)$ that was triggered. In contrast, IMFB updates the influence factor $\hat{\theta}_{v_0}$ and susceptibility factor $\hat{\beta}_{v_1}$. This update implicitly refines the estimates for all other edges connected to $v_0$ (like $(v_0, v_2)$) and all edges pointing to $v_1$ (like $(v_3, v_1), (v_4, v_1), (v_5, v_1)$), even if those edges were not part of the current cascade.
Experimental Evaluation
The researchers evaluated IMFB against several state-of-the-art baselines, including CUCB, IMLinUCB, and $\epsilon$-greedy strategies, using two real-world datasets:
- NetHEPT: A citation network (27k nodes, 352k edges).
- Flickr: A social network for image sharing (12k nodes, 138k edges).
- Controlled Flickr: A modified version of the Flickr dataset where high-degree nodes (those with many connections) were assigned low actual influence. This "tricky" dataset tests whether an algorithm can distinguish between surface-level popularity and true influence.
Results and Discussion
IMFB consistently outperformed all baselines across all datasets in terms of cumulative reward (total nodes activated).
As illustrated in Figure 3, IMFB demonstrates rapid convergence. In the "Controlled Flickr" scenario (Figure 3c), the performance gap is particularly striking. While standard bandit algorithms were misled by high-degree "dud" nodes, IMFB quickly identified the underlying latent factors and pivoted to the true influencers, achieving a 230% improvement over the next best baseline.
Furthermore, the complexity of IMFB scales with the number of nodes and the latent dimension $O(d|V|)$, rather than the number of edges $O(|E|)$. In dense networks, this represents a significant computational efficiency gain.
Conclusion
By incorporating network assortativity through latent factor models, IMFB transforms the online influence maximization problem from an edge-learning task into a node-learning task. This shift allows for powerful observation propagation, enabling the algorithm to "learn from the unseen" and identify top influencers with far fewer interactions than traditional methods. Future work will explore adapting this factorization approach to different diffusion models and scenarios with more limited, node-level feedback.
Summary updated