BOPIM: Bayesian Optimization for influence maximization on temporal networks

The goal of influence maximization (IM) is to select a small set of seed nodes which maximizes the spread of influence on a network. In this work, we propose $\mathsf{BOPIM}$, a Bayesian Optimization (BO) algorithm for IM on temporal networks. The IM task is well-suited for a BO solution due to its expensive and complicated objective function. We propose a simple surrogate function to model the objective function and leverage Gaussian Process regression with shrinkage priors to fit the model. A major difficulty in combinatorial BO is constructing an appropriate covariance matrix. We overcome this challenge with a kernel function based on the amount of overlap in seed set neighbors, thus tailoring the solution to our IM application. This also allows us to use the Expected Improvement acquisition function to choose the next point to evaluate. In numerical experiments on real-world networks, we prove that $\mathsf{BOPIM}$ outperforms competing methods and yields comparable influence spreads to a gold-standard greedy algorithm while being as much as five times faster. We also demonstrate the proposed method’s ability to quantify uncertainty in optimal seed sets. To our knowledge, this is the first attempt to look at uncertainty in the seed sets for IM.

Keywords: Diffusion, Dynamic networks, Shrinkage priors, Uncertainty quantification

1 Introduction

Influence maximization (IM) is a canonical network science problem where the goal is to select a small set of seed nodes in order to maximize the influence spread on a graph (Kempe et al.,, 2003; Chen et al.,, 2009). Over the past two decades, IM has garnered significant research interest due to its relevance in online marketing campaigns (Domingos and Richardson,, 2001; Bharathi et al.,, 2007; Chen et al., 2010b, ), rumor spreading (Kempe et al.,, 2003; Murata and Koga,, 2018), public health campaigns (Wilder et al.,, 2017; Yadav et al.,, 2017; Wilder et al.,, 2018; Yadav et al.,, 2018), vaccine strategies (Holme,, 2004; Lee et al.,, 2012), and more. Traditionally, the problem assumes the graph to be static, i.e., nodes and edges are fixed. In many situations, however, this may be unrealistic. For example, consider a marketing campaign on X where a company promotes a new product. As users and followers change daily, an effective IM algorithm must account for this dynamism. Therefore, recent work has looked at the IM problem on temporal networks (Holme and Saramäki,, 2012) where edges change with time. Since this combinatorial optimization problem is NP-hard, heuristics must be employed. Some methods use a greedy algorithm and probabilistic approximation of the expected influence spread (Aggarwal et al.,, 2012; Osawa and Murata,, 2015; Erkol et al.,, 2020), while others eschew costly influence spread calculations by simply ranking nodes in order of importance (Michalski et al.,, 2014; Murata and Koga,, 2018; Michalski et al.,, 2020). We refer the interested reader to Yanchenko et al., 2024b for a review of temporal IM.

While IM is a well-known problem in the network, information and computer sciences, it has received relatively little attention from statisticians. This has led to several consequences on IM methodology development, not least of which being a lack of uncertainty quantification. Additionally, as the IM task is an optimization problem, statistics has a whole suit of techniques to offer that hitherto have been unexplored. One such approach is Bayesian Optimization (BO) which has emerged as a popular paradigm for optimizing complicated objective functions (Snoek et al.,, 2012; Shahriari et al.,, 2015; Frazier,, 2018). Machine learning hyper-parameter tuning (Snoek et al.,, 2012; Wu et al.,, 2019; Turner et al.,, 2021), experimental design (Frazier and Wang,, 2015; Shahriari et al.,, 2015; Greenhill et al.,, 2020) and computer experiments (Sürer et al.,, 2023; Sauer et al.,, 2023) are just a few of the many applications where BO has been successfully implemented. BO approximates a complicated objective function with a simple surrogate function and fits this model via Bayesian regression. The statistical model is maximized with an acquisition function before evaluating this new point on the original objective function. Finally, this point is added to the data set and the process repeats.

In this work, we propose $\mathsf{BOPIM}$, Bayesian OPtimization for Influence Maximization, a novel BO algorithm for IM on temporal networks, which is one of the first solutions to the IM problem from a statistical angle. We construct an intuitive surrogate model for the influence spread function as well as a novel kernel function based on the similarity in neighbors of the seed set. We then leverage a popular global-local shrinkage prior and Expected Improvement acquisition function to select the next candidate point. In numerical experiments on real-world networks, $\mathsf{BOPIM}$ yields seed sets with influence spreads comparable to those of a greedy algorithm but at a fraction of the computational time. Additionally, our approach yields measures of uncertainty on the seed sets.

There have been many contributions to the combinatorial BO literature, including Baptista and Poloczek, (2018); Oh et al., (2019); Daulton et al., (2022); Papenmeier et al., (2023). These methods cannot be applied directly to our problem, however, due to the cardinality constraint on the number of node in the seed set. Our work primarily builds on Baptista and Poloczek, (2018); Garnett et al., (2010); Buathong et al., (2020). We leverage the ideas from Baptista and Poloczek, (2018) to construct the mean function for our Gaussian process, but this requires some modifications thanks to the cardinality constraint and input space size. Garnett et al., (2010); Buathong et al., (2020), on the other hand, address the challenges of constructing a covariance function for combinatorial optimization problems. Their approaches cannot be used directly either, however, because our input space is nodes in a graph, i.e., non-Euclidean. Though recently, there has been some work on BO for functions defined on graphs (Wan et al.,, 2024).

The layout of the paper is as follows. For the remainder of Section 1, we introduce notation and give a formal problem statement. Section 2 presents the main algorithm while Section 3 is devoted to numerical experiments. We share concluding thoughts and future directions in Section 4.

1.1 Notation and problem statement

Let $\mathcal{G}=(G_{1},\dots,G_{T})$ be a temporal graph with $T$ snapshots or “slices,” where a graph snapshot $G_{t}=(V,E_{t})$ is defined by node set $V$ and edge set $E_{t}$. We let $|V|=n$ be the number of nodes and define $m=|\cup_{t=1}^{T}E_{t}|$ as the number of unique edges. Given an influence diffusion process and integer $k<n$, the goal of IM is to find a set of nodes $S$ with $|S|=k$ such that if the nodes in $S$ are “influenced” at time $t=1$, then the spread of influence at time $T+1$ is maximized.

