Multiple benefit thresholds problem in online social networks: An algorithmic approach

  Citation: Pham, P.N.H.; Nguyen, B.-N.T.; Co, Q.T.N.; Snášel, V. Multiple Benefit Thresholds Problem in Online Social Networks: An Algorithmic Approach. Mathematics 2022,10, 876. https://doi.org/ 10.3390/math10060876 Academic Editors: Gaogao Dong and Jianguo Liu Received: 16 December 2021 Accepted: 4 March 2022 Published: 9 March 2022 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Copyright: © 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). mathematics Article Multiple Benefit Thresholds Problem in Online Social Networks: An Algorithmic Approach Phuong N. H. Pham 1,2,* , Bich-Ngan T. Nguyen 1,2 , Quy T. N. Co 1and Václav Snášel 2 1Faculty of Information Technology, Ho Chi Minh City University of Food Industry, 140 Le Trong Tan Street, Ho Chi Minh 700000, Vietnam; [email protected] (B.-N.T.N.); [email protected] (Q.T.N.C.) 2Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VŠB-Technical University of Ostrava, 17.listopadu 15/2172, 708 33 Ostrava, Czech Republic; vaclav[email protected] *Correspondence: [email protected] Abstract: An important problem in the context of viral marketing in social networks is the Influence Threshold (IT) problem, which aims at finding some users (referred to as a seed set) to begin the process of disseminating their product’s information so that the benefit gained exceeds a predetermined threshold. Even though, marketing strategies exhibit different in several realistic scenarios due to market dependence or budget constraints. As a consequence, picking a seed set for a specific threshold is not enough to come up with an effective solution. To address the disadvantages of previous works with a new approach, we study the Multiple Benefit Thresholds (MBT), a generalized version of the IT problem, as a result of this phenomenon. Given a social network that is subjected to information distribution and a set of thresholds, T={T1 , T2 , . . . , Tk} , Ti> 0, the issue aims to seek the seed sets S1 , S2 , . . . , Sk with the lowest possible cost so that the benefit achieved from the influence process is at the very least T1 , T2 , . . . , Tk , respectively. The main challenges of this problem are a #NP-hard problem and the estimation of the objective function #P-Hard under traditional information propagation models. In addition, adapting the exist algorithms many times to different thresholds can lead to large computational costs. To address the abovementioned challenges, we introduced Efficient Sampling for Selecting Multiple Seed Sets, an efficient technique with theoretical guarantees (ESSM). At the core of our algorithm, we developed a novel algorithmic framework that (1) can use the solution to a smaller threshold to find that of larger ones and (2) can leverage existing samples with the current solution to find that of larger ones. The extensive experiments on several real social networks were conducted in order to show the effectiveness and performance of our algorithm compared with current ones. The results indicated that our algorithm outperformed other state-of-the-art ones in terms of both the total cost and running time. Keywords: social network; viral marketing; information diffusion; approximation algorithm MSC: 68W25; 68R05; 90C27 1. Introduction In recent years, there has been a rapid development of the global economy thanks to the contribution of the Online Social Network (OSN), based on the provision of a powerful platform for communication and information dissemination in the field of marketing, media, and advertising, particularly in social networks with billions of users. The strong underpinnings of problems of social influences in OSNs are information diffusion models. Kempe et al. [ 1 ] first introduced two classic models, named Independent Cascade (IC) and Linear Threshold (LT), and formulated the Influence Maximization (IM) problem, which aims to select k nodes that may impact the largest number of users a social network. This work has inspired many studies on social influence [ 2 – 10 ], misinformation/rumors detection, and control [11–15]. Mathematics 2022,10, 876. https://doi.org/10.3390/math10060876 https://www.mdpi.com/journal/mathematics Mathematics 2022,10, 876 2 of 18 In the context of viral marketing for product promotion, hosts (companies) often devise a marketing campaign including the distribution of product samples to selected users and expect that they persuade their friends, friends of friends, etc. The number of people who have been impacted reaches a certain level. Influence Threshold (IT) was inspired by this phenomenon and a slew of research backed it up; it looks for a node set with the smallest size possible so that the number of impacted nodes reaches or surpasses a predetermined threshold γ [ 8 , 16 , 17 ]. The value of γ can determine the scale of of the viral marketing. However, in some realistic scenarios, there is a distinct cost to persuade a user who promotes a sample product [ 4 , 18 ]. Besides, each influenced user often offers a different benefit when one is influenced after the marketing process. Customers with significant financial resources, for example, will be able to purchase more things than others. As a result, the existing algorithms for IT problem may offer an inaccurate solution of a marketing purpose. Moreover, the marketing strategies are often adjusted since the market can vary in a short time. Consequently, a particular solution for a benefit is insufficient to be the overall effective solution. This can be overcome by finding solutions for multiple thresholds and selecting the best one that suits their budget and current market. For instance, assume that a company wants to come up with a strategy that can influence customers on an online social network. Nonetheless, or due to budget fluctuations or the instability of the market, they may consider strategies of spreading with the different number of influenced customers such as 1000, 2000, 3000, 5000, etc. In this case, the company wants to find solutions, where the benefit function of each is above the corresponding threshold and then that company can select a solution with a reasonable cost so as to execute its marketing plan well. Our goal in this study is to develop an answer to a novel Multiple Benefit Thresholds (MBT) problem, which is expressed as follows. For a social network G= (V , E) given a set of k benefit thresholds T={T1 , T2 , . . . , Tk} , each user u has a distinct cost price c(u)> 0. The issue is to seek for the various seed sets {S1 , S2 , . . . , Sk} , in which each Si has the cheapest total cost c(Si) by a result of each seed set’s earned benefit Si , characterized by B(Si) , and is at least Ti for i= 1 . . . , k . There are two main challenges for solving MBT problem. First ones are to find MBT as #NP-Hard and to calculate the benefit function #P-Hard. Secondly, finding numerous seed sets for multiple thresholds needs more time and memory than other information propagation challenges, as well as the IT problem. It is necessary to run the existing algorithms for a single threshold k times to prove it is costly and, hence, not applicable to large networks. To overcome the challenges, in this paper, we propose a highly efficient algorithm to solve the problem. This not only guarantees a solution but also produces good results in practice. This work revised and extended the our conference paper [19] by providing all the proofs more detail and experiment evaluation. The following is a list of our contributions as a whole: • The Multiple Benefit Thresholds (MBT) is first formulated with the Independent Cascade (IC) information diffusion model. • With a view to developing the solution, the Efficient Sampling for Multiple Seed Set Selection (ESSM) is proposed, a theoretical approximation algorithm bounds by developing a novel algorithmic framework that utilizes the sample technique to estimate the benefit function, denoted as B(·) , and leverages the seed set and the samples with smaller benefit threshold with the purpose of finding the seed set of the larger ones. Accordingly, our algorithm can find multiple seed sets in only one run. For solution guarantee, our algorithm returns multiple seed sets Si satisfying B(Si)≥1−e 1+eTi−e and the total cost c(Si)≤( 1 +ln (Ti−eTi) e)c(S∗ i) a strong possibility (w.h.p), where e> 0 is an input and S∗ i is the best seed set in terms of threshold Ti for all i=1, 2, . . . , k. • Extensive experiments on six real-world networks are performed, including Gnutella, Email-Enron, Net-Hept, Net-Phy, Amazon, and DBLP for the comparison of the efficiency between our algorithm and other state-of-the-art ones. The results of experi- Mathematics 2022,10, 876 3 of 18 ments indicated that our algorithm outperformed the state-of-the-art ones in respect of both the cost and the running time. Organization. The rest of the paper is structured as follows. In Section 2, we review previous relevant works of influence maximization. Section 3presents the model, problem definition, and main algorithm. The experiment results are shown and explained in Section 4. Finally, Section 5brings the paper to the conclusion. 2. Related Works In this section, we review previous studies related to our abovementioned problem, including Information propagation models, Influence Maximization, and Influence Threshold. Information propagation models and Influence Maximization. Social networks provide a convenient environment for business marketing through the word-of-mouth effect. Influence Maximization (IM) [ 1 ], which seeks out k nodes (seed set) in a social network that can influence the greatest number of nodes is one of the most important challenges in social network influence. Kempe et al. originally investigated IM as an #NP-hard combinatorial optimization under two famous information diffusion models: Linear Threshold (LT) and Independent Cascade (IC). Furthermore, the challenge of solving IM also coming from calculating the influence function under two above models is #P-hard models—that is, it is impossible to calculate in polynomial time with input size [ 5 , 6 ]. However, due to the enormous application of IM in commerce, several efficient algorithms were proposed for solving the problem in large-scale networks, such as approximation algorithm [1–3,20,21] and heuristics without theoretical guarantee [ 7 , 22 , 23 ]. Notably, Borg et al. [ 24 ] made a theoretical breakthrough by proposing a ( 1 − 1 /e−e) -approximation algorithm in O(e−3kl2(m+n)log2n) with a probability at least 1 −n−l . The main idea of Borg’ algorithm is that they proposed a sample technique, namely, Reverse Reachable (RR) set, to estimate the number of influenced nodes under stochastic information propagation models and an algorithmic framework that finds the solution in generated samples with theoretical bound. Tang et al. [ 2 ] proposed the TIM/TIM++ algorithms reducing the time complexity to O(e−2(k+l)(m+n)log n) while maintaining the performance guarantees and demonstrated the high efficiency of their algorithm in billion-scale networks. Later on, several algorithms have been devised in an attempt to reduce the sample complexity and running time but they still maintained an approximate ratio by modifying the RIS framework, including IMM [ 3 ], SSA/DSSA [ 21 ], OPIM [ 25 ], etc. Recently, Akram et al. mentioned finding influential communities in a social network with fuzzy competition hypergraphs notion [26,27]. In other directions, numerous studies were carried out on variations of IM for many scenarios of viral marketing. The authors in [ 28 – 30 ] considered IM under topic queries by introducing the information diffusion model that can enable many topics to spread. Additionally, the advance in geoposition enabled devices and services makes OSNs able to integrate a user’s location. The authors in [ 31 ] investigated the location-aware influence maximization (LIM) problem in which some nodes were selected and the largest number of nodes was influenced in a given distance; [ 32 ] considered the role of distance among users to promote the influence process of viral marketing. Moreover, several other variations of IM including competitive-aware [ 5 , 33 ] and time-aware [ 34 ] have been introduced and studied. Recently, Nguyen et al. [ 35 ] has studied IM under the budget constraint where each node has the limited cost to adopt a sample product and the total budget was required. In the seminal paper, it showed that the greedy algorithm can achieve an approximation ratio of 1 − 1 /√e and further proposed efficient heuristic algorithms without any performance guarantees. Later, Nguyen et al. [ 4 ] studied the Cost-aware Targeted Viral Marketing (CTVM) problem, a generalization of IM. In this problem, each node u has an arbitrary cost c(u) and a benefit b(u) . The goal of CTVM was to select a seed set within a given budget B so that the total benefit was maximized. They proposed a benefit sampling technique and a 1 −1 √e−e approximation algorithm with probability at least 1 −δ in O(e−2nlog((n k))/δ) . In this study, the sampling technique in [ 4 ] is adapted to estimate the benefit function. Mathematics 2022,10, 876 4 of 18 However, BCT could not adapt to solving our problem due to the difference between MBT and CTVM. Influence Threshold. Influence Threshold (IT), which seeks the smallest size seed set S such that the influence spread, defined as σ(S) , is at least a specified threshold γ , is the problem that comes closest to ours. Goyal et al. [ 36 ] were the first to investigate the IT problem using IC models. Using the influence function’s monotone submodular characteristic, they proposed a greedy algorithm combining with Monte Carlo simulation method [ 1 ] to estimate σ(S) . The algorithm returns a seed set S satisfying σ(S)≥γ−e and |S|≤|S∗|·( 1 +ln γ e) in O(n2R) time complexity, where e> 0 is an input, S∗ is the optimal solution, and R is number of Monte Carlo simulations with setting R= 10.000. Due to its high time complexity, it is difficult to apply this algorithm to large networks. By utilizing the sampling technique method in [ 37 ], Kuhnle et al. [ 8 ] developed a ( 1 − 2 α ,1 + 4 αγ +log γ) — bicriteria approximation algorithm for a special case of IT where cost of the vertices is the same (We call an algorithm is an (α , β) -bicriteria approximation for IT problem if it returns a solution S satisfying σ(S)≥α·T and |S| ≤ β·|S∗| , where α , β> 0 and S∗ is the optimal solution.) in O(α2(m+n)log(n)|S|) time complexity, where α∈( 0,1 ) is an input and n , m refer to the number of nodes, edges in the network. The authors of [ 17 ] recently explored IT in a noisy model resembling a real-world situation, where we only estimate the influence spread function within an error bound. The greedy algorithm under noise with theoretical bound was proposed but it retained time complexity as in [ 38 ]. In these studies, they ignored the point that each affected user provided a different benefit in these experiments. The benefits of the nodes and different benefit thresholds are considered for identifying the appropriate seed sets in our MBT problem. In the case of the great similarity in benefits of nodes, the above algorithms can be used for each threshold Ti , but it is imperative to run k times to find the k seed sets. On the other hand, our proposed algorithm not only provides theoretical bounds but also returns multiple seed sets for set of benefit thresholds at a single time. 3. Methodology In this section, Independent Cascade (IC) model is presented, as the well-known original model related to the IM problems. [ 1 – 4 , 20 , 21 ]. Our notations and symbols are summarized in Table 1. Table 1. Table of symbols. Notional Description n,mThe number of nodes and of edges in G, respectively Nin(v),Nout(v)The incoming and outgoing neighbor node set of v. SiThe solution returned by our algorithm for threshold Ti B(S),ˆ B(S)Define the benefit function and an estimation of benefit function Γ Γ =∑u∈Vb(u) S∗ iThe optimal seed set for threshold Ti N(i,j)N(i,j) = (2+2 3e)Γ e2(Ti−eTi)ln((n j)/δ) Ni max Ni max =maxj:1...|Si| (2+2 3e)Γ e2(Ti−eTi)ln((n j)/δ) imax imax =argmaxi=1...|Sk|ln((n i)) 3.1. Independent Cascade Model In this work, a social network is abstracted by a directed graph G= (V , E) . V and E represent the set of users and the set of links in the network, respectively. In this model, each edge e= (u , v)∈E has a probability p(u , v)∈( 0,1 ) representing the influence transmission from u to v . Given a seed set S⊆V , each node is in one of two states: active and inactive, which reflects whether it is influenced by the seed set or not. The diffusion process starts from Sand works as follows: • At the beginning (step t=0), all nodes in the seed set are active. Mathematics 2022,10, 876 5 of 18 • At the next steps (step t≥ 1), an node u , which is activated in previous steps, has a single chance to influence each of its neighbors v with the probability of success p(u,v). • All active nodes retain their status until the end of the diffusion process, and the process ends at step tif there is no new activated node in this step. Kempe et al. [ 1 ] showed that the IC model was equivalent to sample graph model, defined as follows. The live-edge model first generates a sample graph g= (Eg , Vg) by selecting e= (u , v)∈E with probability p(e) = p(u , v) and not selecting e= (u , v)∈E with probability 1 −p(u,v). The sample graph gis generated with probability Pr[g/G] = ∏ e∈Eg p(e)·∏ e∈E\Eg (1−p(e)) (1) In our model setting, we will gain a benefit b(u)>= 0 if the node u becomes active, as in [ 4 ]. Benefit function B(S) , denoted as the total benefit over all influenced nodes, is calculated as follows: B(S) = ∑ g/G Pr[g/G]∑ u∈R(g,S) b(u)(2) where R(g , S) is the set of nodes that can reach from any node in S in graph g . In additional, each node u∈V has a cost c(u)> 0, which we have to pay to user u to initiate the influence process from u and c(S) = ∑u∈Sc(u). 3.2. Problem Definition We formally introduce our studied problem, Multiple Benefit Thresholds (MBT), as follows: Definition 1 (MBT) . Given a graph G= (V , E) under the IC model and the set of benefit thresholds T={T1 , T2 , . . . , Tk} . For each Ti∈T , the problem is required to find Si∈V with smallest cost c(Si)so that B(Si)≥Ti. In the case when b(u) = 1, ∀u∈V , the benefit function B(·) becomes the influence spread function [ 1 ]. Ref. [ 6 ] showed that it was #P-hard to compute the number of influence nodes (influence spread function) exactly, so calculating B(·) was also #P-hard. Besides, the IT problem [ 8 , 17 , 38 ], a special case of MBT problem with b(u) = c(u) = 1, ∀u∈V and k=1, is NP-hard, which implies that MBT is also #NP-hard. 3.3. Our Proposed Algorithm In this section, the Efficient Sampling for Selecting Multiple seed sets (ESSM), an efficient algorithm for MBT problem with theoretical guarantee, is introduced. Our novel technique is to develop a method that combines two following ideas: (1) finds the candidate seed set for each threshold via the benefit sampling; (2) uses the seed set with a smaller threshold for finding the seed sets with bigger ones, which can improve the running time as well as memory usage. Moreover, the sampling technique with martingale theory is in use to estimate the benefit function effectively. 3.3.1. Benefit Sampling We first recap the concept of Benefit Sample (BS) in [4] to estimate the B(·). Definition 2 (Benefit Sample) . A BS is generated from G= (V , E) under the IC model by following steps: (1) Choose a source node u with probability b(u) Γ , (2) create a sample graph g from G, and (3) return Rjas the set of nodes that can reach node u in g. The Algorithm 1in [4] can be used to generate a BS for IC model. Mathematics 2022,10, 876 6 of 18 Algorithm 1: An algorithm for generating a BS under the IC model. Input: Graph G= (V,E)under IC model Output: A BS set Rj 1: Choose a source node uwith probability b(u) Γ 2: Initialize a queue Q={u}and Rj={u} 3: while Qis not empty do 4: v←Q.pop() 5: for u∈Nin(v)\(Rj∪Q)do 6: With probability p(u,v)do: Q.push(u),Rj←Rj∪{u}; 7: end for 8: end while 9: return Rj Given R is a collection of BSes, a seed set S , we define a random variable Xj(S) as follows: Xj(S) = (1, If Rj∩S6=∅ 0,Otherwise (3) We can estimate the benefit function B(S)by the following Lemma in [4]. Lemma 1 (Lemma 2, [4]).For any set of nodes S ⊆V, we have: B(S) = Γ·E[Xj(S)] The function B(·) is monotone and submodular [ 4 ], i.e., for any S⊆T⊆V , and v/∈T , we have B(T)≥B(S)(4) B(S+{v})−B(S)≥B(T+{v})−B(T)(5) We can calculate an estimation ˆ B(S)of B(S)via a collection Rof BSes as follows: ˆ B(S) = Γ |R| ∑ Rj∈R Xj(S)(6) It can be seen that Xj(S)∈[ 0,1 ] . We define a random variable Yi=∑i j=1(Xj(S)−µ) , ∀i≥1, where µ=E[Xj]and a sequence random variables Y1,Y2, . . ., we have E[Yi|Y1, . . . , Yj−1] = E[Yi−1] + E[Yi(S)−µ] = E[Yi−1] Therefore, Y1 , Y2 , . . . areaformofmartingale[ 39 ]. Thus, wehave the following Lemma[ 39 ]. Lemma 2 ([39]).Given a collection Rwith T =|R| and λ>0, we have Pr hT ∑ j=1 Xj(S)−T·µ≥λi≤exp(−λ2 2λ2 3+µT)(7) Pr hT ∑ j=1 Xj(S)−T·µ≤ −λi≤exp−λ2 2µT(8) Mathematics 2022,10, 876 7 of 18 Let λ=eTµin Lemma 2, we obtain Pr[ˆ B(S)≥(1+e)B(S)] ≤exp(−e2µT 2+2 3e)(9) Pr[ˆ B(S)≤(1−e)B(S)] ≤exp−e2µT 2(10) If the number of BSs is at least T≥( 2 +2 3)1 µ1 e2ln(1 δ) for δ∈( 0,1 ) , ˆ BR(S) is an (e,δ)-approximation of B(S), i.e., Pr[(1−e)B(S)≤ˆ B(S)≤(1+e)B(S)] ≥1−δ(11) The characteristics of the martingale sequence play an important role in devising our algorithm in the next subsection. 3.3.2. ESSM Algorithm Our proposed algorithm is now described. On a high level, our algorithm combines two methods: (1) We provide a (δ , e) -approximation of the benefit function via martingale theory. (2) In each iteration, we propose the algorithmic framework that finds some candidate seed sets for a threshold and then choose the final seed set, which guarantees the solution quality by checking static evidence. (3) We reuse the seed set for smaller threshold for finding the seed sets with the larger threshold. Our proposed algorithm is presented in Algorithm 2. Algorithm 2: ESSM algorithm. Input: A graph G= (V,E),T={T1, . . . , Tk},e,δ∈(0,1) Output: S1,S2, . . . , Sk 1: Generate R0containing (2+2 3e)Γ e2(Ti−eTi)(ln n+ln(1/δ)) BSs by using Algorithm 1 2: S0←∅ 3: for i=1 to kdo 4: Ri← Ri−1 5: Si←Si−1 6: Calculate ˆ B(Si)by Equation (6) 7: while ˆ B(Si)<Ti−eTi−edo 8: u←argmaxv∈V\Si min(ˆ B(Si∪v),Ti−eTi−e)−ˆ B(Si) c(v) 9: Si←Si∪{u} 10: j← |Si| 11: N(i,j)←(2+2 3e)Γ e2(Ti−eTi)ln((n j)/δ) 12: if |Ri|<N(i,j)then 13: Generate more N(i,j)−|Ri|BSs and add them into Ri 14: N←N(i,j) 15: Si←∅ 16: end if 17: end while 18: end for 19: return S1,S2, . . . , Sk At the beginning of the algorithm, it generates collection R0 that contains (2+2 3e)Γ e2(Ti−eTi)(ln n+ln(1/δ)) BSs by using Algorithm 1and initiates a seed set S1as empty. At each iteration i of first loop (line 3–18), it finds the seed set with respect to threshold Ti . Denote f(Si) = min(ˆ B(Si) , Ti−eTi−e) . At each iteration of the second loop (line 7–18), the algorithm finds a seed Si , by iteratively selecting a node u with maximum marginal of Mathematics 2022,10, 876 8 of 18 the estimation function f as per its cost, i.e., (f(Si∪{u})−f(Si))/c(v) and (2) checking the condition of the number of samples (line 12). If the number of samples is sufficient to give an (δ , e) -approximation (by Lemma 3), the algorithm moves into next iterations and keeps current seed set Si ; otherwise, the algorithm generates more samples (line 13) so that the number of samples is N(i , j) and adds them into Ri . In this case, the seed set Si is suitable for new collection Ri . The second loop terminates when it satisfies the condition ˆ B(Si)≥Ti−eTi−e . Next, the algorithm reuses the current samples and seed set to find the seed set for larger threshold (lines 4–5) by using similar steps with previous iteration. The theoretical bounds of the algorithm are now analyzed. Firstly, the satisfactory number of BSes is provided to estimate B(·)is shown in Lemma 3. Lemma 3. If |R| ≥ (2+2 3e)Γ e2(Ti−eTi)(ln n+ln 1 δ)then Pr[ˆ B(S∗ i)≥Ti−Tie]≥1−δ Proof. Denote µ=B(S∗ i)/Γ,ˆ µ=ˆ B(S∗ i)/Γ, we have Pr[ˆ B(S∗ i)≤Ti−Tie]≤Pr[ˆ B(S∗ i)≤(1−e)B(S∗ i)] =Pr[ˆ µ≤(1−e)µ](By applying (10)) ≤exp−e2|R|µ 2 ≤exp−e2|R|ˆ µ 2(1−e)(Due to µ≥ˆ µ/(1−e)) ≤exp −(2+2 3e)ˆ B(S∗ i) 2(1−e)(Ti−eTi)ln 1 δ!≤δ which implies the proof. The theoretical guarantee of Algorithm 2is stated as follows. Theorem 1. For any inputs e , δ∈( 0,1 ) , the Algorithm 2returns a set of seed sets S= {S1,S2, . . . , Sk}satisfying (a) Pr[c(Si)≤(1+ln Ti−eTi e)c(S∗ i)] ≥1−δ/n. (b) PrB(Si)≥Ti·1−e 1+e−e≥1−δ. Proof. At any i -th iterator of the first loop (line 3 to 19) in Algorithm 2, denote Si=St i={s1 i , s2 i , . . . , st i} as the solution of algorithm with respect to the threshold Ti , and Pi={vi 1 , vi 2 , . . . , vi l} as a set of nodes with minimum cost satisfying ˆ B(Pi)≥Ti−eTi and Ci=c(Pi) . Due to the checking condition in line 12, the number of BSes at the end of iteration iobtains at least Ni min =(2+2 3e)Γ e2(Ti−eTi)ln(n |Si|/δ)(12) and obtains at most, Ni max =max j:1...|Si| (2+2 3e)Γ e2(Ti−eTi)ln(n j/δ)(13) Mathematics 2022,10, 876 9 of 18 Prove (a) As ˆ B(·)is submodular, we have Ti−eTi−ˆ B(St−1 i)) ≤ˆ B(Pi)−ˆ B(St−1 i)) ≤ˆ B(Pi∪St−1 i)−ˆ B(St−1 i)) ≤∑ v∈Pi\St−1 i (ˆ B(St−1 i∪{v})−ˆ B(St−1 i)) ≤Ci c(St−1 i)∑ v∈Pi\St−1 i (ˆ B(St−1 i∪{v})−ˆ B(St−1 i)) For any positive numbers a1, . . . aland b1, . . . , bl. According to [40], we have min i=1...l ai bi≤∑l i=1ai ∑l i=1bi≤max i=1...l ai bi (14) Applying the above inequality, we obtain Ti−eTi−ˆ B(St i)≤Ci c(st i)(ˆ B(St i)−ˆ B(St−1 i)) (15) ≤(1−c(st i) Ci )(Ti−eTi−ˆ B(St−1 i)) (16) ≤e−c(st i) Ci(Ti−eTi−ˆ B(St−1 i)) (17) The (17) condition must satisfy x+1≤ex, for any x>0. Therefore, Ti−eTi−ˆ B(St i)≤e−1 Ci∑t j=1c(st i)(Ti−eTi)(18) =e−1 Cic(St i)(Ti−eTi)(19) By the definition of St i and because Si satisfies the condition in line 7, we have ˆ B(St−1 i)<Ti−eTi−eand ˆ B(St i)≥Ti−eTi−e. Combining with (19), we have (Ti−eTi)e−1 Cic(St−1 i)≥Ti−eTi−ˆ B(St−1 i) >Ti−eTi−(Ti−eTi−e) = e implying that c(St−1 i)<Ciln Ti−eTi e. On the other hand, from (17), we obtain c(st i)≤Ciln Ti−eTi−ˆ B(St−1 i) Ti−eTi−ˆ B(St i)≤1 (20) Thus, c(St i) = c(St−1 i) + c(st i)≤Ci( 1 +ln(Ti−eTi e)) , where Si is the candidate solution for threshold Ti . After i -th iteration of the first loop, |Ri|=N(i , j) = (2+2 3e)Γ e2(Ti−eTi)ln((n j)/δ) . By applying Lemma 3, after iterator i , we have Pr[B(S∗ i)≥Ti−eTi]≥ 1 −δ/(n j) . Combining with the definition of Pi , the following events happen with a probability of at least 1−δ/(n t)≥1−δ/n: c(Si)≤Ci(1+ln(Ti−eTi e)) (21) ≤c(S∗ i)(1+ln(Ti−eTi e)) (22) Mathematics 2022,10, 876 16 of 18 Author Contributions: Conceptualization, P.N.H.P.; methodology, P.N.H.P. and Q.T.N.C.; software, B.-N.T.N.; validation, Q.T.N.C.; formal analysis, B.-N.T.N.; investigation, P.N.H.P.; resources, Q.T.N.C.; writing—original draft preparation, P.N.H.P.; writing—review and editing, P.N.H.P., B.-N.T.N., Q.T.N.C. and V.S.; supervision, V.S.; project administration, P.N.H.P. All authors have read and agreed to the published version of the manuscript. Funding: This research was supported by Ho Chi Minh city University of Food Industry (HUFI). Institutional Review Board Statement: Not applicable. Informed Consent Statement: Not applicable. Data Availability Statement: All real-world social network datasets used in the experiment can be downloaded at http://snap.stanford.edu/data/ (accessed on 15 September 2021). Acknowledgments: This work was supported by Ho Chi Minh City University of Food Industry (HUFI). Conflicts of Interest: The authors declare that there is no conflict of interest. The funders have no role in the research process and the writing of the manuscript. References 1. Kempe, D.; Kleinberg, J.M.; Tardos, É. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 24–27 August 2003; pp. 137–146. [CrossRef] 2. Tang, Y.; Xiao, X.; Shi, Y. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, Snowbird, UT, USA, 22–27 June 2014; pp. 75–86. [CrossRef] 3. Tang, Y.; Shi, Y.; Xiao, X. Influence Maximization in Near-Linear Time: A Martingale Approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia, 31 May–4 June 2015; pp. 1539–1554. [CrossRef] 4. Nguyen, H.T.; Thai, M.T.; Dinh, T.N. A Billion-Scale Approximation Algorithm for Maximizing Benefit in Viral Marketing. IEEE ACM Trans. Netw. 2017,25, 2419–2429. [CrossRef] 5. Chen, W.; Lakshmanan, L.V.S.; Castillo, C. Information and Influence Propagation in Social Networks; Synthesis Lectures on Data Management; Morgan & Claypool Publishers: San Rafael, CA, USA, 2013. [CrossRef] 6. Chen, W.; Wang, C.; Wang, Y. Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 25–28 July 2010; pp. 1029–1038. 7. Chen, W.; Collins, A.; Cummings, R.; Ke, T.; Liu, Z.; Rincón, D.; Sun, X.; Wang, Y.; Wei, W.; Yuan, Y. Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate. In Proceedings of the Eleventh SIAM International Conference on Data Mining, Mesa, AZ, USA, 28–30 April 2011; pp. 379–390. [CrossRef] 8. Kuhnle, A.; Pan, T.; Alim, M.A.; Thai, M.T. Scalable Bicriteria Algorithms for the Threshold Activation Problem in Online Social Networks. In Proceedings of the IEEE Conference on Computer Communications, Atlanta, GA, USA, 1–4 May 2017. [CrossRef] 9. Pham, C.V.; Duong, H.V.; Bui, B.Q.; Thai, M.T. Budgeted Competitive Influence Maximization on Online Social Networks. In Lecture Notes in Computer Science, Proceedings of the Computational Data and Social Networks— 7th International Conference, CSoNet 2018, Shanghai, China, 18–20 December 2018; Chen, X., Sen, A., Li, W.W., Thai, M.T., Eds.; Springer: Cham, Switzerland, 2018; Volume 11280, pp. 13–24. [CrossRef] 10. Pham, C.V.; Thai, M.T.; Ha, D.K.; Ngo, D.Q.; Hoang, H.X. Time-Critical Viral Marketing Strategy with the Competition on Online Social Networks. In Lecture Notes in Computer Science Proceedings of the Computational Social Networks—5th International Conference, CSoNet 2016, Ho Chi Minh City, Vietnam, 2–4 August 2016; Nguyen, H.T., Snásel, V., Eds.; Springer: Cham, Switzerland, 2016; Volume 9795, pp. 111–122. [CrossRef] 11. Pham, C.V.; Dinh, H.M.; Nguyen, H.D.; Xuan, H.H.; Dang, H.T. Limiting the Spread of Epidemics within Time Constraint on Online Social Networks. In Proceedings of the Eight International Symposium on Information and Communication Technology, Nha Trang City, Vietnam, 7–8 December 2017; pp. 262–269. [CrossRef] 12. Pham, C.V.; Phu, Q.V.; Hoang, H.X.; Pei, J.; Thai, M.T. Minimum budget for misinformation blocking in onlinesocial networks. Comb. Optim. 2019,38, 1101–1127. [CrossRef] 13. Budak, C.; Agrawal, D.; El Abbadi, A. Limiting the spread of misinformation in social networks. In Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India, 28 March–1 April 2011; pp. 665–674. [CrossRef] 14. Zhang, H.; Alim, M.A.; Li, X.; Thai, M.T.; Nguyen, H.T. Misinformation in Online Social Networks: Detect Them All with a Limited Budget. ACM Trans. Inf. Syst. 2016,34, 1–24. [CrossRef] 15. Pham, C.V.; Pham, D.V.; Bui, B.Q.; Nguyen, A.V. Minimum budget for misinformation detection in online social networks with provable guarantees. Optim. Lett. 2022,16, 515–544. [CrossRef] Mathematics 2022,10, 876 17 of 18 16. Goyal, A.; Lu, W.; Lakshmanan, L.V. Simpath: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model. In Proceedings of the 11th IEEE International Conference on Data Mining, ICDM 2011, Vancouver, BC, Canada, 11–14 December 2011; pp. 211–220. [CrossRef] 17. Crawford, V.G.; Kuhnle, A.; Thai, M.T. Submodular Cost Submodular Cover with an Approximate Oracle. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Long Beach, CA, USA, 9–15 June 2019; Chaudhuri, K., Salakhutdinov, R., Eds.; PMLR: Mountain View, CA, USA, 2019; Volume 97, pp. 1426–1435. 18. Pham, C.V.; Duong, H.V.; Thai, M.T. Importance Sample-Based Approximation Algorithm for Cost-Aware Targeted Viral Marketing. In Proceedings of the Computational Data and Social Networks—8th International Conference, Ho Chi Minh City, Vietnam, 18–20 November 2019; pp. 120–132. [CrossRef] 19. Pham, P.N.H.; Nguyen, B.T.; Pham, C.V.; Nghia, N.D.; Snásel, V. Efficient Algorithm for Multiple Benefit Thresholds Problem in Online Social Networks. In Proceedings of the 15th IEEE-RIVF International Conference on Computing and Communication Technologies, Hanoi, Vietnam, 19–21 August 2021; pp. 1–6. [CrossRef] 20. Borgs, C.; Brautbar, M.; Chayes, J.T.; Lucier, B. Maximizing Social Influence in Nearly Optimal Time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, USA, 5–7 January 2014; pp. 946–957. [CrossRef] 21. Nguyen, H.T.; Thai, M.T.; Dinh, T.N. Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, 26 June–1 July 2016; pp. 695–710. [CrossRef] 22. Chen, W.; Yuan, Y.; Zhang, L. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In Proceedings of the ICDM 2010, the 10th IEEE International Conference on Data Mining, Sydney, Australia, 14–17 December 2010; pp. 88–97. [CrossRef] 23. Bozorgi, A.; Samet, S.; Kwisthout, J.; Wareham, T. Community-based influence maximization in social networks under a competitive linear threshold model. Knowl.-Based Syst. 2017,134, 149–158. [CrossRef] 24. Borodin, A.; Filmus, Y.; Oren, J. Threshold Models for Competitive Influence in Social Networks. In Proceedings of the Internet and Network Economics—6th International Workshop, WINE 2010, Stanford, CA, USA, 13–17 December 2010; pp. 539–550. [CrossRef] 25. Tang, J.; Tang, X.; Xiao, X.; Yuan, J. Online Processing Algorithms for Influence Maximization. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, 10–15 June 2018; Das, G., Jermaine, C.M., Bernstein, P.A., Eds.; pp. 991–1005. [CrossRef] 26. Akram, M.; Zafar, F. Hybrid Soft Computing Models Applied to Graph Theory. In Studies in Fuzziness and Soft Computing; Springer: Cham, Switzerland, 2020; Volume 380. [CrossRef] 27. Akram, M.; Luqman, A. Fuzzy Hypergraphs and Related Extensions. In Studies in Fuzziness and Soft Computing; Springer: Singapore, 2020; Volume 390. [CrossRef] 28. Li, Y.; Zhang, D.; Tan, K. Targeted Influence Maximization for Online Advertisements. PVLDB 2015,8, 1070–1081. 29. Barbieri, N.; Bonchi, F.; Manco, G. Topic-aware social influence propagation models. Knowl. Inf. Syst. 2013 ,37, 555–584. [CrossRef] 30. Chen, S.; Fan, J.; Li, G.; Feng, J.; Tan, K.; Tang, J. Online Topic-Aware Influence Maximization. PVLDB 2015 ,8, 666–677. [CrossRef] 31. Li, G.; Chen, S.; Feng, J.; Tan, K.L.; Li, W.-S. Efficient Location-Aware Influence Maximization. In Proceedings of the 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, 16–19 April 2018; pp. 1569–1572. 32. Wang, X.; Zhang, Y.; Zhang, W.; Lin, X. Efficient Distance-Aware Influence Maximization in Geo-Social Networks. IEEE Trans. Knowl. Data Eng. 2017,29, 599–612. [CrossRef] 33. Bharathi, S.; Kempe, D.; Salek, M. Competitive Influence Maximization in Social Networks. In Proceedings of the Internet and Network Economics, Third International Workshop, WINE 2007, San Diego, CA, USA, 12–14 December 2007; pp. 306–311. [CrossRef] 34. Chen, W.; Lu, W.; Zhang, N. Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, ON, Canada, 22–26 July 2012; pp. 592–598. 35. Nguyen, H.; Zheng, R. On Budgeted Influence Maximization in Social Networks. IEEE J. Sel. Areas Commun. 2013 ,31, 1084–1094. [CrossRef] 36. Goyal, A.; Bonchi, F.; Lakshmanan, L.V.S.; Venkatasubramanian, S. On minimizing budget and time in influence propagation over social networks. Soc. Netw. Anal. Min. 2013,3, 179–192. [CrossRef] 37. Cohen, E.; Delling, D.; Pajor, T.; Werneck, R.F. Sketch-Based Influence Maximization and Computation: Scaling Up with Guarantees. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, Shangai, China, 3–7 November 2014; pp. 629–638. [CrossRef] 38. Goyal, A.; Lu, W.; Lakshmanan, L.V. CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social Networks. In Proceedings of the 20th International Conference Companion on World Wide Web, New York, NY, USA, 28 March 2011; pp. 47–48. 39. Chung, F.R.K.; Lu, L. Survey: Concentration Inequalities and Martingale Inequalities: A Survey. Internet Math. 2006 ,3, 79–127. [CrossRef] Mathematics 2022,10, 876 18 of 18 40. Sachdeva, S.; Vishnoi, N.K. Approximation Theory and the Design of Fast Algorithms. arXiv 2013, arXiv:1309.4882. 41. Leskovec, J.; Kleinberg, J.M.; Faloutsos, C. Graph evolution: Densification and shrinking diameters. TKDD 2007 ,1, 2. [CrossRef] 42. Leskovec, J.; Lang, K.J.; Dasgupta, A.; Mahoney, M.W. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Math. 2009,6, 29–123. [CrossRef] 43. Chen, W.; Wang, Y.; Yang, S. Efficient influence maximization in social networks. In Proceedings of the KDD ’09 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 28 June–1 July 2009; pp. 199–208. [CrossRef] 44. Leskovec, J.; Adamic, L.A.; Huberman, B.A. From Competition to Complementarity: Comparative Influence Diffusion and Maximization. arXiv 2015, arXiv:1507.00317. 45. Yang, J.; Leskovec, J. Defining and Evaluating Network Communities based on Ground-truth. Knowl. Inf. Syst. 2015 ,42, 181–213. [CrossRef]