Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs

In this paper, we propose an algorithm for computing $\sigma (S)$ for given $S$ under the IC model. Specifically, the proposed algorithm simultaneously computes $\text{Pr}(S\rightsquigarrow v)$ in an uncertain directed graph for all vertices $v$. Our main result can be expressed as follows.

Since even inputting the entire graph requires linear time, this algorithm is asymptotically optimal for graphs with a bounded pathwidth when the constant factor is ignored. Moreover, the exponential factor of the pathwidth, hidden in the constant, remains the same as in the algorithm of Maehara et al. [15]: the dependence on the graph sizes is improved from $O(mn)$ to $O(m+n)$ while the dependence on the pathwidth is kept the same.

Our algorithm shares certain ideas with the existing algorithm for simultaneously computing the probabilities of connection in undirected graphs [16] in that both use similarities in the computation of the previous algorithms [8, 15] for different vertices. However, there is a non-trivial gap in extending that algorithm [16] to directed graphs due to the difference between connectivity in undirected graphs and reachability in directed graphs. We fill this gap by finding additional similarities in computing $\sigma (S)$ with the previous algorithm [15]; details are discussed in Section 5.

Influence maximization.

The most well-studied problem related to influence spread is influence maximization [10], that is, the problem of choosing a seed set $S$ to maximize the influence spread. This has attracted much attention over the past two decades [12, 14, 19]. Although the influence maximization problem under most diffusion models including the IC model is NP-hard [10], a simple greedy algorithm [10] can achieve a $(1-1/e)$-approximation provided that every $\sigma (S)$ is computed exactly. Various methods, e.g., the sketch-based methods described in a survey [12], have improved this greedy algorithm. However, if we resorted to using Monte Carlo simulation to evaluate $\sigma (S)$, we could not obtain a deterministic approximation bound for influence maximization, even with greedy or more sophisticated algorithms. Moreover, although many studies have used an alternative proxy for $\sigma (S)$ to speed up the computation (e.g., proxy-based methods [12] and learning-based methods [14]), they also lack approximation bounds. This situation accentuates the theoretical importance of an exact evaluation of influence spread.

Network reliability.

Computing the probability that some vertices are connected in an uncertain graph has been traditionally studied as network reliability evaluation in the network community. Most studies on network reliability evaluation have modeled the network as an undirected graph and, given a vertex set $K$ and the probability $p_e$ of presence for every edge, they computed the probability that the vertices in $K$ are connected. Even for undirected graphs, computing this probability is #P-complete [22]. Nevertheless, Hardy et al. [8] developed an algorithm that could compute this probability in linear time for graphs with bounded pathwidth. Another line of research has attempted to compute the expected number of vertices connected to vertex $u$ [17], which is an analogue of the influence spread under the IC model for undirected graphs. Nakamura et al. [16] proposed an algorithm that could compute the probability that a vertex $u$ is connected to $v$ for every $v\in V$ in linear time for an undirected graph with bounded pathwidth. By summing all the probabilities for every $v$, it is also possible to compute the expected number of vertices connected to $v$ in linear time. This algorithm uses the similarities in the computation of the probability that $u$ and $v$ are connected with Hardy’s algorithm [8] for different $v$; therefore, it shares similar ideas with our work. However, we cannot straightforwardly extend this algorithm to handle directed graphs, as described in Section 1; detailed discussions are given in Section 5. Note that these algorithms [8, 16] also run in polynomial time for graphs with bounded pathwidth, indicating the importance of algorithms dealing with bounded-pathwidth graphs.

In the following, we review Maehara’s algorithm [15] for exactly computing $\text{Pr}(S\rightsquigarrow v)$ for a given $S,v$. Although the literature [15] only showed the algorithm for the case $|S|=1$, here we show the general $S$ case because it can be easily extended.

The basic idea in evaluating $\text{Pr}(S\rightsquigarrow v)$ is to decompose $\text{Pr}(S\rightsquigarrow v)$ into terms that can be easily computed. For $E^{\prime },E^{\prime \prime }\subseteq E$ such that $E^{\prime }\cap E^{\prime \prime }=\mathrm{\varnothing }$, let $\text{Pr}(\cdot \mid E^{\prime },\overline{E^{\prime \prime }})$ be the conditional probability given that the edges in $E^{\prime }$ are present and those in $E^{\prime \prime }$ are absent. From the case analysis of whether $e\in E\setminus (E^{\prime }\cup E^{\prime \prime })$ is present or absent,