Central to this problem is the influence diffusion mechanism. Some of the most popular choices are the Independent Cascade (IC) (Wang et al.,, 2012; Wen et al.,, 2017) and Linear Threshold (Chen et al., 2010a, ; Goyal et al.,, 2011) models. We adopt the Susceptible-Infected (SI) model from epidemiological studies (Osawa and Murata,, 2015; Murata and Koga,, 2018). In the SI model, a node is either in a susceptible (S) or infected (I) state. A node is infected if it was influenced at some point during the process, and susceptible otherwise. At time $t=1$, nodes in the seed set are set to state I, and all other nodes initialize to state S. At time $t$, a node in state I attempts to influence all of its neighbors. Specifically, if node $i$ is in state I, node $j$ is in state S, and there exists an edge between node $i$ and $j$ at time $t$, then node $j$ will be in state I at time $t+1$ with probability $\lambda$. The process concludes at time $T+1$ and the number of nodes in state I corresponds to the total influence spread. If we let $\sigma(S)$ be the expected number of influenced nodes at time $T+1$ for seed set $S$, the IM problem seeks the set of nodes of size $k$ that maximizes $\sigma(S)$ on $\mathcal{G}$, i.e.,

$$S^{*}=\arg\max_{S\subseteq V,|S|=k}\sigma(S).$$ (1)

Finding $S^{*}$ is a combinatorial optimization problem with a cardinality constraint and has been shown to be NP-hard under many popular diffusion mechanisms (Li et al.,, 2018) so finding the global optimum by brute-force calculation is infeasible even for moderate $n$. Indeed, as the influence spread function is typically computed using Monte Carlo (MC) simulations, even evaluating $\sigma(S)$ is costly. Many IM algorithms efficiently compute the influence spread function and apply a greedy algorithm to choose the seed nodes, while others skip evaluation of the objective function and instead use a heuristic to rank nodes by influence. In the remainder of this work, we describe a BO algorithm to approximate the solution in (1).

2 Bayesian Optimization

We now present the main contribution of this paper, the $\mathsf{BOPIM}$ algorithm, by addressing the three main steps of the BO schema: the objective function, statistical model and acquisition function.

2.1 Objective function

The first step in a BO algorithm is the initial evaluation of the objective function. Let $f:\mathcal{X}\to\mathbb{R}$ be some real-valued function defined on domain $\mathcal{X}$ that we wish to maximize. BO is particularly useful when $f(\cdot)$ is computationally expensive to evaluate, lacks special structure, e.g., concavity, and/or has unavailable first and second order derivatives. Then we evaluate $f(\bm{x}_{i})$ for $\bm{x}_{i}\in\mathcal{X}$ and $i=1,\dots,N_{0}$ for a user-defined $N_{0}$.

For the temporal IM problem, let $\bm{x}\in\mathcal{X}=\{0,1\}^{n}$ be such that $x_{j}=1$ if node $j$ is in the seed set, and 0 otherwise, for $j=1,\dots,n$. Since the seed set is limited to $k$ nodes, we impose the cardinality constraint that $\sum_{j=1}^{n}x_{j}=k$. Then we define $f(\bm{x})$ as the expected influence spread for seed set $\bm{x}$. We stress that $f(\cdot)$ is highly dependent on $\mathcal{G}$ as well as the diffusion process, but suppress this dependence in the notation for convenience. $f(\cdot)$ is an ideal candidate for BO because its evaluation does not yield derivatives and it is expensive to compute via MC simulations. For the initial $N_{0}$ evaluations of $f(\cdot)$, we remark that nodes with high degrees on the temporally aggregated network, $\tilde{G}=\cup_{t}G_{t}$, are good candidates for the optimal seed set. Therefore, instead of randomly sampling $\bm{x}_{i}$ from $\mathcal{X}$, we sample nodes proportionally to their degree. Mathematically, this means sampling $k$ times without replacement from a distribution with probability mass function $\mathsf{P}(Z=j)=d_{j}/\sum_{k}d_{k}$ where $d_{j}$ is the degree of node $j$ on $\tilde{G}$ for $Z\in\{1,\dots,n\}$. This sampling scheme ensures that the model better fits the objective function near the expected optimal seed set (see Section 3.2 for empirical evidence). With $\bm{x}_{1},\dots,\bm{x}_{N_{0}}$ sampled, we define ${\bf X}=(\bm{x}_{1}^{T},\dots,\bm{x}_{N_{0}}^{T})^{T}\in\{0,1\}^{N_{0}\times n}$ and evaluate $f(\bm{x}_{i})$ using MC simulations.

2.2 Statistical model

Next we need an adequate surrogate model for the objective function. The most popular approach uses Gaussian Process (GP) regression. First, let

$$y_{i}=f(\bm{x}_{i})+\epsilon_{i},$$

where $y_{i}$ is the observed influence spread, $f(\bm{x}_{i})$ is the objective function from Section 2.1 and $\epsilon_{i}\sim\mathsf{Normal}(0,\sigma^{2})$ is the noise term. Then our GP regression model is

$$\bm{y}\sim\mathsf{Normal}(\mu({\bf X}),\sigma^{2}\gamma{\bf K}+\sigma^{2}{\bf I}_{N_{0}})$$ (2)

where $\mu(\cdot)$ is the mean function and ${\bf K}$ is the covariance defined by a kernel function $\kappa(\cdot,\cdot)$ such that ${\bf K}_{ij}=\kappa(\bm{x}_{i},\bm{x}_{j})$. Additionally, $\bm{y}=(y_{1},\dots,y_{N_{0}})^{T}$, ${\bf X}$ is defined in the previous sub-section, and $\gamma>0$ is a kernel hyper-parameter. The two key components of the GP regression model are the mean function $\mu(\cdot)$ and kernel function $\kappa(\cdot,\cdot)$, so we consider each of these in turn.

2.2.1 Mean function

First, we construct a mean function, $\mu(\cdot)$ parameterized by $\bm{\beta}$, to serve as a surrogate for $f(\cdot)$. Motivated by Baptista and Poloczek, (2018), we assume that the surrogate model is linear in its parameters, i.e.,

$$\mu(\bm{x}_{i})=\sum_{j=1}^{n}x_{ij}\beta_{j}=\bm{x}_{i}\bm{\beta}$$ (3)

for $\bm{\beta}=(\beta_{1},\dots,\beta_{n})^{T}$. GP regression places a multivariate normal prior $\bm{\beta}\sim\mathsf{Normal}({\bf 0}_{n},\Sigma_{\beta})$ where ${\bf 0}_{n}$ is the vector of zeros of length $n$ and $\Sigma_{\beta}$ is some covariance matrix. We also empirically standardize $\bm{y}$ to have mean zero to remove the need for an intercept.

