

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 ]