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

  Ci a ion: Pham, P.N.H.; Nguyen, B.-N.T.; Co, Q.T.N.; Snášel, V. Mul iple Bene i Th esholds P oblem in Online Social Ne wo ks: An Algo i hmic App oach. Ma hema ics 2022,10, 876. h ps://doi.o g/ 10.3390/ma h10060876 Academic Edi o s: Gaogao Dong and Jianguo Liu Recei ed: 16 Decembe 2021 Accep ed: 4 Ma ch 2022 Published: 9 Ma ch 2022 Publishe ’s No e: MDPI s ays neu al wi h ega d o ju isdic ional claims in published maps and ins i u ional a il- ia ions. Copy igh : © 2022 by he au ho s. Licensee MDPI, Basel, Swi ze land. This a icle is an open access a icle dis ibu ed unde he e ms and condi ions o he C ea i e Commons A ibu ion (CC BY) license (h ps:// c ea i ecommons.o g/licenses/by/ 4.0/). ma hema ics A icle Mul iple Bene i Th esholds P oblem in Online Social Ne wo ks: An Algo i hmic App oach Phuong N. H. Pham 1,2,* , Bich-Ngan T. Nguyen 1,2 , Quy T. N. Co 1and Václa Snášel 2 1Facul y o In o ma ion Technology, Ho Chi Minh Ci y Uni e si y o Food Indus y, 140 Le T ong Tan S ee , Ho Chi Minh 700000, Vie nam; [email p o ec ed] (B.-N.T.N.); [email p o ec ed] (Q.T.N.C.) 2Depa men o Compu e Science, Facul y o Elec ical Enginee ing and Compu e Science, VŠB-Technical Uni e si y o Os a a, 17.lis opadu 15/2172, 708 33 Os a a, Czech Republic; acla [email p o ec ed] *Co espondence: [email p o ec ed] Abs ac : An impo an p oblem in he con ex o i al ma ke ing in social ne wo ks is he In luence Th eshold (IT) p oblem, which aims a inding some use s ( e e ed o as a seed se ) o begin he p ocess o dissemina ing hei p oduc ’s in o ma ion so ha he bene i gained exceeds a p ede e - mined h eshold. E en hough, ma ke ing s a egies exhibi di e en in se e al ealis ic scena ios due o ma ke dependence o budge cons ain s. As a consequence, picking a seed se o a speci ic h eshold is no enough o come up wi h an e ec i e solu ion. To add ess he disad an ages o p e ious wo ks wi h a new app oach, we s udy he Mul iple Bene i Th esholds (MBT), a gene alized e sion o he IT p oblem, as a esul o his phenomenon. Gi en a social ne wo k ha is subjec ed o in o ma ion dis ibu ion and a se o h esholds, T={T1 , T2 , . . . , Tk} , Ti> 0, he issue aims o seek he seed se s S1 , S2 , . . . , Sk wi h he lowes possible cos so ha he bene i achie ed om he in luence p ocess is a he e y leas T1 , T2 , . . . , Tk , espec i ely. The main challenges o his p oblem a e a #NP-ha d p oblem and he es ima ion o he objec i e unc ion #P-Ha d unde adi ional in o ma ion p opaga ion models. In addi ion, adap ing he exis algo i hms many imes o di e en h esholds can lead o la ge compu a ional cos s. To add ess he abo emen ioned challenges, we in oduced E icien Sampling o Selec ing Mul iple Seed Se s, an e icien echnique wi h heo e ical gua an ees (ESSM). A he co e o ou algo i hm, we de eloped a no el algo i hmic amewo k ha (1) can use he solu ion o a smalle h eshold o ind ha o la ge ones and (2) can le e age exis ing samples wi h he cu en solu ion o ind ha o la ge ones. The ex ensi e expe imen s on se e al eal social ne wo ks we e conduc ed in o de o show he e ec i eness and pe o mance o ou algo i hm compa ed wi h cu en ones. The esul s indica ed ha ou algo i hm ou pe o med o he s a e-o - he-a ones in e ms o bo h he o al cos and unning ime. Keywo ds: social ne wo k; i al ma ke ing; in o ma ion di usion; app oxima ion algo i hm MSC: 68W25; 68R05; 90C27 1. In oduc ion In ecen yea s, he e has been a apid de elopmen o he global economy hanks o he con ibu ion o he Online Social Ne wo k (OSN), based on he p o ision o a powe ul pla o m o communica ion and in o ma ion dissemina ion in he ield o ma ke ing, media, and ad e ising, pa icula ly in social ne wo ks wi h billions o use s. The s ong unde pinnings o p oblems o social in luences in OSNs a e in o ma ion di usion models. Kempe e al. [ 1 ] i s in oduced wo classic models, named Independen Cascade (IC) and Linea Th eshold (LT), and o mula ed he In luence Maximiza ion (IM) p oblem, which aims o selec k nodes ha may impac he la ges numbe o use s a social ne wo k. This wo k has inspi ed many s udies on social in luence [ 2 – 10 ], misin o ma ion/ umo s de ec ion, and con ol [11–15]. Ma hema ics 2022,10, 876. h ps://doi.o g/10.3390/ma h10060876 h ps://www.mdpi.com/jou nal/ma hema ics Ma hema ics 2022,10, 876 2 o 18 In he con ex o i al ma ke ing o p oduc p omo ion, hos s (companies) o en de ise a ma ke ing campaign including he dis ibu ion o p oduc samples o selec ed use s and expec ha hey pe suade hei iends, iends o iends, e c. The numbe o people who ha e been impac ed eaches a ce ain le el. In luence Th eshold (IT) was inspi ed by his phenomenon and a slew o esea ch backed i up; i looks o a node se wi h he smalles size possible so ha he numbe o impac ed nodes eaches o su passes a p ede e mined h eshold γ [ 8 , 16 , 17 ]. The alue o γ can de e mine he scale o o he i al ma ke ing. Howe e , in some ealis ic scena ios, he e is a dis inc cos o pe suade a use who p omo es a sample p oduc [ 4 , 18 ]. Besides, each in luenced use o en o e s a di e en bene i when one is in luenced a e he ma ke ing p ocess. Cus ome s wi h signi ican inancial esou ces, o example, will be able o pu chase mo e hings han o he s. As a esul , he exis ing algo i hms o IT p oblem may o e an inaccu a e solu ion o a ma ke ing pu pose. Mo eo e , he ma ke ing s a egies a e o en adjus ed since he ma ke can a y in a sho ime. Consequen ly, a pa icula solu ion o a bene i is insu icien o be he o e all e ec i e solu ion. This can be o e come by inding solu ions o mul iple h esholds and selec ing he bes one ha sui s hei budge and cu en ma ke . Fo ins ance, assume ha a company wan s o come up wi h a s a egy ha can in luence cus ome s on an online social ne wo k. None heless, o due o budge luc ua ions o he ins abili y o he ma ke , hey may conside s a egies o sp eading wi h he di e en numbe o in luenced cus ome s such as 1000, 2000, 3000, 5000, e c. In his case, he company wan s o ind solu ions, whe e he bene i unc ion o each is abo e he co esponding h eshold and hen ha company can selec a solu ion wi h a easonable cos so as o execu e i s ma ke ing plan well. Ou goal in his s udy is o de elop an answe o a no el Mul iple Bene i Th esholds (MBT) p oblem, which is exp essed as ollows. Fo a social ne wo k G= (V , E) gi en a se o k bene i h esholds T={T1 , T2 , . . . , Tk} , each use u has a dis inc cos p ice c(u)> 0. The issue is o seek o he a ious seed se s {S1 , S2 , . . . , Sk} , in which each Si has he cheapes o al cos c(Si) by a esul o each seed se ’s ea ned bene i Si , cha ac e ized by B(Si) , and is a leas Ti o i= 1 . . . , k . The e a e wo main challenges o sol ing MBT p oblem. Fi s ones a e o ind MBT as #NP-Ha d and o calcula e he bene i unc ion #P-Ha d. Secondly, inding nume ous seed se s o mul iple h esholds needs mo e ime and memo y han o he in o ma ion p opaga ion challenges, as well as he IT p oblem. I is necessa y o un he exis ing algo i hms o a single h eshold k imes o p o e i is cos ly and, hence, no applicable o la ge ne wo ks. To o e come he challenges, in his pape , we p opose a highly e icien algo i hm o sol e he p oblem. This no only gua an ees a solu ion bu also p oduces good esul s in p ac ice. This wo k e ised and ex ended he ou con e ence pape [19] by p o iding all he p oo s mo e de ail and expe imen e alua ion. The ollowing is a lis o ou con ibu ions as a whole: • The Mul iple Bene i Th esholds (MBT) is i s o mula ed wi h he Independen Cascade (IC) in o ma ion di usion model. • Wi h a iew o de eloping he solu ion, he E icien Sampling o Mul iple Seed Se Selec ion (ESSM) is p oposed, a heo e ical app oxima ion algo i hm bounds by de eloping a no el algo i hmic amewo k ha u ilizes he sample echnique o es ima e he bene i unc ion, deno ed as B(·) , and le e ages he seed se and he samples wi h smalle bene i h eshold wi h he pu pose o inding he seed se o he la ge ones. Acco dingly, ou algo i hm can ind mul iple seed se s in only one un. Fo solu ion gua an ee, ou algo i hm e u ns mul iple seed se s Si sa is ying B(Si)≥1−e 1+eTi−e and he o al cos c(Si)≤( 1 +ln (Ti−eTi) e)c(S∗ i) a s ong possibili y (w.h.p), whe e e> 0 is an inpu and S∗ i is he bes seed se in e ms o h eshold Ti o all i=1, 2, . . . , k. • Ex ensi e expe imen s on six eal-wo ld ne wo ks a e pe o med, including Gnu ella, Email-En on, Ne -Hep , Ne -Phy, Amazon, and DBLP o he compa ison o he e iciency be ween ou algo i hm and o he s a e-o - he-a ones. The esul s o expe i- Ma hema ics 2022,10, 876 3 o 18 men s indica ed ha ou algo i hm ou pe o med he s a e-o - he-a ones in espec o bo h he cos and he unning ime. O ganiza ion. The es o he pape is s uc u ed as ollows. In Sec ion 2, we e iew p e ious ele an wo ks o in luence maximiza ion. Sec ion 3p esen s he model, p oblem de ini ion, and main algo i hm. The expe imen esul s a e shown and explained in Sec ion 4. Finally, Sec ion 5b ings he pape o he conclusion. 2. Rela ed Wo ks In his sec ion, we e iew p e ious s udies ela ed o ou abo emen ioned p oblem, including In o ma ion p opaga ion models, In luence Maximiza ion, and In luence Th eshold. In o ma ion p opaga ion models and In luence Maximiza ion. Social ne wo ks p o- ide a con enien en i onmen o business ma ke ing h ough he wo d-o -mou h e ec . In luence Maximiza ion (IM) [ 1 ], which seeks ou k nodes (seed se ) in a social ne wo k ha can in luence he g ea es numbe o nodes is one o he mos impo an challenges in social ne wo k in luence. Kempe e al. o iginally in es iga ed IM as an #NP-ha d combina o ial op imiza ion unde wo amous in o ma ion di usion models: Linea Th eshold (LT) and Independen Cascade (IC). Fu he mo e, he challenge o sol ing IM also coming om calcula ing he in luence unc ion unde wo abo e models is #P-ha d models— ha is, i is impossible o calcula e in polynomial ime wi h inpu size [ 5 , 6 ]. Howe e , due o he eno mous applica ion o IM in comme ce, se e al e icien algo i hms we e p oposed o sol ing he p oblem in la ge-scale ne wo ks, such as app oxima ion algo i hm [1–3,20,21] and heu is ics wi hou heo e ical gua an ee [ 7 , 22 , 23 ]. No ably, Bo g e al. [ 24 ] made a heo e ical b eak h ough by p oposing a ( 1 − 1 /e−e) -app oxima ion algo i hm in O(e−3kl2(m+n)log2n) wi h a p obabili y a leas 1 −n−l . The main idea o Bo g’ al- go i hm is ha hey p oposed a sample echnique, namely, Re e se Reachable (RR) se , o es ima e he numbe o in luenced nodes unde s ochas ic in o ma ion p opaga ion models and an algo i hmic amewo k ha inds he solu ion in gene a ed samples wi h heo e ical bound. Tang e al. [ 2 ] p oposed he TIM/TIM++ algo i hms educing he ime complexi y o O(e−2(k+l)(m+n)log n) while main aining he pe o mance gua an ees and demons a ed he high e iciency o hei algo i hm in billion-scale ne wo ks. La e on, se e al algo i hms ha e been de ised in an a emp o educe he sample complexi y and unning ime bu hey s ill main ained an app oxima e a io by modi ying he RIS amewo k, including IMM [ 3 ], SSA/DSSA [ 21 ], OPIM [ 25 ], e c. Recen ly, Ak am e al. men ioned inding in luen ial communi ies in a social ne wo k wi h uzzy compe i ion hype g aphs no ion [26,27]. In o he di ec ions, nume ous s udies we e ca ied ou on a ia ions o IM o many scena ios o i al ma ke ing. The au ho s in [ 28 – 30 ] conside ed IM unde opic que ies by in oducing he in o ma ion di usion model ha can enable many opics o sp ead. Addi ionally, he ad ance in geoposi ion enabled de ices and se ices makes OSNs able o in eg a e a use ’s loca ion. The au ho s in [ 31 ] in es iga ed he loca ion-awa e in luence maximiza ion (LIM) p oblem in which some nodes we e selec ed and he la ges numbe o nodes was in luenced in a gi en dis ance; [ 32 ] conside ed he ole o dis ance among use s o p omo e he in luence p ocess o i al ma ke ing. Mo eo e , se e al o he a ia ions o IM including compe i i e-awa e [ 5 , 33 ] and ime-awa e [ 34 ] ha e been in oduced and s udied. Recen ly, Nguyen e al. [ 35 ] has s udied IM unde he budge cons ain whe e each node has he limi ed cos o adop a sample p oduc and he o al budge was equi ed. In he seminal pape , i showed ha he g eedy algo i hm can achie e an app oxima ion a io o 1 − 1 /√e and u he p oposed e icien heu is ic algo i hms wi hou any pe o - mance gua an ees. La e , Nguyen e al. [ 4 ] s udied he Cos -awa e Ta ge ed Vi al Ma ke ing (CTVM) p oblem, a gene aliza ion o IM. In his p oblem, each node u has an a bi a y cos c(u) and a bene i b(u) . The goal o CTVM was o selec a seed se wi hin a gi en budge B so ha he o al bene i was maximized. They p oposed a bene i sampling echnique and a 1 −1 √e−e app oxima ion algo i hm wi h p obabili y a leas 1 −δ in O(e−2nlog((n k))/δ) . In his s udy, he sampling echnique in [ 4 ] is adap ed o es ima e he bene i unc ion. Ma hema ics 2022,10, 876 4 o 18 Howe e , BCT could no adap o sol ing ou p oblem due o he di e ence be ween MBT and CTVM. In luence Th eshold. In luence Th eshold (IT), which seeks he smalles size seed se S such ha he in luence sp ead, de ined as σ(S) , is a leas a speci ied h eshold γ , is he p oblem ha comes closes o ou s. Goyal e al. [ 36 ] we e he i s o in es iga e he IT p oblem using IC models. Using he in luence unc ion’s mono one submodula cha ac e is ic, hey p oposed a g eedy algo i hm combining wi h Mon e Ca lo simula ion me hod [ 1 ] o es ima e σ(S) . The algo i hm e u ns a seed se S sa is ying σ(S)≥γ−e and |S|≤|S∗|·( 1 +ln γ e) in O(n2R) ime complexi y, whe e e> 0 is an inpu , S∗ is he op imal solu ion, and R is numbe o Mon e Ca lo simula ions wi h se ing R= 10.000. Due o i s high ime complexi y, i is di icul o apply his algo i hm o la ge ne wo ks. By u ilizing he sampling echnique me hod in [ 37 ], Kuhnle e al. [ 8 ] de eloped a ( 1 − 2 α ,1 + 4 αγ +log γ) — bic i e ia app oxima ion algo i hm o a special case o IT whe e cos o he e ices is he same (We call an algo i hm is an (α , β) -bic i e ia app oxima ion o IT p oblem i i e u ns a solu ion S sa is ying σ(S)≥α·T and |S| ≤ β·|S∗| , whe e α , β> 0 and S∗ is he op imal solu ion.) in O(α2(m+n)log(n)|S|) ime complexi y, whe e α∈( 0,1 ) is an inpu and n , m e e o he numbe o nodes, edges in he ne wo k. The au ho s o [ 17 ] ecen ly explo ed IT in a noisy model esembling a eal-wo ld si ua ion, whe e we only es ima e he in luence sp ead unc ion wi hin an e o bound. The g eedy algo i hm unde noise wi h heo e ical bound was p oposed bu i e ained ime complexi y as in [ 38 ]. In hese s udies, hey igno ed he poin ha each a ec ed use p o ided a di e en bene i in hese expe imen s. The bene i s o he nodes and di e en bene i h esholds a e conside ed o iden i ying he app op ia e seed se s in ou MBT p oblem. In he case o he g ea simila i y in bene i s o nodes, he abo e algo i hms can be used o each h eshold Ti , bu i is impe a i e o un k imes o ind he k seed se s. On he o he hand, ou p oposed algo i hm no only p o ides heo e ical bounds bu also e u ns mul iple seed se s o se o bene i h esholds a a single ime. 3. Me hodology In his sec ion, Independen Cascade (IC) model is p esen ed, as he well-known o iginal model ela ed o he IM p oblems. [ 1 – 4 , 20 , 21 ]. Ou no a ions and symbols a e summa ized in Table 1. Table 1. Table o symbols. No ional Desc ip ion n,mThe numbe o nodes and o edges in G, espec i ely Nin( ),Nou ( )The incoming and ou going neighbo node se o . SiThe solu ion e u ned by ou algo i hm o h eshold Ti B(S),ˆ B(S)De ine he bene i unc ion and an es ima ion o bene i unc ion Γ Γ =∑u∈Vb(u) S∗ iThe op imal seed se o h eshold 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 =a gmaxi=1...|Sk|ln((n i)) 3.1. Independen Cascade Model In his wo k, a social ne wo k is abs ac ed by a di ec ed g aph G= (V , E) . V and E ep esen he se o use s and he se o links in he ne wo k, espec i ely. In his model, each edge e= (u , )∈E has a p obabili y p(u , )∈( 0,1 ) ep esen ing he in luence ansmission om u o . Gi en a seed se S⊆V , each node is in one o wo s a es: ac i e and inac i e, which e lec s whe he i is in luenced by he seed se o no . The di usion p ocess s a s om Sand wo ks as ollows: • A he beginning (s ep =0), all nodes in he seed se a e ac i e. Ma hema ics 2022,10, 876 5 o 18 • A he nex s eps (s ep ≥ 1), an node u , which is ac i a ed in p e ious s eps, has a sin- gle chance o in luence each o i s neighbo s wi h he p obabili y o success p(u, ). • All ac i e nodes e ain hei s a us un il he end o he di usion p ocess, and he p ocess ends a s ep i he e is no new ac i a ed node in his s ep. Kempe e al. [ 1 ] showed ha he IC model was equi alen o sample g aph model, de ined as ollows. The li e-edge model i s gene a es a sample g aph g= (Eg , Vg) by selec ing e= (u , )∈E wi h p obabili y p(e) = p(u , ) and no selec ing e= (u , )∈E wi h p obabili y 1 −p(u, ). The sample g aph gis gene a ed wi h p obabili y P [g/G] = ∏ e∈Eg p(e)·∏ e∈E Eg (1−p(e)) (1) In ou model se ing, we will gain a bene i b(u)>= 0 i he node u becomes ac i e, as in [ 4 ]. Bene i unc ion B(S) , deno ed as he o al bene i o e all in luenced nodes, is calcula ed as ollows: B(S) = ∑ g/G P [g/G]∑ u∈R(g,S) b(u)(2) whe e R(g , S) is he se o nodes ha can each om any node in S in g aph g . In addi ional, each node u∈V has a cos c(u)> 0, which we ha e o pay o use u o ini ia e he in luence p ocess om u and c(S) = ∑u∈Sc(u). 3.2. P oblem De ini ion We o mally in oduce ou s udied p oblem, Mul iple Bene i Th esholds (MBT), as ollows: De ini ion 1 (MBT) . Gi en a g aph G= (V , E) unde he IC model and he se o bene i h esholds T={T1 , T2 , . . . , Tk} . Fo each Ti∈T , he p oblem is equi ed o ind Si∈V wi h smalles cos c(Si)so ha B(Si)≥Ti. In he case when b(u) = 1, ∀u∈V , he bene i unc ion B(·) becomes he in luence sp ead unc ion [ 1 ]. Re . [ 6 ] showed ha i was #P-ha d o compu e he numbe o in luence nodes (in luence sp ead unc ion) exac ly, so calcula ing B(·) was also #P-ha d. Besides, he IT p oblem [ 8 , 17 , 38 ], a special case o MBT p oblem wi h b(u) = c(u) = 1, ∀u∈V and k=1, is NP-ha d, which implies ha MBT is also #NP-ha d. 3.3. Ou P oposed Algo i hm In his sec ion, he E icien Sampling o Selec ing Mul iple seed se s (ESSM), an e - icien algo i hm o MBT p oblem wi h heo e ical gua an ee, is in oduced. Ou no el echnique is o de elop a me hod ha combines wo ollowing ideas: (1) inds he candida e seed se o each h eshold ia he bene i sampling; (2) uses he seed se wi h a smalle h eshold o inding he seed se s wi h bigge ones, which can imp o e he unning ime as well as memo y usage. Mo eo e , he sampling echnique wi h ma ingale heo y is in use o es ima e he bene i unc ion e ec i ely. 3.3.1. Bene i Sampling We i s ecap he concep o Bene i Sample (BS) in [4] o es ima e he B(·). De ini ion 2 (Bene i Sample) . A BS is gene a ed om G= (V , E) unde he IC model by ollowing s eps: (1) Choose a sou ce node u wi h p obabili y b(u) Γ , (2) c ea e a sample g aph g om G, and (3) e u n Rjas he se o nodes ha can each node u in g. The Algo i hm 1in [4] can be used o gene a e a BS o IC model. Ma hema ics 2022,10, 876 6 o 18 Algo i hm 1: An algo i hm o gene a ing a BS unde he IC model. Inpu : G aph G= (V,E)unde IC model Ou pu : A BS se Rj 1: Choose a sou ce node uwi h p obabili y b(u) Γ 2: Ini ialize a queue Q={u}and Rj={u} 3: while Qis no emp y do 4: ←Q.pop() 5: o u∈Nin( ) (Rj∪Q)do 6: Wi h p obabili y p(u, )do: Q.push(u),Rj←Rj∪{u}; 7: end o 8: end while 9: e u n Rj Gi en R is a collec ion o BSes, a seed se S , we de ine a andom a iable Xj(S) as ollows: Xj(S) = (1, I Rj∩S6=∅ 0,O he wise (3) We can es ima e he bene i unc ion B(S)by he ollowing Lemma in [4]. Lemma 1 (Lemma 2, [4]).Fo any se o nodes S ⊆V, we ha e: B(S) = Γ·E[Xj(S)] The unc ion B(·) is mono one and submodula [ 4 ], i.e., o any S⊆T⊆V , and /∈T , we ha e B(T)≥B(S)(4) B(S+{ })−B(S)≥B(T+{ })−B(T)(5) We can calcula e an es ima ion ˆ B(S)o B(S) ia a collec ion Ro BSes as ollows: ˆ B(S) = Γ |R| ∑ Rj∈R Xj(S)(6) I can be seen ha Xj(S)∈[ 0,1 ] . We de ine a andom a iable Yi=∑i j=1(Xj(S)−µ) , ∀i≥1, whe e µ=E[Xj]and a sequence andom a iables Y1,Y2, . . ., we ha e E[Yi|Y1, . . . , Yj−1] = E[Yi−1] + E[Yi(S)−µ] = E[Yi−1] The e o e, Y1 , Y2 , . . . a ea o mo ma ingale[ 39 ]. Thus, weha e he ollowing Lemma[ 39 ]. Lemma 2 ([39]).Gi en a collec ion Rwi h T =|R| and λ>0, we ha e P hT ∑ j=1 Xj(S)−T·µ≥λi≤exp(−λ2 2λ2 3+µT)(7) P hT ∑ j=1 Xj(S)−T·µ≤ −λi≤exp−λ2 2µT(8) Ma hema ics 2022,10, 876 7 o 18 Le λ=eTµin Lemma 2, we ob ain P [ˆ B(S)≥(1+e)B(S)] ≤exp(−e2µT 2+2 3e)(9) P [ˆ B(S)≤(1−e)B(S)] ≤exp−e2µT 2(10) I he numbe o BSs is a leas T≥( 2 +2 3)1 µ1 e2ln(1 δ) o δ∈( 0,1 ) , ˆ BR(S) is an (e,δ)-app oxima ion o B(S), i.e., P [(1−e)B(S)≤ˆ B(S)≤(1+e)B(S)] ≥1−δ(11) The cha ac e is ics o he ma ingale sequence play an impo an ole in de ising ou algo i hm in he nex subsec ion. 3.3.2. ESSM Algo i hm Ou p oposed algo i hm is now desc ibed. On a high le el, ou algo i hm combines wo me hods: (1) We p o ide a (δ , e) -app oxima ion o he bene i unc ion ia ma ingale heo y. (2) In each i e a ion, we p opose he algo i hmic amewo k ha inds some candida e seed se s o a h eshold and hen choose he inal seed se , which gua an ees he solu ion quali y by checking s a ic e idence. (3) We euse he seed se o smalle h eshold o inding he seed se s wi h he la ge h eshold. Ou p oposed algo i hm is p esen ed in Algo i hm 2. Algo i hm 2: ESSM algo i hm. Inpu : A g aph G= (V,E),T={T1, . . . , Tk},e,δ∈(0,1) Ou pu : S1,S2, . . . , Sk 1: Gene a e R0con aining (2+2 3e)Γ e2(Ti−eTi)(ln n+ln(1/δ)) BSs by using Algo i hm 1 2: S0←∅ 3: o i=1 o kdo 4: Ri← Ri−1 5: Si←Si−1 6: Calcula e ˆ B(Si)by Equa ion (6) 7: while ˆ B(Si)<Ti−eTi−edo 8: u←a gmax ∈V Si min(ˆ B(Si∪ ),Ti−eTi−e)−ˆ B(Si) c( ) 9: Si←Si∪{u} 10: j← |Si| 11: N(i,j)←(2+2 3e)Γ e2(Ti−eTi)ln((n j)/δ) 12: i |Ri|<N(i,j) hen 13: Gene a e mo e N(i,j)−|Ri|BSs and add hem in o Ri 14: N←N(i,j) 15: Si←∅ 16: end i 17: end while 18: end o 19: e u n S1,S2, . . . , Sk A he beginning o he algo i hm, i gene a es collec ion R0 ha con ains (2+2 3e)Γ e2(Ti−eTi)(ln n+ln(1/δ)) BSs by using Algo i hm 1and ini ia es a seed se S1as emp y. A each i e a ion i o i s loop (line 3–18), i inds he seed se wi h espec o h eshold Ti . Deno e (Si) = min(ˆ B(Si) , Ti−eTi−e) . A each i e a ion o he second loop (line 7–18), he algo i hm inds a seed Si , by i e a i ely selec ing a node u wi h maximum ma ginal o Ma hema ics 2022,10, 876 8 o 18 he es ima ion unc ion as pe i s cos , i.e., ( (Si∪{u})− (Si))/c( ) and (2) checking he condi ion o he numbe o samples (line 12). I he numbe o samples is su icien o gi e an (δ , e) -app oxima ion (by Lemma 3), he algo i hm mo es in o nex i e a ions and keeps cu en seed se Si ; o he wise, he algo i hm gene a es mo e samples (line 13) so ha he numbe o samples is N(i , j) and adds hem in o Ri . In his case, he seed se Si is sui able o new collec ion Ri . The second loop e mina es when i sa is ies he condi ion ˆ B(Si)≥Ti−eTi−e . Nex , he algo i hm euses he cu en samples and seed se o ind he seed se o la ge h eshold (lines 4–5) by using simila s eps wi h p e ious i e a ion. The heo e ical bounds o he algo i hm a e now analyzed. Fi s ly, he sa is ac o y numbe o BSes is p o ided o es ima e B(·)is shown in Lemma 3. Lemma 3. I |R| ≥ (2+2 3e)Γ e2(Ti−eTi)(ln n+ln 1 δ) hen P [ˆ B(S∗ i)≥Ti−Tie]≥1−δ P oo . Deno e µ=B(S∗ i)/Γ,ˆ µ=ˆ B(S∗ i)/Γ, we ha e P [ˆ B(S∗ i)≤Ti−Tie]≤P [ˆ B(S∗ i)≤(1−e)B(S∗ i)] =P [ˆ µ≤(1−e)µ](By applying (10)) ≤exp−e2|R|µ 2 ≤exp−e2|R|ˆ µ 2(1−e)(Due o µ≥ˆ µ/(1−e)) ≤exp −(2+2 3e)ˆ B(S∗ i) 2(1−e)(Ti−eTi)ln 1 δ!≤δ which implies he p oo . The heo e ical gua an ee o Algo i hm 2is s a ed as ollows. Theo em 1. Fo any inpu s e , δ∈( 0,1 ) , he Algo i hm 2 e u ns a se o seed se s S= {S1,S2, . . . , Sk}sa is ying (a) P [c(Si)≤(1+ln Ti−eTi e)c(S∗ i)] ≥1−δ/n. (b) P B(Si)≥Ti·1−e 1+e−e≥1−δ. P oo . A any i - h i e a o o he i s loop (line 3 o 19) in Algo i hm 2, deno e Si=S i={s1 i , s2 i , . . . , s i} as he solu ion o algo i hm wi h espec o he h eshold Ti , and Pi={ i 1 , i 2 , . . . , i l} as a se o nodes wi h minimum cos sa is ying ˆ B(Pi)≥Ti−eTi and Ci=c(Pi) . Due o he checking condi ion in line 12, he numbe o BSes a he end o i e a ion iob ains a leas Ni min =(2+2 3e)Γ e2(Ti−eTi)ln(n |Si|/δ)(12) and ob ains a mos , Ni max =max j:1...|Si| (2+2 3e)Γ e2(Ti−eTi)ln(n j/δ)(13) Ma hema ics 2022,10, 876 9 o 18 P o e (a) As ˆ B(·)is submodula , we ha e Ti−eTi−ˆ B(S −1 i)) ≤ˆ B(Pi)−ˆ B(S −1 i)) ≤ˆ B(Pi∪S −1 i)−ˆ B(S −1 i)) ≤∑ ∈Pi S −1 i (ˆ B(S −1 i∪{ })−ˆ B(S −1 i)) ≤Ci c(S −1 i)∑ ∈Pi S −1 i (ˆ B(S −1 i∪{ })−ˆ B(S −1 i)) Fo any posi i e numbe s a1, . . . aland b1, . . . , bl. Acco ding o [40], we ha e min i=1...l ai bi≤∑l i=1ai ∑l i=1bi≤max i=1...l ai bi (14) Applying he abo e inequali y, we ob ain Ti−eTi−ˆ B(S i)≤Ci c(s i)(ˆ B(S i)−ˆ B(S −1 i)) (15) ≤(1−c(s i) Ci )(Ti−eTi−ˆ B(S −1 i)) (16) ≤e−c(s i) Ci(Ti−eTi−ˆ B(S −1 i)) (17) The (17) condi ion mus sa is y x+1≤ex, o any x>0. The e o e, Ti−eTi−ˆ B(S i)≤e−1 Ci∑ j=1c(s i)(Ti−eTi)(18) =e−1 Cic(S i)(Ti−eTi)(19) By he de ini ion o S i and because Si sa is ies he condi ion in line 7, we ha e ˆ B(S −1 i)<Ti−eTi−eand ˆ B(S i)≥Ti−eTi−e. Combining wi h (19), we ha e (Ti−eTi)e−1 Cic(S −1 i)≥Ti−eTi−ˆ B(S −1 i) >Ti−eTi−(Ti−eTi−e) = e implying ha c(S −1 i)<Ciln Ti−eTi e. On he o he hand, om (17), we ob ain c(s i)≤Ciln Ti−eTi−ˆ B(S −1 i) Ti−eTi−ˆ B(S i)≤1 (20) Thus, c(S i) = c(S −1 i) + c(s i)≤Ci( 1 +ln(Ti−eTi e)) , whe e Si is he candida e solu ion o h eshold Ti . A e i - h i e a ion o he i s loop, |Ri|=N(i , j) = (2+2 3e)Γ e2(Ti−eTi)ln((n j)/δ) . By applying Lemma 3, a e i e a o i , we ha e P [B(S∗ i)≥Ti−eTi]≥ 1 −δ/(n j) . Com- bining wi h he de ini ion o Pi , he ollowing e en s happen wi h a p obabili y o a leas 1−δ/(n )≥1−δ/n: c(Si)≤Ci(1+ln(Ti−eTi e)) (21) ≤c(S∗ i)(1+ln(Ti−eTi e)) (22) Ma hema ics 2022,10, 876 16 o 18 Au ho Con ibu ions: Concep ualiza ion, P.N.H.P.; me hodology, P.N.H.P. and Q.T.N.C.; so wa e, B.-N.T.N.; alida ion, Q.T.N.C.; o mal analysis, B.-N.T.N.; in es iga ion, P.N.H.P.; esou ces, Q.T.N.C.; w i ing—o iginal d a p epa a ion, P.N.H.P.; w i ing— e iew and edi ing, P.N.H.P., B.-N.T.N., Q.T.N.C. and V.S.; supe ision, V.S.; p ojec adminis a ion, P.N.H.P. All au ho s ha e ead and ag eed o he published e sion o he manusc ip . Funding: This esea ch was suppo ed by Ho Chi Minh ci y Uni e si y o Food Indus y (HUFI). Ins i u ional Re iew Boa d S a emen : No applicable. In o med Consen S a emen : No applicable. Da a A ailabili y S a emen : All eal-wo ld social ne wo k da ase s used in he expe imen can be downloaded a h p://snap.s an o d.edu/da a/ (accessed on 15 Sep embe 2021). Acknowledgmen s: This wo k was suppo ed by Ho Chi Minh Ci y Uni e si y o Food Indus y (HUFI). Con lic s o In e es : The au ho s decla e ha he e is no con lic o in e es . The unde s ha e no ole in he esea ch p ocess and he w i ing o he manusc ip . Re e ences 1. Kempe, D.; Kleinbe g, J.M.; Ta dos, É. Maximizing he sp ead o in luence h ough a social ne wo k. In P oceedings o he Nin h ACM SIGKDD In e na ional Con e ence on Knowledge Disco e y and Da a Mining, Washing on, DC, USA, 24–27 Augus 2003; pp. 137–146. [C ossRe ] 2. Tang, Y.; Xiao, X.; Shi, Y. In luence maximiza ion: Nea -op imal ime complexi y mee s p ac ical e iciency. In P oceedings o he 2014 ACM SIGMOD In e na ional Con e ence on Managemen o Da a, Snowbi d, UT, USA, 22–27 June 2014; pp. 75–86. [C ossRe ] 3. Tang, Y.; Shi, Y.; Xiao, X. In luence Maximiza ion in Nea -Linea Time: A Ma ingale App oach. In P oceedings o he 2015 ACM SIGMOD In e na ional Con e ence on Managemen o Da a, Melbou ne, Aus alia, 31 May–4 June 2015; pp. 1539–1554. [C ossRe ] 4. Nguyen, H.T.; Thai, M.T.; Dinh, T.N. A Billion-Scale App oxima ion Algo i hm o Maximizing Bene i in Vi al Ma ke ing. IEEE ACM T ans. Ne w. 2017,25, 2419–2429. [C ossRe ] 5. Chen, W.; Lakshmanan, L.V.S.; Cas illo, C. In o ma ion and In luence P opaga ion in Social Ne wo ks; Syn hesis Lec u es on Da a Managemen ; Mo gan & Claypool Publishe s: San Ra ael, CA, USA, 2013. [C ossRe ] 6. Chen, W.; Wang, C.; Wang, Y. Scalable In luence Maximiza ion o P e alen Vi al Ma ke ing in La ge-Scale Social Ne wo ks. In P oceedings o he 16 h ACM SIGKDD In e na ional Con e ence on Knowledge Disco e y and Da a Mining, Washing on, 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. In luence Maximiza ion in Social Ne wo ks When Nega i e Opinions May Eme ge and P opaga e. In P oceedings o he Ele en h SIAM In e na ional Con e ence on Da a Mining, Mesa, AZ, USA, 28–30 Ap il 2011; pp. 379–390. [C ossRe ] 8. Kuhnle, A.; Pan, T.; Alim, M.A.; Thai, M.T. Scalable Bic i e ia Algo i hms o he Th eshold Ac i a ion P oblem in Online Social Ne wo ks. In P oceedings o he IEEE Con e ence on Compu e Communica ions, A lan a, GA, USA, 1–4 May 2017. [C ossRe ] 9. Pham, C.V.; Duong, H.V.; Bui, B.Q.; Thai, M.T. Budge ed Compe i i e In luence Maximiza ion on Online Social Ne wo ks. In Lec u e No es in Compu e Science, P oceedings o he Compu a ional Da a and Social Ne wo ks— 7 h In e na ional Con e ence, CSoNe 2018, Shanghai, China, 18–20 Decembe 2018; Chen, X., Sen, A., Li, W.W., Thai, M.T., Eds.; Sp inge : Cham, Swi ze land, 2018; Volume 11280, pp. 13–24. [C ossRe ] 10. Pham, C.V.; Thai, M.T.; Ha, D.K.; Ngo, D.Q.; Hoang, H.X. Time-C i ical Vi al Ma ke ing S a egy wi h he Compe i ion on Online Social Ne wo ks. In Lec u e No es in Compu e Science P oceedings o he Compu a ional Social Ne wo ks—5 h In e na ional Con e ence, CSoNe 2016, Ho Chi Minh Ci y, Vie nam, 2–4 Augus 2016; Nguyen, H.T., Snásel, V., Eds.; Sp inge : Cham, Swi ze land, 2016; Volume 9795, pp. 111–122. [C ossRe ] 11. Pham, C.V.; Dinh, H.M.; Nguyen, H.D.; Xuan, H.H.; Dang, H.T. Limi ing he Sp ead o Epidemics wi hin Time Cons ain on Online Social Ne wo ks. In P oceedings o he Eigh In e na ional Symposium on In o ma ion and Communica ion Technology, Nha T ang Ci y, Vie nam, 7–8 Decembe 2017; pp. 262–269. [C ossRe ] 12. Pham, C.V.; Phu, Q.V.; Hoang, H.X.; Pei, J.; Thai, M.T. Minimum budge o misin o ma ion blocking in onlinesocial ne wo ks. Comb. Op im. 2019,38, 1101–1127. [C ossRe ] 13. Budak, C.; Ag awal, D.; El Abbadi, A. Limi ing he sp ead o misin o ma ion in social ne wo ks. In P oceedings o he 20 h In e na ional Con e ence on Wo ld Wide Web, WWW 2011, Hyde abad, India, 28 Ma ch–1 Ap il 2011; pp. 665–674. [C ossRe ] 14. Zhang, H.; Alim, M.A.; Li, X.; Thai, M.T.; Nguyen, H.T. Misin o ma ion in Online Social Ne wo ks: De ec Them All wi h a Limi ed Budge . ACM T ans. In . Sys . 2016,34, 1–24. [C ossRe ] 15. Pham, C.V.; Pham, D.V.; Bui, B.Q.; Nguyen, A.V. Minimum budge o misin o ma ion de ec ion in online social ne wo ks wi h p o able gua an ees. Op im. Le . 2022,16, 515–544. [C ossRe ] Ma hema ics 2022,10, 876 17 o 18 16. Goyal, A.; Lu, W.; Lakshmanan, L.V. Simpa h: An E icien Algo i hm o In luence Maximiza ion unde he Linea Th eshold Model. In P oceedings o he 11 h IEEE In e na ional Con e ence on Da a Mining, ICDM 2011, Vancou e , BC, Canada, 11–14 Decembe 2011; pp. 211–220. [C ossRe ] 17. C aw o d, V.G.; Kuhnle, A.; Thai, M.T. Submodula Cos Submodula Co e wi h an App oxima e O acle. In P oceedings o he 36 h In e na ional Con e ence on Machine Lea ning, ICML 2019, Long Beach, CA, USA, 9–15 June 2019; Chaudhu i, K., Salakhu dino , R., Eds.; PMLR: Moun ain View, CA, USA, 2019; Volume 97, pp. 1426–1435. 18. Pham, C.V.; Duong, H.V.; Thai, M.T. Impo ance Sample-Based App oxima ion Algo i hm o Cos -Awa e Ta ge ed Vi al Ma ke ing. In P oceedings o he Compu a ional Da a and Social Ne wo ks—8 h In e na ional Con e ence, Ho Chi Minh Ci y, Vie nam, 18–20 No embe 2019; pp. 120–132. [C ossRe ] 19. Pham, P.N.H.; Nguyen, B.T.; Pham, C.V.; Nghia, N.D.; Snásel, V. E icien Algo i hm o Mul iple Bene i Th esholds P oblem in Online Social Ne wo ks. In P oceedings o he 15 h IEEE-RIVF In e na ional Con e ence on Compu ing and Communica ion Technologies, Hanoi, Vie nam, 19–21 Augus 2021; pp. 1–6. [C ossRe ] 20. Bo gs, C.; B au ba , M.; Chayes, J.T.; Lucie , B. Maximizing Social In luence in Nea ly Op imal Time. In P oceedings o he Twen y-Fi h Annual ACM-SIAM Symposium on Disc e e Algo i hms, SODA 2014, Po land, OR, USA, 5–7 Janua y 2014; pp. 946–957. [C ossRe ] 21. Nguyen, H.T.; Thai, M.T.; Dinh, T.N. S op-and-S a e: Op imal Sampling Algo i hms o Vi al Ma ke ing in Billion-scale Ne wo ks. In P oceedings o he 2016 In e na ional Con e ence on Managemen o Da a, SIGMOD Con e ence 2016, San F ancisco, CA, USA, 26 June–1 July 2016; pp. 695–710. [C ossRe ] 22. Chen, W.; Yuan, Y.; Zhang, L. Scalable In luence Maximiza ion in Social Ne wo ks unde he Linea Th eshold Model. In P oceedings o he ICDM 2010, he 10 h IEEE In e na ional Con e ence on Da a Mining, Sydney, Aus alia, 14–17 Decembe 2010; pp. 88–97. [C ossRe ] 23. Bozo gi, A.; Same , S.; Kwis hou , J.; Wa eham, T. Communi y-based in luence maximiza ion in social ne wo ks unde a compe i i e linea h eshold model. Knowl.-Based Sys . 2017,134, 149–158. [C ossRe ] 24. Bo odin, A.; Filmus, Y.; O en, J. Th eshold Models o Compe i i e In luence in Social Ne wo ks. In P oceedings o he In e ne and Ne wo k Economics—6 h In e na ional Wo kshop, WINE 2010, S an o d, CA, USA, 13–17 Decembe 2010; pp. 539–550. [C ossRe ] 25. Tang, J.; Tang, X.; Xiao, X.; Yuan, J. Online P ocessing Algo i hms o In luence Maximiza ion. In P oceedings o he 2018 In e na ional Con e ence on Managemen o Da a, SIGMOD Con e ence 2018, Hous on, TX, USA, 10–15 June 2018; Das, G., Je maine, C.M., Be ns ein, P.A., Eds.; pp. 991–1005. [C ossRe ] 26. Ak am, M.; Za a , F. Hyb id So Compu ing Models Applied o G aph Theo y. In S udies in Fuzziness and So Compu ing; Sp inge : Cham, Swi ze land, 2020; Volume 380. [C ossRe ] 27. Ak am, M.; Luqman, A. Fuzzy Hype g aphs and Rela ed Ex ensions. In S udies in Fuzziness and So Compu ing; Sp inge : Singapo e, 2020; Volume 390. [C ossRe ] 28. Li, Y.; Zhang, D.; Tan, K. Ta ge ed In luence Maximiza ion o Online Ad e isemen s. PVLDB 2015,8, 1070–1081. 29. Ba bie i, N.; Bonchi, F.; Manco, G. Topic-awa e social in luence p opaga ion models. Knowl. In . Sys . 2013 ,37, 555–584. [C ossRe ] 30. Chen, S.; Fan, J.; Li, G.; Feng, J.; Tan, K.; Tang, J. Online Topic-Awa e In luence Maximiza ion. PVLDB 2015 ,8, 666–677. [C ossRe ] 31. Li, G.; Chen, S.; Feng, J.; Tan, K.L.; Li, W.-S. E icien Loca ion-Awa e In luence Maximiza ion. In P oceedings o he 34 h IEEE In e na ional Con e ence on Da a Enginee ing, ICDE 2018, Pa is, F ance, 16–19 Ap il 2018; pp. 1569–1572. 32. Wang, X.; Zhang, Y.; Zhang, W.; Lin, X. E icien Dis ance-Awa e In luence Maximiza ion in Geo-Social Ne wo ks. IEEE T ans. Knowl. Da a Eng. 2017,29, 599–612. [C ossRe ] 33. Bha a hi, S.; Kempe, D.; Salek, M. Compe i i e In luence Maximiza ion in Social Ne wo ks. In P oceedings o he In e ne and Ne wo k Economics, Thi d In e na ional Wo kshop, WINE 2007, San Diego, CA, USA, 12–14 Decembe 2007; pp. 306–311. [C ossRe ] 34. Chen, W.; Lu, W.; Zhang, N. Time-C i ical In luence Maximiza ion in Social Ne wo ks wi h Time-Delayed Di usion P ocess. In P oceedings o he Twen y-Six h AAAI Con e ence on A i icial In elligence, To on o, ON, Canada, 22–26 July 2012; pp. 592–598. 35. Nguyen, H.; Zheng, R. On Budge ed In luence Maximiza ion in Social Ne wo ks. IEEE J. Sel. A eas Commun. 2013 ,31, 1084–1094. [C ossRe ] 36. Goyal, A.; Bonchi, F.; Lakshmanan, L.V.S.; Venka asub amanian, S. On minimizing budge and ime in in luence p opaga ion o e social ne wo ks. Soc. Ne w. Anal. Min. 2013,3, 179–192. [C ossRe ] 37. Cohen, E.; Delling, D.; Pajo , T.; We neck, R.F. Ske ch-Based In luence Maximiza ion and Compu a ion: Scaling Up wi h Gua an- ees. In P oceedings o he 23 d ACM In e na ional Con e ence on Con e ence on In o ma ion and Knowledge Managemen , Shangai, China, 3–7 No embe 2014; pp. 629–638. [C ossRe ] 38. Goyal, A.; Lu, W.; Lakshmanan, L.V. CELF++: Op imizing he G eedy Algo i hm o In luence Maximiza ion in Social Ne wo ks. In P oceedings o he 20 h In e na ional Con e ence Companion on Wo ld Wide Web, New Yo k, NY, USA, 28 Ma ch 2011; pp. 47–48. 39. Chung, F.R.K.; Lu, L. Su ey: Concen a ion Inequali ies and Ma ingale Inequali ies: A Su ey. In e ne Ma h. 2006 ,3, 79–127. [C ossRe ] Ma hema ics 2022,10, 876 18 o 18 40. Sachde a, S.; Vishnoi, N.K. App oxima ion Theo y and he Design o Fas Algo i hms. a Xi 2013, a Xi :1309.4882. 41. Lesko ec, J.; Kleinbe g, J.M.; Falou sos, C. G aph e olu ion: Densi ica ion and sh inking diame e s. TKDD 2007 ,1, 2. [C ossRe ] 42. Lesko ec, J.; Lang, K.J.; Dasgup a, A.; Mahoney, M.W. Communi y S uc u e in La ge Ne wo ks: Na u al Clus e Sizes and he Absence o La ge Well-De ined Clus e s. In e ne Ma h. 2009,6, 29–123. [C ossRe ] 43. Chen, W.; Wang, Y.; Yang, S. E icien in luence maximiza ion in social ne wo ks. In P oceedings o he KDD ’09 15 h ACM SIGKDD In e na ional Con e ence on Knowledge Disco e y and Da a Mining, Pa is, F ance, 28 June–1 July 2009; pp. 199–208. [C ossRe ] 44. Lesko ec, J.; Adamic, L.A.; Hube man, B.A. F om Compe i ion o Complemen a i y: Compa a i e In luence Di usion and Maximiza ion. a Xi 2015, a Xi :1507.00317. 45. Yang, J.; Lesko ec, J. De ining and E alua ing Ne wo k Communi ies based on G ound- u h. Knowl. In . Sys . 2015 ,42, 181–213. [C ossRe ]