Since $n$ is large for most real-world networks, the dimension of $\bm{\beta}$ will also be large. Additionally, it is unlikely that each component of $\bm{\beta}$ is significant, i.e., many nodes inclusion in the seed set does not lead to significant influence spread. Thus, we endow $\bm{\beta}$ with a sparsity-inducing shrinkage prior. As in Baptista and Poloczek, (2018), we use the Horseshoe (HS) prior (Carvalho et al.,, 2009, 2010) which is designed to shrink insignificant coefficient estimates towards zero while still allowing for accurate estimation of the important coefficients. Specifically, the HS prior handles sparsity via a half-Cauchy prior distribution on the variance of the coefficients, i.e.,

$$\beta_{j}|\lambda_{j}^{2},\tau^{2},\sigma^{2} \sim\mathsf{Normal}(0,\lambda_{j}^{2}\tau^{2}\sigma^{2})$$

$$\lambda_{j}^{2},\tau^{2} \sim\mathsf{C}^{+}(0,1)\$$ (4)

where $j=1,\dots,n$ and $\mathsf{C}^{+}(0,1)$ is the standard half-Cauchy distribution. Thus, $\tau^{2}$ represents the global shrinkage and $\lambda_{j}^{2}$ controls the local shrinkage of each coefficient. For the Gibbs sampler, we leverage an auxiliary variable formulation (Makalic and Schmidt,, 2015). Please see the Supplemental Materials for complete MCMC details. We also considered the R2D2 prior (Zhang et al.,, 2022; Yanchenko et al., 2024a, ) and Dirichlet-Laplace (Bhattacharya et al.,, 2015), but the results were similar, so we focus on the HS prior.

2.2.2 Coefficient interpretation

The coefficient $\beta_{j}$ represents the marginal importance of each node to the overall influence spread. This means that if the estimate of $\beta_{j}$ is positive and large, then including node $j$ in the seed set leads to a larger total influence spread. Conversely, small and negative coefficient estimates correspond to nodes whose inclusion in the seed set does not yield large influence spreads. We stress, however, that the coefficient estimates are not interpretable in the traditional sense. Typically, the coefficient $\beta_{j}$ for a binary explanatory variable $x_{j}\in\{0,1\}$ corresponds to the increase in the response when $x_{j}=1$ and all other variables are fixed. This interpretation is invalid in our context, however, due to the constraint $\sum_{j=1}^{n}x_{j}=k$. In other words, $\beta_{j}$ does not correspond to the increase in the influence spread if node $j$ is added to the seed set and all other nodes are held fixed, because then the number of nodes in the seed set would be greater than $k$. Instead, we interpret $\beta_{j}-\beta_{i}$ as the expected increase in the influence spread function if node $j$ replaced node $i$ in the seed set. Thus, the estimates yield a relative sense of the increase/decrease of the objective function if a node is seeded, and in this sense, are analogous to a node-ranking heuristic.

2.2.3 Kernel function

To complete our GP regression model, we must also specify the covariance, ${\bf K}$, defined by the kernel function, $\kappa(\cdot,\cdot)$. If $\bm{x}_{i},\bm{x}_{j}\in\mathbb{R}^{p}$, then it is straightforward to compute their variance using, e.g., a Gaussian or Matern kernel. In our setting, however, $\bm{x}_{i},\bm{x}_{j}\in\{0,1\}^{n}$ and correspond to nodes in a graph, so it is not immediately obvious how to choose a kernel.

Recall that for the IM task, we initially influence a small set of nodes which then propagate information to the rest of the network. Clearly, these initially selected nodes (as well as their neighboring nodes) are very important for the final influence spread (Erkol et al.,, 2020). Indeed, if the nodes corresponding to seed sets $\bm{x}_{i}$ and $\bm{x}_{j}$ have many neighbors in common, then we would expect their influence spreads also to be similar.

Inspired by this observation, as well as Garnett et al., (2010), who studies the BO task on combinatorial search-spaces, we propose the following kernel function. Let $\{v_{i_{1}},\dots,v_{i_{k}}\}$ correspond to seed set $\bm{x}_{i}$. First, we find all neighbors of $\{v_{i_{1}},\dots,v_{i_{k}}\}$ at time $t=1$, and call this neighboring set $\mathcal{S}_{i}$. In other words, if node $v_{\ell}$ has an incoming edge from some node in $\{v_{i_{1}},\dots,v_{i_{k}}\}$ at time $t=1$, then $v_{\ell}\in\mathcal{S}_{i}$. Of course, $\{v_{i_{1}},\dots,v_{i_{k}}\}\in\mathcal{S}_{i}$ as well. We also compute the set of neighboring nodes set, $\mathcal{S}_{j}$, for $\bm{x}_{j}$. Again, if $\mathcal{S}_{i}$ and $\mathcal{S}_{j}$ have many common elements, then we want $\kappa(\bm{x}_{i},\bm{x}_{j})$ to be large. Therefore, we can compute the Jaccard coefficient between $\mathcal{S}_{i}$ and $\mathcal{S}_{j}$ and use this as our kernel function. The Jaccard coefficient (JC) (Jaccard,, 1901, 1912) is a simple metric to quantify the similarity between two finite sets. If $A$ and $B$ are two such sets, then the JC is the number of common elements between the two sets divided by the total number of elements in each set, i.e.,

$$JC(A,B)=\frac{|A\cap B|}{|A\cup B|}.$$

If $A$ and $B$ are the same set, then $JC(A,B)=1$ and if $A$ and $B$ have no common elements, then $JC(A,B)=0$ such that $0\leq JC(A,B)\leq 1$. Additionally, it is clear that $JC(A,B)=JC(B,A)$.

With kernel function in hand, we can easily construct our covariance matrix. Indeed,

$${\bf K}_{ij}=\kappa(\bm{x}_{i},\bm{x}_{j})=\begin{cases}JC(\mathcal{S}_{i},\mathcal{S}_{j})&i\neq j\\ 1+\delta&i=j\end{cases}$$ (5)

where $\delta>0$ is some small constant to ensure positive-definiteness of our covariance matrix. This definition satisfies the desideratum that points close in the input space are more strongly correlated where we have defined two seed sets to be “close” if they have many neighbors in common at time $t=1$.

2.3 Acquisition function

With our GP model fully defined, we can move on to the final step in the BO algorithm: the acquisition function. This function determines which seed set to evaluate our objective function at next. We want to probe areas of the search space with a high likelihood of being near the global maximum (exploitation), while also considering seed sets which have not been explored yet to prevent getting stuck in a local optimum (exploration).