By ordering edges as $e_1,\mathrm{\dots },e_m$, $\text{Pr}(S\rightsquigarrow v)$ can be decomposed by recursively applying (2):

This expansion eventually reaches the definition $\text{Pr}(S\rightsquigarrow v)≔{\sum }_{E^{\prime }\in {ℰ}_{S\rightsquigarrow v}}\text{Pr}(E^{\prime })$. Therefore, by using this decomposition naively, we have $O(2^m)$ terms, which incurs exponential complexity of the graph size in evaluating it.

To prevent this, we attempt to detect the equality among probabilities, i.e., to find subsets such that . If such equality can be detected, we simply need to further decompose only one among the equal probabilities, which reduces the number of terms. If the following condition (#) holds, we can confirm :

(#) For any , $S{\rightsquigarrow }_{(V,E^{\prime }\cup H)}v$ if and only if $S{\rightsquigarrow }_{(V,F^{\prime }\cup H)}v$.

To check condition (#), we focus on the reachability relation on the subgraph $(V,E^{\prime })$. If $u{\rightsquigarrow }_{(V,E^{\prime })}w$ and $w{\rightsquigarrow }_{(V,F^{\prime })}v$ are equivalent for any $u,w\in V$, we can confirm that (#) holds. In brief, this is because, given a path from $s\in S$ to $v$ on $(V,E^{\prime }\cup H)$, we can construct a path from $s$ to $v$ on $(V,F^{\prime }\cup H)$ by using the above equivalence, and vice versa.

Maehara et al. [15] indicated that only a limited subset of vertices called frontier vertices is important for checking (#).

We consider the reachability relations among $W_i\cup S\cup \{v\}$ on $(V,E^{\prime })$ as follows.

We can then prove the following.

This can be shown by transforming a $u$-$v$ directed path on $(V,E^{\prime }\cup H)$ for some $u\in S$ to a $u^{\prime }$-$v$ directed path on $(V,F^{\prime }\cup H)$ for some $u^{\prime }\in S$. Now we can rewrite as $\text{Pr}(S\rightsquigarrow v\mid {\mathrm{\Phi }}_i^v(E^{\prime }))$.

Moreover, ${\mathrm{\Phi }}_i^v(\cdot )$ has the following property: if ${\mathrm{\Phi }}_i^v(E^{\prime })={\mathrm{\Phi }}_i^v(F^{\prime })$ for , both ${\mathrm{\Phi }}_{i+1}^v(E^{\prime })={\mathrm{\Phi }}_{i+1}^v(F^{\prime })$ and ${\mathrm{\Phi }}_{i+1}^v(E^{\prime }\cup \{e_i\})={\mathrm{\Phi }}_{i+1}^v(F^{\prime }\cup \{e_i\})$ hold. Thus, there exist transition functions ${\mathrm{𝗅𝗈}}^v,{\mathrm{𝗁𝗂}}^v$ from ${\mathrm{\Phi }}_i^v$ to ${\mathrm{\Phi }}_{i+1}^v$ satisfying ${\mathrm{𝗅𝗈}}^v({\mathrm{\Phi }}_i^v(E^{\prime }))={\mathrm{\Phi }}_{i+1}^v(E^{\prime })$ and ${\mathrm{𝗁𝗂}}^v({\mathrm{\Phi }}_i^v(E^{\prime }))={\mathrm{\Phi }}_{i+1}^v(E^{\prime }\cup \{e_i\})$ for any . By combining this fact and (2), we have, for any ,

Using this decomposition recursively, $\text{Pr}(S\rightsquigarrow v)$ can be decomposed as follows:

In other words, $\text{Pr}(\mathrm{\Phi })$ is the probability that TC $\mathrm{\Phi }$ appears and ${𝒩}_i$ is the set of all TCs of the subsets of . We later show that $|{𝒩}_i|$ is bounded by a constant if the pathwidth is bounded in Lemma 4.15. This is the main reason to achieve $O(m)$ time complexity in computing $\text{Pr}(S\rightsquigarrow v)$.

For some TCs $\mathrm{\Phi }$, we can confirm that $S\rightsquigarrow v$ must hold or must not hold, i.e., $\text{Pr}(S\rightsquigarrow v\mid \mathrm{\Phi })=1$ or $0$. For such TCs, we do not need to further decompose $\text{Pr}(S\rightsquigarrow v\mid \mathrm{\Phi })$ with (4). We define such base cases with the following $\top$-pruning and $\perp$-pruning as follows. Let $i_u$ be the largest index $i$ such that one of the endpoints of $e_i$ is $u$ and let $i_S≔{\max }_{u\in S}{i}_u$.

• $\mathrm{■}$

  If ${\mathrm{𝗁𝗂}}^v{(\mathrm{\Phi })}_{Sv}=1$, determining the presence of $e_i$ confirms $S\rightsquigarrow v$, i.e., $\text{Pr}(S\rightsquigarrow v\mid {\mathrm{𝗁𝗂}}^v(\mathrm{\Phi }))=1$. In such a case, we let ${\mathrm{𝗁𝗂}}^v(\mathrm{\Phi })=\top$, a special TC meaning that $S\rightsquigarrow v$ must hold ($\top$-pruning).

• $\mathrm{■}$

  Suppose that $i\ge i_S$ and ${\mathrm{𝗅𝗈}}^v{(\mathrm{\Phi })}_{Su}=0$ for any $u$, or that $i\ge i_v$ and ${\mathrm{𝗅𝗈}}^v{(\mathrm{\Phi })}_{uv}=0$ for any $u$. In these cases, no further vertices can be reached from $S$ or reach $v$ by determining the absence of $e_i$, i.e., $\text{Pr}(S\rightsquigarrow v\mid {\mathrm{𝗅𝗈}}^v(\mathrm{\Phi }))=0$. Thus, we let ${\mathrm{𝗅𝗈}}^v(\mathrm{\Phi })=\perp$, which is a special TC meaning that $S\rightsquigarrow v$ must not hold ($\perp$-pruning)¹¹1Although the original version [15] uses different pruning rules, they require a pre-computation of transitive closures of $(V,E_{\ge i})$, which takes cubic time. We use an alternative pruning rule that can be checked in linear time.. We also let ${\mathrm{𝗁𝗂}}^v(\mathrm{\Phi })=\perp$ if $\top$-pruning does not occur and ${\mathrm{𝗁𝗂}}^v(\mathrm{\Phi })$ satisfies the same condition as above.

Eventually, all the TCs are transformed into either $\top$ or $\perp$, and (5) reaches $\text{Pr}(S\rightsquigarrow v)=\text{Pr}(\top )\cdot 1+\text{Pr}(\perp )\cdot 0=\text{Pr}(\top )$. Thus, computing $\text{Pr}(\top )$ is sufficient for evaluating $\text{Pr}(S\rightsquigarrow v)$.

Now we describe the procedure to compute $\text{Pr}(\top )$. We again use the transition of TCs. By considering the pruning described above, we redefine the set of TCs as ${𝒩}_1^{\prime }≔\{{\mathrm{\Phi }}_1^v(\mathrm{\varnothing })\}$ and ${𝒩}_i^{\prime }≔\left({\bigcup }_{\mathrm{\Phi }\in {𝒩}_{i-1}^{\prime }}\{{\mathrm{𝗁𝗂}}^v(\mathrm{\Phi }),{\mathrm{𝗅𝗈}}^v(\mathrm{\Phi })\}\right)\setminus \{\top ,\perp \}$, i.e., we remove the pruned TCs from ${𝒩}_i$. Then, from the definition of $\text{Pr}(\mathrm{\Phi })$ (Eq. (6)), we have

To compute $\text{Pr}(\top )$, we can use a similar formula:

Starting from ${𝒩}_1^{\prime }=\{{\mathrm{\Phi }}_1^v(\mathrm{\varnothing })\}$, we can generate ${𝒩}_{i+1}^{\prime }$ from ${𝒩}_i^{\prime }$ recursively using transition functions ${\mathrm{𝗁𝗂}}^v,{\mathrm{𝗅𝗈}}^v$. By recording the transition, we can compute every $\text{Pr}(\mathrm{\Phi })$ and $\text{Pr}(\top )$ with (7) and (8).

Algorithm 1 formally presents the procedures. Lines 1–7 recursively generate the successive TCs using transition functions ${\mathrm{𝗅𝗈}}^v,{\mathrm{𝗁𝗂}}^v$ while executing $\perp ,\top$-pruning. This process can be seen as constructing a diagram of TCs as in Figure 3. Every $\mathrm{\Phi }$ except for $\perp ,\top$ has two outgoing edges heading to ${\mathrm{𝗅𝗈}}^v(\mathrm{\Phi })$ and ${\mathrm{𝗁𝗂}}^v(\mathrm{\Phi })$. In Algorithm 1, each $\mathrm{\Phi }$ has two entries $\mathrm{\Phi }.\mathrm{𝗅𝗈}$ and $\mathrm{\Phi }.\mathrm{𝗁𝗂}$ that store the pointer to ${\mathrm{𝗅𝗈}}^v(\mathrm{\Phi })$ and ${\mathrm{𝗁𝗂}}^v(\mathrm{\Phi })$. Here, ${𝒩}_i^{\prime }$ stores the TCs of the subsets of as a hash map; pruned TCs are not stored. Along this diagram, we can compute every $\text{Pr}(\mathrm{\Phi })$ with simple dynamic programming (DP) in lines 8–13; this simulates the formulas (7) and (8). The array $\text{p}[\mathrm{\Phi }]$ for $\mathrm{\Phi }\in {𝒩}_i^{\prime }$ is prepared to store $\text{Pr}(\mathrm{\Phi })$. Note that even if an identical TC $\mathrm{\Phi }$ appears in ${𝒩}_i^{\prime }$ and ${𝒩}_j^{\prime }$ $(i\ne j)$, we distinguish $\mathrm{\Phi }\in {𝒩}_i^{\prime }$ and $\mathrm{\Phi }\in {𝒩}_j^{\prime }$ in computing $\text{p}[\cdot ]$. After computing all $\text{p}[\mathrm{\Phi }]$, $\text{Pr}(S\rightsquigarrow v)=\text{Pr}(\top )$ is stored in $\text{p}[\top ]$.

Next, we analyze the complexity of this algorithm. For each TC $\mathrm{\Phi }$, computing ${\mathrm{𝗅𝗈}}^v(\mathrm{\Phi })$ and ${\mathrm{𝗁𝗂}}^v(\mathrm{\Phi })$ takes $O({(|W_i|+|W_{i+1}|)}^2)$ time; details are in Lemma 4.14 of Section 4.4. If every ${𝒩}_i^{\prime }$ is implemented as a hash map, storing or searching a TC also takes $O({|W_i|}^2)$ time. The number of patterns on ${\mathrm{\Phi }}_i^v$ can be bounded by $O(2^{{|W_i|}^2})$; since this was not rigorously proved [15], we prove it in Lemma 4.15 of Section 4.4. The overall complexity can be bounded by $O({\sum }_i{(|W_i|+|W_{i+1}|)}^2\cdot 2^{{|W_i|}^2})=O(m{\omega }^2\cdot 2^{{\omega }^2})$, where $\omega ={\max }_i|W_i|$.

In fact, $\omega$ is related to the pathwidth of a graph. Given a path decomposition of $G$ with width ${\omega }_p$, we can generate an edge ordering with $\omega \le {\omega }_p$ in linear time [9]. Since we can construct a path decomposition in linear time for a graph with bounded pathwidth [2], we have a linear time algorithm for computing $\text{Pr}(S\rightsquigarrow v)$ on a graph with bounded pathwidth. However, computing $\sigma (S)$ requires $O(mn{\omega }^2\cdot 2^{{\omega }^2})$ time by computing $\text{Pr}(S\rightsquigarrow v)$ for $v\in V\setminus S$.

We formally state the equivalence of different diagrams of TCs for upper levels ($v\in B_i$), lower levels ($v\in A_i$), and middle levels ($v\in W_i$).