Identifying the most influential spreaders is an important issue for the study of the dynamics of information diffusion in complex networks. In this paper we analyze the following spreading model. Initially, a few nodes know a piece of information and are active spreaders of it. At subsequent rounds, spreaders communicate the information to their neighbors. Upon receiving the information, a node becomes aware of it but does not necessarily become a spreader; it starts spreading only if it gets the information from a sufficiently large number of its neighbors. We study the problem of choosing the smallest set of initial spreaders that guarantee that all the nodes become aware of the information. We provide hardness results and show that the problem becomes tractable on trees. In case of general graphs, we provide an efficient algorithm and validate its effectiveness (in terms of the solution size) on real-life networks.
During the past decade spreading processes in complex networks have experienced
a particular surge of interest. A large part of research activity in the area deals
with the analysis of influence spreading in social networks. There are many
situations where members of a network may influence their neighbors’ behavior
and decisions, by swaying their opinions, by suggesting what products to buy,
or simply by passing on a misinformation [
We model the network as an undirected graph G = (V, E), where V is the set of individuals and the set of edges E represents the relationships among members of the network, i.e., (u, v) ∈ E if individuals u and v can directly communicate. We posit a threshold function t : V → {0, 1, 2, . . .}, and we denote by N (v) the neighborhood of v ∈ V . An active diffusion process starting at S ⊆ V is a sequence of node subsets: SpreaderG[S, τ ], τ = 0, 1, . . . , such that SpreaderG[S, 0] = S and SpreaderG[S, τ ] = SpreaderG[S, τ − 1] ∪ nu s.t. N (u) ∩ SpreaderG[S, τ − 1] ≥ t(u)o, for τ ≥ 1. The process terminates when SpreaderG[S, ρ] = SpreaderG[S, ρ − 1] for some ρ > 1. We denote by SpreaderG[S] = SpreaderG[S, ρ]. Hence, when the process stops the set of aware nodes is
AwareG[S] = SpreaderG[S] ∪ n o u s.t. N (u) ∩ SpreaderG[S] 6= ∅ .
Given G, a threshold function t(·), we aim to identify a small node set S ⊆ V such that AwareG[S] = V .3 Namely, we consider the following problem, P e r f e c t Awa r e n e s s ( PA ).
Instance: A graph G = (V, E), node thresholds t : V −→ N0.
Question: Find a seed set S ⊆ V of minimum size such that Aware[S] = V . We refer to the set S for which Aware[S] = V as a perfect seed set and to the nodes in S as seeds. 1.1
The above algorithmic problem has its roots in the area of the spread of
influence in Social Networks. Maximizing the spread of viral information across a
network naturally suggests many interesting optimization problems (see [
However, the papers appeared in the scientific literature considered the basic
model in which any node, as soon as it is influenced by its neighbors, it
immediately starts spreading influence. In this paper we consider a more refined model
that differentiates among spreaders and plain aware node. This model has been
first considered in [
In Section 2, we study the computational complexity of the PA problem and extend the TSS problem hardness result to the PA problem. In Section 3, we give an algorithm that outputs a perfect seed set for any input graph. Experimental evaluation of the proposed algorithm is given in Section 4; it shows that the proposed algorithm outperforms some heuristics developed for related problems. Finally, we show that our problem becomes tractable if the graph is a tree (Section 5).
We would like to remark that if the threshold t(v) is equal to the node degree d(v), for each v ∈ V , then a perfect target set for G is, indeed, a dominating set for G. Hence, the proposed algorithm outputs a dominating set for G and computational experiments suggest that it performs very well in practice. 2
We prove the hardness of the PA problem by constructing a gap-preserving
reduction from the TSS problem. We recall that the TSS problems, given G =
(V, E) with threshold function t : V → N , asks to identify a minimum size S ⊆ V
such that Spreader[S] = V . Our Theorem 1 follows from the inapproximability
results for the TSS problem given in [
Theorem 1. The PA problem cannot be approximated within a ratio of O(2log1− n), for any > 0, unless NP⊆DTIME(npolylog(n)).
Proof. We give a reduction from the Ta r g e t S e t S e l e c t i o n problem. Consider an instance of the TSS problem consisting in a graph G = (V, E) with threshold function t(·). Let V = {v1, . . . , vn}, we build a graph G0 = (V 0, E0) as follows: – Replace each vi ∈ V by a triangle in which the node set is Vi0 = {vi,0, vi,1, vi,2}.
Formally, – V 0 = Sin=1 Vi0 = {vi,j | 1 ≤ i ≤ n, 0 ≤ j ≤ 2} – E0 = {(vi,0, v`,0) | 1≤i<`≤n, (vi, v`) ∈ E } S
{(vi,j , vi,`) | i = 1, . . . , n, 0≤j<`≤2 }; – the thresholds are t0(vi,0) = t(vi) and t0(vi,1) = t0(vi,2) = 2, for i = 1, . . . , n. Notice that G corresponds to the subgraph of G0 induced by the set {vi,0|1 ≤ i ≤ n}. We show that there exists a target set S ⊆ V for G iff there exists a perfect seed set S0 ⊆ V 0 for G0 such that |S0| = | | S .
Assume first that S ⊆ V is a target set for G. Since SpreaderG[S] = V , then all the nodes vi,0 ∈ Vi0 will become spreaders in G0 when the seed set is S0 = {vi,0 ∈ V 0|vi ∈ S}. Once a node vi,0 becomes a spreader the nodes vi,1, vi,2 are aware in the next round. Hence, S0 is a perfect seed set for G0, that is AwareG0 [S0] = V 0. Assume now that S0 ⊆ V 0 is a perfect seed set for G0. Let S00 = {vi,0 ∈ V 0 | S0 ∩ Vi0 6= ∅}. It is easy to observe that AwareG0 [S00] = AwareG0 [S0] = V 0. Let V00 = {vi,0 | 1 ≤ i ≤ n}. A node in V00 can influence at most 2 nodes in V 0 − V00—the other vertices of the triangle its belongs to. Hence, in order to influence all the nodes in V 0 − V00 all nodes in V00 must be spreaders, that is, SpreaderG0 [S00] = V 0. 0 As a consequence, recalling that G is isomorphic to the subgraph of G0 induced by V00, we get SpreaderG[{vi | S0 ∩ Vi0 6= ∅}] = V . tu
We notice that the Target Set Selection problem remains hard when each
node has threshold upper bounded by a constant; in particular, it was proved
in [
In this section we propose an algorithm for the PA problem in case of arbitrary graphs and thresholds. The algorithm PA(G, t), given in Algorithm 1, works greedily by iteratively deprecating nodes from the input graph G unless a certain condition occurs which makes a node be added to the seed set S; it stops when all nodes have either been discarded or selected as seed.
The algorithm maintains five sets of nodes: S that represents the current seed set; U that represents the set of nodes in the surviving graph (i.e., nodes not removed from the initial graph); T emp which is a set of nodes moved into a temporary waiting state (such nodes still belong to U but their neighbors will not count on them for being influenced); R that represents a set of nodes that must become spreaders (but will not do so with the current seed); A is the set of aware nodes (assuming that all the nodes in R will be indeed spreaders).
The algorithm proceeds as follows: As long as there exists at least a non-aware node or there is a node in R, a node v is selected according to a certain function (see Case 3) and is moved into a temporary waiting state, represented by the set T emp. As a consequence of being in T emp, all the neighbors of v will not count on v for being influenced (for each u ∈ N (v) the value δ(u), which denotes the degree of u restricted to the nodes in the U − T emp, is reduced by 1).
Due to this update, some nodes in the surviving graph may remain with less “usable” neighbors (if a node v ∈/ A has δ(v) = 0 or v ∈ R has δ(v) < t(v)); in such a case (see Case 2) the nodes are added to the seed set and removed from the graph, while the thresholds of their neighbors are decreased by 1 (since they receive v’s influence).
If (see Case 1) the surviving graph contains a node v whose threshold has been decreased down to 0 (which means that the nodes which have been already added to the seed set S – see Case 2 – suffice to make v a spreader), v is deleted from the graph and the thresholds of its neighbors are decreased by 1 (since once v becomes a spreader, they will receive its influence). Notice that Case 1 can also apply to nodes in T emp.
Algorithm 1: PA(G, t) //G = (V, E) is a graph with thresholds t(v) for v ∈ V 1 S = ∅; T emp = ∅; U = V ; R = ∅; A = ∅; 2 foreach v ∈ V do 3 k(v) = t(v); 4 δ(v) = |N (v)|; 5 while A 6= V OR R 6= ∅ do 6 if ∃v ∈ U s.t. k(v) = 0 then // Case 1): v is a spreader, thanks to its neighbors outside U 7 foreach u ∈ N (v) ∩ U do 8 k(u) = max(k(u) − 1, 0); A = A ∪ {u}; 9 if v ∈/ T emp then δ(u) = δ(u) − 1;
U = U − {v};
R = R − {v};
A = A ∪ {v}; else if ∃v ∈ (U −T emp) ∩ R s.t. δ(v)<k(v) OR ∃v ∈/ A s.t. δ(v) = 0 then
S = S ∪ {v}; foreach u ∈ N (v) ∩ U do k(u) = k(u) − 1; δ(u) = δ(u) − 1; U = U − {v};
R = R − {v}; else if U − T emp − R 6= ∅ then temporary repository
// Case 2): v must be a seed A = A ∪ {v};
// Case 3): v is moved in the v = argminw∈U−T emp−R {δ(w)} if v ∈/ A then
R = R ∪ {u} where u = argmaxw∈N(v)∩(U−T emp){δ(w)} foreach z ∈ N (u) ∩ U do A = A ∪ {z}; else
n k(w) o v = argmaxw∈R δ(w)(δ(w)+1) ; foreach u ∈ N (v) ∩ U do δ(u) = δ(u) − 1;
T emp = T emp ∪ {v}; R = R − {v}; A = A ∪ {v}; In such a case the value of δ() of the neighbors of the selected node v were already reduced by 1—when v moved to T emp—and, therefore, it is not reduced further. By construction, once a node is moved to T emp, then it will be removed from the graph only by Case 1; indeed, Case 2 and 3 only apply to nodes outside T emp. In other words, nodes moved to T emp will never belong to the seed set.
When Case 3 applies the idea is to identify nodes that will never belong to
the initial seed set. Two cases are considered, if the surviving graph still contains
nodes which do not belong to the set R, then one of such nodes having minimum
δ() is moved to the set T emp. Otherwise all the nodes in the surviving graph
must spread and the choice of the node to be deprecated is made according to a
metric first studied in [
Example 1. Let G be a complete graph, the algorithm PA(G, t) optimally returns a single seed: At the first iteration of the while loop, Case 3) applies and a node v1 is selected; then a node v2 is marked as required while all the others—being neighbors of v2—are marked aware; during the successive iterations, |V |−t(v2)−1 nodes are removed from U ; finally Case 2) holds for v2 which is added to S and the algorithm returns S = {v2}.
In the rest of the paper, we use the following notation. We denote by n the number of nodes in G, that is, n = |V | and by λ the number of iterations of the while loop of algorithm PA(G, t). Given a subset V 0 ⊆ V of vertices of G, we denote by G[V 0] the subgraph of G induced by nodes in V 0. Moreover, with respect to the iterations of the while loop in PA(G, t), for each i = 1, . . . , λ we denote: – by vi the node selected during the i-th iteration; – by Ui, T empi, Si, Ri, Ai, δi(u), and ki(u), the sets U, T emp, S, R, A and the values of δ(u), k(u), respectively, as updated at the beginning of the i-th iteration.
When i = 1, the above values are those of the input graph G, that is: U1 = V , G[U1] = G, δ1(v) = |N (v)| and k1(v) = t(v), for each node v of G.
The following properties will be useful for the algorithm analysis. Fact 1 For each iteration i of the while loop in PA(G, t),
1. V − Ui ⊆ Ai 2. T empi ⊆ Ai 3. Ri ⊆ Ui − T empi Fact 2 For each iteration i of the while loop in PA(G, t) and u ∈ Ui, it holds δi(u) = |N (u) ∩ (Ui − T empi)| Lemma 1. Algorithm PA(G, t) executes at most 2n iterations of the while loop (i.e., λ ≤ 2n).
Proof. First of all we prove that, at each iteration i ≥ 1 of the while loop of PA(G, t), a node vi ∈ Ui is selected. If Ri = ∅ then Ai 6= V (otherwise the algorithm terminates). Since by 1. of Fact 1 V − Ui ⊆ Ai we have that there exist u ∈ Ui such that u ∈/ Ai. Then using 2. of Fact 1 we have that u ∈/ T empi and consequently Ui − T empi − Ri 6= ∅. Hence a node is selected by Case 1 or by Case 2 or at line 20 of the algorithm. Otherwise (Ri 6= ∅) and a node is selected by Case 1 or by Case 2 or at line 25 of the algorithm. We conclude the proof noticing each v ∈ V can be selected at most twice: Once v is eventually inserted in T emp (if Case 3 applies) and once v is removed from U (if either Case 1 or Case 2 apply). Indeed by 3. of Fact 1, Case 3 only applies to nodes in Ui − T empi. Theorem 2. For any graph G = (V, E) and threshold function t(·), the algorithm P A(G,t) returns a perfect seed set for G in O(|E| log |V |) time.
Proof. In order to show that the set S provided by the algorithm P A(G,t) is a perfect seed set for G, we first show that for each i = 1, . . . , λ the set Si is able to make all the nodes in
λ Ri = [(Ri ∪ {u ∈/ Ai such that δi(u) = 0})
j=i a spreader, that is Ri ⊆ SpreaderG[Ui][Si]. We show it by induction with i going from λ back to 1.
Consider first i = λ. Let vλ a node in G[Uλ]. Since λ is the last step and at most one node is removed from R at each step, we have that Rλ = ∅ or Rλ = {vλ} . We distinguish three cases on the selected node vi.
– (Case 1 holds). In this case kλ(vλ) = 0 and vλ is immediately spreader in
G[Uλ] and the statement is clearly satisfied. – (Case 2 holds). In this case (Rλ = {vλ} and kλ(vλ) > δλ(vλ)) or (vλ ∈/ Aλ and δλ(vλ) = 0) and consequently Sλ = {vλ} and Rλ ⊆ SpreaderG[Uλ][Sλ]. – Finally we show that case 3 cannot hold at the last iteration of the algorithm.
Indeed if Rλ = ∅ then vλ ∈/ Aλ (otherwise the algorithm cannot terminate at round λ). In this case a new node is added to R at the line 22 of the algorithm and the algorithm cannot terminate at round λ. We notice that this node must exists, otherwise δλ(vλ) = 0 and Case 2 holds. On the other hand, if Rλ = {vλ} then Uλ − T empλ − Rλ = ∅ and we have Uλ − T empλ = {vλ} and consequently δλ(vλ) = 0. Since we are in case tree we also know that kλ(vλ) > 0 and Case 2 holds.
Consider now i < λ and suppose the algorithm be correct on G[Ui+1], that is, Ri+1 ⊆ SpreaderG[Ui+1][Si+1]. We show that the algorithm is correct on G[Ui] with thresholds ki(u) for u ∈ Ui.
By the algorithm PA, for each u ∈ Ui we have ki+1(u)= (max(ki(u)−1, 0) if Case 1 or 2 hold and u ∈ N (vi) ∩ Ui ki(u) otherwise, (1) where vi is the node selected at iteration i.
We distinguish three cases on the selected node vi. – (Case 3 holds). In this case Ui = Ui+1 and Si+1 = Si. Moreover by (1), ki+1(u) = ki(u) for each u ∈ Ui+1. If vi ∈/ Ri then Ri ⊆ Ri+1 and consequently Ri = Ri+1 ⊆ SpreaderG[Ui+1][Si+1] = SpreaderG[Ui][Si].
Otherwise (vi ∈ Ri) we have Ri ⊆ Ri+1 ∪ {vi}, Ui − T empi − Ri = ∅ and by 3. of Fact 1 , we have Ui − T empi = Ri. Hence, (N (v) ∩ (Ui − T empi)) ⊆ Ri+1 (2) Since we are in Case 3 and vi ∈ Ri then δi(v) ≥ ki(v). Using this, Fact 2 and equation (2), we have that since Ri+1 ⊆ SpreaderG[Ui+1][Si+1] then Si+1 = Si is able to make vi a spreader in G[Ui] and we have Ri ⊆ SpreaderG[Ui][Si]. – (Case 2 holds). In this case Ui+1 = Ui − {vi}, Ri ⊆ Ri+1 ∪ {vi} and Si = Si+1 ∪ {vi}. Hence vi ∈ Spreader[Si]. Moreover by (1), it follows that for any u ∈ N (vi) ∩ Ui, if u ∈ Spreader[Si+1] then u ∈ Spreader[Si]. Hence Ri ⊆ Spreader[Si]. – (Case 1 holds). In this case we have ki(vi) = 0, Ui+1 = Ui −{vi}, Ri ⊆ Ri+1 ∪ {vi} and Si = Si+1. Since ki(vi) = 0, node vi is immediately spreader in G[Ui]. Hence by (1), each neighbor u of vi in G[Ui] is influenced by vi and its threshold is updated according to (1). Therefore, since Ri+1 ⊆ SpreaderG[Ui+1][Si+1], we have that Ri ⊆ SpreaderG[Ui][Si].
The statement follows since G[U1] = G.
The theorem follows by observing that a node is moved to the set A only if (v ∪ N (v)) ∩ R1 6= ∅ and that the algorithm terminates when all nodes are aware (A = V ) and the set R is empty.
The PA algorithm can be implemented to run in O(|E| log |V |) time. Indeed we need to process the nodes v ∈ V —each one at most two times (see Lemma 1)—according to the metrics δ(v) and k(v)/(δ(v)(δ(v) + 1)), and the updates, that follows each processed node v ∈ V involve at most |N (v)| neighbors of v. 4
Due to Theorem 1, we cannot aim to any significant performance guaranteed on the seed set size for general graphs and threshold functions. Nonetheless, extensive experiments show that our algorithm performs very well on large real networks, both in terms of efficiency of the solution and of the running time.
We conducted experiments on 12 real networks of various sizes from the
Stanford Large Network Data set Collection (SNAP) [
The active information diffusion problem is a novel model of information
diffusion and, to the best of our knowledge, no heuristic is known for the PA
problem. For this reason we decided to evaluate the effectiveness of our algorithm
(PA) with two heuristics that respectively solve two problems related to the PA
# of nodes # of edges
Name
BlogCatalog3 [
78
6594
problem. The first heuristic, named MTS [
The rationale of this comparison is to show that by relaxing the goal of the TSS model for the new model (which only aims to make each node aware) we are able to identify significantly smaller seed sets.
On the other hand, when all the thresholds t(v) are equal to the node degrees
d(v), the PA problem is equivalent to the well known Dominating Set problem.
For this reason we will compare our algorithm with the (best known) heuristic
[
Thresholds values. We tested the three algorithms using two categories of threshold function: – Random thresholds where t(v) is chosen uniformly at random in the interval [1, d(v)]. Since the random thresholds test settings involve some randomization, we executed each test 10 times. The results were compared using means of target set sizes (the observed variance was negligible); – Proportional thresholds, where for each v the threshold t(v) is set as α × d(v) with α = 0.1, 0.2, . . . , 1. Notice that for α = 0.5 we are considering a particular version of the activation process named “majority” thresholds, while for α = 1 we are considering the D o m i n at i n g S e t problem. 4.1
Random Thresholds. Table 2 depicts the results of the Random threshold test setting. Each number represents the average size of the perfect seed set generated by PA and MTS algorithms on each network using random thresholds (for each test setting, the same thresholds values have been used for both the algorithms). The
Name PA MTS BlogCatalog3 10 12 (20%) Ca-AstroPh 919 1157 (25.9%) Ca-CondMath 1573 1810 (15.07%) Ca-GrQc 636 661 (3.93%) Ca-HepPh 790 901 (14.05%) Ca-HepTh 964 945 (-1.97%) Cit-HepTh 955 1045 (9.42%) Douban 2374 2343 (-1.31%) Facebook 9 213 (2267%) Jazz 4 7 (75%) Karate 3 3 (0%)
Power grid 352 340 (-3.41%) value in bracket represents the overhead percentage of MTS algorithm compared to the PA algorithm.
Constant and Proportional thresholds. Figures 1 and 2 report the results for the proportional thresholds settings. For each network the plot depicts the size of the perfect seed set (Y-axis), for each value of α ∈ [0.1, 1] (X-axis) and for each algorithm (series). We present the results only for 4 networks because of space limits; the experiments performed on the other networks exhibit similar behaviors.
The results in Fig. 1 and 2 confirm our hypothesis. The size of the initial seed set provided by our PA algorithm is in general significantly smaller than the size of the set provided by the other strategies. We notice that the gap between the PA and the MTS algorithms increase with the value of the node thresholds (this result was expected: the larger the value of t(), the larger the difference between the models). The PA algorithm is always better than the DOM algorithm, when t(v) < d(v). Moreover when t(v) = d(v) (that is, when the PA problems becomes the Dominating Set Problem), the two algorithms provide comparable results, hence the PA algorithm could be considered as an effective alternative heuristics for the dominating set problem. 5
Let T = (V, E) be a tree rooted at any node r, and let T (v) the subtree rooted at v, for any v ∈ V . We can prove that the algorithm PA outputs an optimal perfect seed set whenever the input graph is a tree.
Theorem 3. PA(T, t) returns an optimal perfect seed set for any tree T . If T is the tree in Fig. 3 one can see that the algorithm PA(T, t) returns a optimal seed set—consisting of the three double-circled nodes in the figure.
In order to evaluate the time complexity for trees, we report as TREE-PA the rewriting of the general PA algorithm in Section 3 in case the input graph is known to be a tree. One can see that the algorithm essentially computes the seed set while performing a visit (in BFS reverse order) of the tree. We can then show that Theorem 4. The PA problem can be solved in linear time for any tree.
TREE-PA(T , t), T = (V, E) is a tree with thresholds t(v) for
if v = r AND t(v) > 0 AND v ∈/ A − P then S = S ∪ {v} 16 return S 6
We have studied some algorithmic aspects of a recently introduced information
diffusion model, that differentiates among spreaders and aware nodes [