For the acquisition function, we use the Expected Improvement function (Frazier,, 2018)as it is one of the most popular acquisition functions and does not require any hyper-parameter tuning. The idea is to evaluate the objective function at the value which leads to the largest expected increase compared to the current maximum. Specifically, assume that we are in $b$th iteration of the BO loop. Let $\bm{x}\in\{0,1\}^{n}$ and $\mu(\bm{x})$ and $\sigma^{2}(\bm{x})$ be the conditional mean and variance, respectively, of our GP model given the current data. By properties of the multivariate normal distribution, we have

$$\mu(\bm{x})=\bm{x}^{T}\bm{\beta}+\kappa^{*}(\bm{x},{\bf X})^{T}(\gamma{\bf K}+{\bf I}_{N_{0}+b})^{-1}(\bm{y}-{\bf X}\bm{\beta})$$

and

$$\sigma^{2}(\bm{x})=\sigma^{2}\{(\gamma+1)-\kappa^{*}(\bm{x},{\bf X})^{T}(\gamma{\bf K}+{\bf I}_{N_{0}+b})^{-1}\kappa^{*}(\bm{x},{\bf X})\}$$

where

$$\kappa^{*}(\bm{x},{\bf X})=(\kappa(\bm{x},\bm{x}_{1}),\dots,\kappa(\bm{x},\bm{x}_{N_{0}+b}))^{T}.$$

In practice, we replace $\bm{\beta}$ and $\sigma^{2}$ with their corresponding posterior medians. Now, let $\Delta(\bm{x})=\mu(\bm{x})-f^{*}$ where $f^{*}=\max_{i\in\{1,\dots,N_{0}+b}\{f(\bm{x}_{i})\}$, i.e., the maximum influence spread of the seed sets we have already evaluated. Then

$$EI(\bm{x})=\max\{\Delta(\bm{x}),0\}+\sigma(\bm{x})\phi\left(\frac{\Delta(\bm{x})}{\sigma(\bm{x})}\right)-|\Delta(\bm{x})|\Phi\left(\frac{\Delta(\bm{x})}{\sigma(\bm{x})}\right)$$ (6)

where $\phi(\cdot)$ and $\Phi(\cdot)$ are the probability density function and distribution function, respectively, of the standard normal (Frazier,, 2018). We choose the next seed set to evaluate, $\tilde{\bm{x}}$ as the seed set with largest expected improvement, i.e.,

$$\tilde{\bm{x}}={\arg\max}_{\bm{x}\in\{0,1\}^{n}}EI(\bm{x}).$$

The astute reader will notice that we have simply traded one combinatorial optimization problem (maximizing $f(\cdot)$) for another (maximizing $EI(\cdot)$). $EI(\cdot)$, however, is much cheaper to evaluate than $f(\cdot)$ so finding its optimum will be significantly faster. Indeed, we propose a simple greedy algorithm to find the maximum of $EI(\cdot)$ with details in the Supplemental Materials. The main idea is that nodes in the current seed set are swapped with other nodes. If the switch improves the solution (larger $EI(\cdot)$), then its kept, otherwise the previous seed set is used. In this way, the algorithm makes the locally optimal decision. The algorithm continues until all nodes have been looped through and no changes are made.

After solving for $\tilde{\bm{x}}=\arg\max EI(\bm{x})$, we append it and $f(\tilde{\bm{x}})$ to ${\bf X}$ and $\bm{y}$, respectively, update the covariance matrix ${\bf K}$, and re-fit the GP regression model to update the posterior distribution of $\bm{\beta}$ and $\sigma^{2}$. This step is repeated $B$ times where $B$ is the number of iterations in the BO loop. Then the optimal seed set is $\bm{x}^{*}=\arg\max_{\bm{x}\in\{\bm{x}_{1},\dots,\bm{x}_{N_{0}+B}\}}f(\bm{x})$ where this maximum is taken over the $N_{0}+B$ sampled points.

The steps for the entire algorithm are outlined in Algorithm 1. For a given network $\mathcal{G}$, diffusion mechanism, seed size $k$, and budget $N_{0},B$, the algorithm outputs the optimal seed set to maximize the influence spread on $\mathcal{G}$. We call the method $\mathsf{BOPIM}$ for Bayesian OPtimization for Influence Maximization on temporal networks.

Result: Optimal seed set $S$

Input: Objective function $f(\bm{x})$; temporal network $\mathcal{G}$; seed set size $k$; budget $B$; number of initial samples $N_{0}$;

for $N_{0}$ times do

       Sample $\bm{x}_{i}$ proportional to node’s aggregate degree  Evaluate $y_{i}=f(\bm{x}_{i})$ 

end for

Construct ${\bf K}$ using (5)  Compute posterior of $\bm{\beta}$ and $\sigma^{2}$  for  $B$ times do

       Find $\tilde{\bm{x}}=\arg\max_{\bm{x},\sum_{j}x_{j}=k}EI(\bm{x})$   Compute $y=f(\tilde{\bm{x}})$  Append observation and re-compute posterior of $\bm{\beta}$ and $\sigma^{2}$  Update ${\bf K}$  

end for

return $\bm{x}^{*}=\arg\max_{\bm{x}\in\{\bm{x}_{1},\dots,\bm{x}_{N_{0}+B}\}}f(\bm{x})$

Algorithm 1 Bayesian optimization for influence maximization: $\mathsf{BOPIM}$

2.4 Discussion

Finding the seed set for IM on temporal networks is a cardinality-constrained, combinatorial optimization problem with non-Euclidean inputs. The challenges associated with the constraint are mitigated with our simple surrogate function (3) that is linear in the marginal contribution of each node to the influence spread. This mean function, however, implicitly assumes that there is no interaction between nodes in the seed set. From previous studies on IM, we know that this is not the case as there can be large overlap in the influence of a particular node. Instead of accounting for this property in the mean function, we explicitly incorporate the interaction between nodes via the kernel function. Our kernel function quantifies the similarity in potential seeds sets by the number of common neighbors at time $t=1$.

$\mathsf{BOPIM}$ is much faster than a standard greedy approach since the costly objective function $f(\cdot)$ only needs to be evaluated $N_{0}+B$ times, as opposed to $O(nk)$ times for a greedy algorithm. Thus, the number of evaluations of the objective function for $\mathsf{BOPIM}$ is independent of $k$. Moreover, it is trivial to adapt the algorithm to other diffusion mechanisms. In practice, the diffusion model should be chosen with great care based on the application at hand. But since the diffusion model only appears in the evaluation of the objective function, and the objective function is treated as a “black-box”, changing the diffusion model has no impact on the implementation of the method. This differs from, e.g., Dynamic Degree (Murata and Koga,, 2018), which only works for the SI model, or Erkol et al., (2020), which is based on the SIR model.

In addition to its efficiency, $\mathsf{BOPIM}$ allows for uncertainty quantification (UQ) of the total influence spread, $\sigma(S)$, and seed set, $S$. By evaluating a given seed set using the posterior distribution of $\bm{\beta}$, we obtain a complete posterior predictive distribution for the total influence spread. This is in contrast with node-ranking heuristics, which do not yield an estimated influence spread, and probabilistic approximations, which yield a point estimate but not a measure of uncertainty of the total spread. Moreover, if a researcher wants to estimate the expected influence spread for another seed set $S^{\prime}\neq S$, then the entire calculation needs to be re-run for previous methods. After $\mathsf{BOPIM}$ has been fit once, the influence spread for any seed set can be estimated immediately and the uncertainty in the optimal seed set can also easily be quantified. Please see Section 3.4 for a full discussion of UQ in the seed sets.

2.5 Hyper-parameter selection

Finally, there are several hyper-parameters that need to be chosen for $\mathsf{BOPIM}$. Choosing $\gamma$, the kernel hyper-parameter, is perhaps the most tricky. We note that $\gamma$ corresponds to the contribution of ${\bf K}$ to the overall variance of the GP regression model. If $\gamma$ is small, then most of the variance is simply coming from the random noise term, $\epsilon_{i}$, but if $\gamma$ is large, then the variance in the objective function evaluations is largely driven by our kernel function. There are many different ways that we could choose $\gamma$. If we want a fully Bayesian approach, then we could endow $\gamma$ with a prior and update its posterior distribution during the MCMC routine. In practice, however, we found that this did not lead to very good performance and required adding a Metropolis-Hastings step to an otherwise entirely Gibbs sampler. Another choice is to fix $\gamma$ at its maximum likelihood estimate (MLE). In our experiments, this choice proved to perform better than the fully Bayesian approach, but the MLE estimate of $\gamma$ was consistently close to 1. Indeed, if instead of finding the MLE for $\gamma$ after each new observation we simply set $\gamma=1$, then this yielded the best performance. This choice corresponds to equal contribution from ${\bf K}$ and the random error term.

There are several other parameters that must be chosen in our algorithm. For the number of initial samples $N_{0}$ and BO loop iterations $B$, if these values are large, then the surrogate function will fit the true function well, but at a high computational cost. We found that setting $N_{0}=5$ and $B=25$ led to a good balance of fit and speed. To show that the BO iterations improve the solution quality, we report a progress curve in Figure 1 for a single run of the $\mathsf{BOPIM}$ algorithm. Please see Section 3 for a description of the network. We can clearly see that as the number of BO iterations increases, the total influence spread also increases. Indeed, for this particular example, the solution quality (percentage of influenced nodes) increases by 18 % during the BO loop, which corresponds to a relative increase of almost 100%.

Figure 1: Progress curve of $\mathsf{BOPIM}$ algorithm for Reality network.

For computing the posterior of $\bm{\beta}$ and $\sigma^{2}$, the number of MCMC samples also must be selected. Again, more MCMC samples lead to better estimates of the posterior distribution but also longer run-times. Since we only use the median of the posterior distribution, we can keep the number of MCMC samples relatively small to increase speed. We recommend 2,000 iterations with the first 500 used for burn-in. For hyper-parameters in the Horseshoe prior, we simply use the default settings from the original papers. Lastly, for the number of MC simulations for the objective function calculation, it is important that this output is accurate so we recommend 1,000 iterations. Unless otherwise noted, we use these settings for all experiments in Section 3.

3 Experiments

We now study the performance of the proposed method with numerical experiments. All experiments were performed in Python and the code for Algorithm 1 is available on GitHub: https://github.com/eyanchenko/BOPIM.

3.1 Data

The following experiments are conducted on four real-world networks. Reality ($n=64$, $m=722$) (Eagle and Pentland,, 2006), Hospital ($n=75$, $m=1139$) (Vanhems et al.,, 2013), Bluetooth ($n=136$, $m=5949$) (Kotz and Henderson,, 2004) and Conference 2 ($n=199$, $m=1550$) (Chaintreau et al.,, 2007) are all proximity networks where an edge exists if two people are close to each other. In order to discretize the continuous appearing and disappearing of edges, each network is aggregated into $T$ temporal snapshots of equal duration. We note that these networks are relatively small due to the slow speed of the greedy algorithm. Therefore, in the Supplemental Materials, we also conduct an experiment using the proposed method on the DNC email network (Rossi and Ahmed,, 2015) with $n=1891$ nodes to demonstrate its scalability.

3.2 Surrogate function validation

3.2.1 Settings

In the first set of simulations, we quantify the fit of the surrogate model to the true objective function $f(\cdot)$. Towards this end, we first run Algorithm 1 with $N_{0}=5$ and $B=25$ and save the final posterior distribution of $\bm{\beta}$. Using this posterior distribution, we then compute out-of-sample influence spread predictions on $N=100$ seed sets and compare with the values of the true objective function. If the surrogate model fits well, then its predicted influence spread will be close to the true influence spread. We quantify this similarity using the mean absolute prediction error (MAPE). If $\widehat{\bm{\beta}}$ is the posterior median of $\bm{\beta}$, and $\bm{x}^{*}$ corresponds to the new seed set, then

$$\hat{y}=(\bm{x}^{*})^{T}\hat{\bm{\beta}}+\kappa(\bm{x}^{*},{\bf X})^{T}(\gamma{\bf K}+{\bf I}_{N_{0}+b})^{-1}(\bm{y}-{\bf X}\hat{\bm{\beta}})$$

where $\kappa(\bm{x}^{*},{\bf X})_{j}=\kappa(\bm{x}^{*},\bm{x}_{j})$ for $j=1,\dots,N_{0}+B$. Recall that $\kappa(\bm{x}^{*},\bm{x}_{j})$ is the Jaccard coefficient between the neighbors of the seed set corresponding to $\bm{x}_{j}$ and $\bm{x}^{*}$. The MAPE is computed as

$$\frac{1}{N}\sum_{i=1}^{N}|\hat{y}_{i}-y_{i}|$$

where $N$ is the number of out-of-sample seed sets. A smaller MAPE means a closer fit.

We compute the MAPE for each of the four data sets. We fix $\lambda=0.05,0.05,0.01,0.01$, and $k=3,4,6,10$ for the Reality, Hospital, Bluetooth and Conference 2 datasets, respectively. $k$ was chosen as approximately 5% of the total number of nodes for each network. For the out-of-sample predictions, we consider two node sampling schemes. One samples nodes at random while the other samples according to their degree on the aggregate network, as in $\mathsf{BOPIM}$. We expect the model to have a closer fit when the test points are sampled in the same way as the training points. Results are averaged over 25 Monte Carlo (MC) replications.

3.2.2 Results

The results are in Table 1. Note that the MAPE results are interpreted as follows: for the Conference 2 network with degree-based sampling of seed sets, for example, the MAPE value of 1.23 means that, on average, the estimated influence spread of the surrogate function (3) is within about one node of the true influence spread. We can see that for all networks and both sampling schemes, the MAPE values are quite small. Additionally, the degree-based sampling always leads to smaller MAPE values, which is to be expected since this is how the $\mathsf{BOPIM}$ algorithm samples points for the initial fitting stage. Indeed, the surrogate model fits the true objective function more closely when the seed nodes have a large degree, which is where we hypothesize that the global optimum lies. These results give use confidence that our surrogate function is doing an adequate job of modeling the true objective function.

Dataset	Sampling	MAPE (se)
Reality	Random	3.60 (0.19)
	Degree	3.22 (0.11)
Hospital	Random	4.88 (0.16)
	Degree	3.49 (0.12)
Bluetooth	Random	2.78 (0.08)
	Degree	1.77 (0.04)
Conference 2	Random	7.45 (0.11)
	Degree	1.23 (0.05)

Table 1: Mean absolute prediction errors for validating surrogate function simulations. Standard error in parentheses.

3.3 Influence maximization

For the second set of experiments, we compare the method’s performance on the IM task.

3.3.1 Settings

We simulate the influence diffusion process and select seed sets for IM using $\mathsf{BOPIM}$. The main metrics of comparison are the number of influenced nodes at the conclusion of the spreading process, as well as the total algorithmic run time. We compare $\mathsf{BOPIM}$ with a greedy algorithm as this is considered the “gold standard” in IM. Erkol et al., (2022) proved that the SI model of diffusion is monotone and sub-modular so we use the CELF (Leskovec et al.,, 2007) step to increase the speed of the greedy algorithm. We also compare with random sampling seed nodes (Random), randomly sampling proportional to a nodes’ degree (Random Degree) and Dynamic Degree (Murata and Koga,, 2018). All experiments are conducted under the ex post assumption where the future evolution of the network is known when selecting seed nodes as in Murata and Koga, (2018); Osawa and Murata, (2015); Aggarwal et al., (2012); Erkol et al., (2020). While this assumption may be unrealistic in some cases, the main goal of this work is to propose a BO scheme for IM rather than tackling the ex ante problem (Yanchenko et al.,, 2023). We leave this as an important avenue of future work. Finally, to compare the different methods, we vary the number of seed nodes $(k)$, number of snapshots $(T)$, and infection parameter $(\lambda)$.

3.3.2 Results

First, we fix $T=10$ and $\lambda=0.05,0.05,0.01,0.01$ for the Reality, Hospital, Bluetooth and Conference 2 datasets, respectively, while varying $k$. For this setting, we record both the influence spread and computing time with the results in Figures 2 and 3. For each data set, the proposed BO method yields comparable influence spread to the greedy algorithm. For Hospital and Conference 2, in particular, the spreads are almost indistinguishable between the two methods. $\mathsf{BOPIM}$ also yields a larger influence spread then Dynamic Degree in almost all settings. While Random Degree performs similarly to Dynamic Degree for some settings, Random always performs the worst. In terms of computing time, the proposed method has a large advantage over the greedy algorithm. In each case, the computational time greatly increases with $k$ for the greedy algorithm, whereas that of the proposed method increases more slowly. For large $k$, the proposed method is as much as five times faster than the greedy algorithm.

Keeping the same values of $\lambda$ as before, we now fix $k$ such that roughly 5% of the total number of nodes are initially activated. We vary the number of aggregations of the temporal network, where small and large $T$ correspond to granular and fine aggregations, respectively. While the “real-time” that the network diffuses remains the same, we can vary the number of aggregations to see how this affects the influence spread. The results are in Figure 4. The trends are similar to that of varying $k$. Across networks and $T$, the proposed method yields comparable influence spread to that of the greedy algorithm, performing especially well in the Reality and Hospital networks. Dynamic Degree and Random Degree again yield consistently smaller influence spreads than both $\mathsf{BOPIM}$ and Greedy. In general, the total spread increases with $T$ as there are more rounds for influence to diffuse, but this trend need not be monotonic as different aggregations changes when certain nodes have edges. Indeed, in the Reality network, Dynamic Degree’s results are quite sensitive to $T$ as compared to the proposed method.

Finally, we fix $k$ at 5% of $n$ and $T=10$ and vary the infection probability $\lambda$. The results are in Figure 5 and are similar for each network: as $\lambda$ increases, the total influence spread also increases. The distinction between different methods is least pronounced in this setting, but $\mathsf{BOPIM}$ has almost identical influence spreads to Greedy in all settings and networks.

Figure 2: Influence spread results for increasing seed size $(k)$.

Figure 3: Computation time results for increasing seed size $(k)$.

Figure 4: Influence spread results for increasing number of snapshots $(T)$.

Figure 5: Influence spread results for increasing infection probability $(\lambda)$.

3.4 Uncertainty quantification

The proposed method also provides measures of uncertainty for the optimal seed sets. Uncertainty quantification (UQ) allows for a richer understanding of the outputted solution and can answer questions such as: Are there many seed sets which yield near optimal spread? Can the selection of seed nodes be viewed on a spectrum as opposed to binary inclusion/exclusion? We take a first step towards answering these questions with the proposed method.

There are two main ways that we can use the $\mathsf{BOPIM}$ output for UQ. First, recall that we use GP regression to model the objective function. In (3), $\beta_{i}$ corresponds to the inclusion ($x_{i}=1$) or exclusion ($x_{i}=0$) of node $i$ in the seed set, and we obtain the complete posterior distribution for each coefficient. For the acquisition function step of $\mathsf{BOPIM}$, we only use the median of this posterior distribution. We can leverage the entire distribution, however, to obtain a clearer picture of a node’s importance.

To do this, we save the final posterior distribution of $\bm{\beta}$ in $\mathsf{BOPIM}$ for the Reality network with $k=5$, $T=10$, $\lambda=0.05$ (15,000 MCMC samples, 5,000 burn-in). In Figure 6(a), we report the box-plot for the posterior distribution of $\beta_{i}$ for each node $i\in\{1,\dots,n\}$. The largest posterior distributions correspond with the ideal nodes for the seed set. From the figure, nodes 2, 3, 38 and 59 have noticeably larger values of the posterior distribution than that of the other nodes. Thus, while $k=5$ nodes are chosen for the seed set, it may be that nodes 2, 3, 38 and 59 are more influential than the other node included in the seed set.

While $\mathsf{BOPIM}$ seeks the global optimum of our objective function, in practice, running the algorithm multiple times will give different optimal seed sets due to the randomness inherent in the algorithm. We can leverage this randomness for another way to quantify the uncertainty in the optimal seed sets. We now run the algorithm for 50 MC simulations (1,500 MCMC samples with 500 burn-in), and for each iteration, we find the optimal seed set. Then we can average these results to find the proportion of times that each node is assigned to the optimal seed set. These proportions are reported in Figure 6(b). For example, node 2 was selected in the seed set in 100% of the iterations, thus making it the most influential node. While nodes 1, 2 and 3 have noticeably larger proportions than all other nodes, the fourth and fifth largest (6 and 9) have much smaller proportions than that of those three.

Finally, we note some differences between the two methods of UQ. Since Figure 6(b) is based on a single iteration, the results are subject to more stochastic variability, whereas much of this effect is averaged out in Figure 6(b). For example, nodes 38 and 59 appear to be key candidates for the seed set based on their large posterior distribution, but once we average over the results we see that these very rarely appears in the top $k$ of all nodes. On the other hand, the posterior mean of nodes 9 and 6 are close to zero in this one iteration, but they are the fourth and fifth most important nodes, respectively, when we re-run the algorithm many times. Regardless, these two figures together give us a good sense of the uncertainty in our optimal seed set and show that there are multiple sets of $k$ nodes which likely yield similar influence spreads.

(a) Posterior distribution box plots of $\bm{\beta}$.

(b) Proportion of MC samples selected for seed set.

Figure 6: Posterior distribution summaries for the Reality network.

4 Discussion and conclusion

In this work, we apply a Bayesian Optimization framework to solve the influence maximization problem on temporal networks. The proposed $\mathsf{BOPIM}$ algorithm models the influence spread function via Gaussian Process regression and Horseshoe shrinkage prior. A simple mean function quantifies the importance of each nodes in the seed set, while our kernel function computes the correlation between seed sets based on their number of common neighbors. Experiments showed that despite being such a simple surrogate, the statistical model’s estimated influence spread is, on average, within a few nodes to the true spread. In the IM simulations, the proposed method yields influence spreads comparable to that of seed sets from a greedy algorithm. The BO approach, however, is much faster than the greedy algorithm. While in some settings, Dynamic Degree or Random Degree may have been similar to $\mathsf{BOPIM}$, the proposed algorithm consistently yielded the best results across all networks and settings. Moreover, the UQ found evidence that there are many seed sets which yield comparably optimal influence spread, thus implying that the objective function is relatively “flat.”

There are many interesting avenues to extend this work. First, we could study the performance of the proposed method under various forms of model mis-specification. Indeed, we take a first step in this direction in the Supplemental Materials where we consider two different cases. First, the algorithm is trained on one value of $k^{\prime}$ but then the resulting model fit is used to find the optimal seed set for $k\neq k^{\prime}$. In the second setting, we fit the algorithm on one value of $T^{\prime}$, the number of temporal snapshots, and then use the resulting seed set to compute the influence spread on the network with $T\neq T^{\prime}$ snapshots. In both cases, the $\mathsf{BOPIM}$ algorithm performs quite favorably. This not only implies a robustness of the method, but also can lead to computational advantages as the model may not need to be re-fit for every new parameter combination. These are important and encouraging findings, but there is certainly room for more study.

The posterior sampling scheme is another area where future work could be needed. In this work, we used a fully Gibbs approach to sample from the posterior distribution. As the size of the network increases, however, this step will become slower and more difficult. Thus, alternative approaches like Variational Bayes (Kingma and Welling,, 2013), where direct sampling from the posterior distribution is replaced with an optimization problem, may be necessary for computational advantages. Another area of extension is considering more complicated surrogate functions that take into account interactions between nodes in the seed set (Baptista and Poloczek,, 2018). This should lead to better performance that may even exceed the greedy algorithm. The number of parameters in the model, however, would be $O(n^{2})$ which could lead to computational challenges. Considering the ex ante IM task is another important open-problem.

Supplemental Materials

Horseshoe prior Gibbs sampler

In this section, we report the Horseshoe prior (Polson and Scott,, 2010) Gibbs sampler, using the auxiliary variable formulation of Makalic and Schmidt, (2015).

1. Sample $\bm{\beta}|\bm{\lambda},\bm{\nu},\tau^{2},\sigma^{2},{\bf Y}\sim\mathsf{N}(\bm{\mu},\sigma^{2}{\bf V})$ where $\bm{\mu}={\bf V}{\bf X}^{T}{\bf Y}$, ${\bf V}=({\bf X}^{T}{\bf K}^{-1}{\bf X}+{\bf S}^{-1})^{-1}$,
   ${\bf S}=diag(\lambda_{1}^{2}\tau^{2},\dots,\lambda_{n}^{2}\tau^{2})$.

2. Sample $\sigma^{2}|\bm{\beta},\bm{\lambda},\bm{\nu},\tau^{2},,{\bf Y}\sim\mathsf{IG}(a_{1}+(N_{0}+n)/2,b_{1}+(({\bf Y}-{\bf X}\bm{\beta})^{T}{\bf K}^{-1}({\bf Y}-{\bf X}\bm{\beta})+\bm{\beta}^{T}{\bf S}^{-1}\bm{\beta})/2)$.

3. Sample $\lambda_{j}^{2}|\bm{\beta},\bm{\nu},\tau^{2},\sigma^{2}\sim\mathsf{IG}(1,\nu_{j}^{-1}+\beta^{2}_{j}/(2\tau^{2}\sigma^{2})$, $j=1,\dots,n$

4. Sample $\tau^{2}|\bm{\beta},\bm{\lambda},\sigma^{2},\xi\sim\mathsf{IG}((n+1)/2,\xi^{-1}+\sum_{k=1}^{n}\beta^{2}_{k}/(2\lambda^{2}_{k}\sigma^{2}))$.

5. Sample $\nu_{j}|\lambda_{k}\sim\mathsf{IG}(1,1+\lambda_{j}^{-2})$ for $j=1,\dots,n$.

6. Sample $\xi|\tau^{2}\sim\mathsf{IG}(1,1+\tau^{-2})$.

Greedy algorithm for $EI(\cdot)$

Result: Optimum seed set $\tilde{\bm{x}}$

Input: seed set size $k$, current optimum $\tilde{y}$, sampled sets ${\bf X}$, observations $\bm{y}$, ;

Initialize seed set $S$

$run=1$

while $run>0$ do

       $run=0$  Randomly order nodes  for $v\in S$ do

             for $u\in V\setminus S$ do

                   $S^{\prime}=S$  Remove $v$ from $S^{\prime}$ and replace with $u$  if $EI(S^{\prime})>EI(S)$ then

                         $S=S^{\prime}$  $run=1$ 

                   end if

                  

             end for

            

       end for

      

end while

Algorithm 2 Greedy

IM for large networks

To demonstrate the performance of $\mathsf{BOPIM}$ on large networks, we present the results for IM on the DNC email network (Rossi and Ahmed,, 2015) with $n=1891$ nodes. We fix $\lambda=0.05$ and $T=10$ while varying $k=25,50,\dots,100$. Because of the long run times, we set $N_{0}=5,\ B=20$ and only use 3 MC simulations for $\mathsf{BOPIM}$, but still use 25 for Random and Random Degree. The influence spread results and run times are in Figure 7. We can see that the proposed method provides comparable results to the greedy algorithm, but is faster for all but the first value of $k$. While $\mathsf{BOPIM}$ performs similarly to Random Degree, it greatly outperforms Dynamic Degree.

Figure 7: Results for Email DNC network.

Robustness experiments

In this section, we explore the robustness of the proposed method to varying the size of the seed set as well as the number of temporal snapshots.

Varying $k$

First, we are interested in the performance of the proposed method when the fitting steps are done on one value of $k^{\prime}$, but then we find the optimal seed set for $k\neq k^{\prime}$. Specifically, we let $k^{\prime}$ be fixed and then run the $\mathsf{BOPIM}$ algorithm for $B$ BO loop iterations as usual. After the last iteration, however, we re-fit the GP regression model and use the acquisition function to find the optimal seed set of size $k$ which is not necessarily the same as $k^{\prime}$. We then use this seed set to compute the number of influenced nodes on the network.

In the following experiments, we fix $\lambda=0.05$ and $T=10$ and look at the Reality and Hospital networks. All other hyper-parameters are the same as in the previous experiments. We consider four different methods, Low, Mid, High and Mix. For Low, Mid and High, the BO routine is carried out setting $k^{\prime}=1,4$ and $7$, respectively. For Mix, we randomly sample $k^{\prime}$ from a uniform distribution on $\{1,2\dots,7\}$ at each stage in the initial fitting as well as the BO loop. For each method, we then compute the optimal seed set of size $k$ for $k=1,\dots,7$. The results are repeated 25 times and averaged for each value of $k$. We compare the results with the original $\mathsf{BOPIM}$ algorithm where the same $k$ is used in the training phase of the algorithm as well as the final influence spread evaluation.

Note that even when the network is trained on seed set of size $k^{\prime}$ and then tested on sets of size $k=k^{\prime}$, this is still not equivalent to the original $\mathsf{BOPIM}$ algorithm. In the original algorithm, the model is fit on one value of $k$ throughout the $B$ BO iterations and then the set seed which corresponded to the largest influence spread is then chosen as the optimal set. In these robustness simulations, on the other hand, the final posterior distribution is used to select the optimal seed set. Therefore, Low, for example, is not equivalent to $\mathsf{BOPIM}$ even when $k^{\prime}=k=1$.

Now, the results are in Figure 9. In the Reality network, for $k=2$, Low comes closest to the original $\mathsf{BOPIM}$ algorithm. When $k=3,4,5$, Mid performs well while High does the best for large $k$. Mix, however, yields seed sets with noticeably smaller influence spreads. In the Hospital network, Low, Mid and High all perform comparably well when $k\geq 4$ with Low and Mid yielding slightly larger optimal spreads for smaller values of $k$. Again, Mix is clearly performing quite poorly.

These findings are promising for the performance of the $\mathsf{BOPIM}$ algorithm. In particular, it means that even if we run the algorithm for one value of $k^{\prime}$, the results can be used to select seed sets of various sizes. Additionally and not surprisingly, these results also show that as $|k^{\prime}-k|$ increases, the performance seems to decrease slightly. Thus, the method will yield better seed sets when $k^{\prime}\approx k$. This not only shows the generalizability of the method, but also can save computing time as the algorithm may not need to be re-run for each value of $k$. Finally, a single $k^{\prime}$ should be used in the algorithm’s model fitting as the Mix method consistently performed poorly.

Figure 8: Robustness simulations where the size of the seed set in the model fitting is different from the final seed set.

Varying $T$

This sub-section is similar to the previous, except now we are looking at the robustness of the $\mathsf{BOPIM}$ algorithm to different values of $T$, the number of temporal snapshots. In particular, we run the $\mathsf{BOPIM}$ algorithm for some fixed $T^{\prime}$ and obtain the optimal seed set. This seed set is then used to compute the influence spread on the same network but now with $T\in\{2,3,\dots,10\}$ snapshots. This scenario can be considered as model mis-specification as the number of snapshots is not correctly known.

We fix $\lambda=0.05$ and $k=3,4$ for the Reality and Hospital network, respectively. We now consider three different methods, Low, Mid and High. For these methods, we train the proposed method on the network using $T^{\prime}=2,5$ and $10$, respectively. We then use the resulting seed sets to compute the influence spread on the same network but with $T=2,3,\dots,10$. The results are again averaged over 25 repetitions for each value of $T$ and compare with the $\mathsf{BOPIM}$ algorithm fit using the correct value of $T$.

The results are in Figure 9. For the Reality network, both Mid and High perform similarly and nearly approximate the correctly-specified algorithm. Low, however, yields seed sets with smaller influence spreads. In the Hospital network, Low, Mid and High all perform comparably well in relation to the original algorithm.

Again, these results are favorable for the $\mathsf{BOPIM}$ algorithm. They show that the algorithm can be fit on almost any value of $T^{\prime}$ and the resulting seed set will yield large influence spreads for nearly all $T$. Moreover, they imply that the optimal seed set is not very sensitive to the number of snapshots used to aggregate the temporal network. For example, if a node is influential with $T=5$ snapshots, it is also likely to be influential with $T=10$ snapshots. This is somewhat expected as central nodes should be influential regardless of the network aggregation scheme. Thus, the proposed algorithm is relatively robust to the choice of $T$.

Figure 9: Robustness simulations where the number of temporal snap shots in the model fitting is different from influence spread calculation.