D:\TeX_522\04_pogh.DVI


Mathematical Problems of Computer Science 52, 30{42, 2019.

U D C 5 1 9 .1

Rumor Spr eading and I nvasion P er colation

S u r e n S . P o g h o s ya n a n d V a h a g n S . P o g h o s ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: psuren55@yandex.ru, povahagn@gmail.com

Abstract

We study the models of rumor spreading and invasion bond percolation aimed at
the revelation of possible connections between them. Rumor spreading model describes
the dissemination of a rumor due to the periodical repetition of sequential phone calls,
whereas the invasion bond percolation refers to the spread of liquid in the porous
environment. During a round of the rumor spreading, each node performs a call only
once, meanwhile transmitting all the information that it knows at the moment of the
call to its neighbors. The rumor reaches the receiver node during one round if there
is a chain of successive calls between the source of the rumor and that node. The
sequence of calls is taken uniformly at random from the set of all possible sequences
(permutations of nodes). We compare the propagation of the rumor spreading with
the invasion bond percolation in order to put forth necessary improvements of the
percolation rules to map one model onto another, and vice versa.

Keywords: Gossip problem, Information dissemination, Invasion percolation.

1 . In t r o d u c t io n a n d Mo d e ls

Th e s p r e a d in g o f r u m o r s a n d in va s io n p e r c o la t io n a r e c o r e p r o b le m s in t wo d i®e r e n t ¯ e ld s :
t h e t h e o r y o f d is s e m in a t io n o f in fo r m a t io n [1 ]{ [1 7 ] a n d t h e t h e o r y o f ° o w in a p o r o u s m e d ia
[1 8 ]{ [2 3 ]. B o t h p r o b le m s c o n c e r n wit h t h e s t o c h a s t ic g r o wt h o f c lu s t e r s : t h e c lu s t e r o f
in fo r m e d in d ivid u a ls in t h e ¯ r s t c a s e a n d t h e c lu s t e r o f in va d e d s it e s in t h e s e c o n d o n e .
H e r e , we c o n s id e r t wo m o d e ls t yp ic a l fo r e a c h p r o b le m a n d e s t a b lis h a lin k b e t we e n t h e m .

A m o n g t h e va r ie t y o f fo r m u la t io n s o f t h e ¯ r s t p r o b le m , we c h o o s e t h e r a n d o m p h o n e c a ll
m o d e l [1 9 ] d e ¯ n e d o n t h e s o c a lle d c o m m u n ic a t io n g r a p h G ( V; E ) wit h t h e s e t o f ve r t ic e s V
a n d t h e s e t o f e d g e s E. V e r t ic e s V d e n o t e t h e s e t o f p la ye r s , t h e e d g e s E d e n o t e p o s s ib le
c o n n e c t io n s b e t we e n t h e p la ye r s b y p h o n e c a lls . W h e n e ve r a c o n n e c t io n is e s t a b lis h e d , t h e
r u m o r c a n b e t r a n s m it t e d fr o m o n e p la ye r ( if s h e h o ld s t h e r u m o r ) t o a n o t h e r p la ye r ( if s h e
d o e s n o t h o ld t h e r u m o r ye t ) . In [1 9 ], t h e a u t h o r s c o n s id e r e d t h e m o d e l wh e r e t h e p la ye r s
c o m m u n ic a t e in parallel d u r in g c o m m u n ic a t io n r o u n d s . It m e a n s t h a t a n y in fo r m a t io n r e -
c e ive d in a r o u n d c a n n o t b e fo r wa r d e d t o a n o t h e r p la ye r in t h e s a m e r o u n d . Th e a im is t o
s p r e a d a ll r u m o r s fr o m a ll p la ye r s t o o t h e r s . Th e p r o b le m wa s t o ¯ n d a n a lg o r it h m u s in g
o n ly O ( ln jV j) r o u n d s a n d O ( jEj ln ln jEj ) c a lls .

3 0



Su. Poghosyan and V. Poghosyan 3 1

In t h is p a p e r , we c o n c e n t r a t e o n kin e t ic s o f t h e r u m o r p r o p a g a t io n o n t h e c o m m u n ic a t io n
g r a p h G ( V; E ) . To t h is e n d , we in ve s t ig a t e t h e e ®e c t o f sequential c o m m u n ic a t io n s wh e n a
r u m o r c a n b e t r a n s la t e d t h r o u g h a c h a in o f r a n d o m c a lls d u r in g o n e r o u n d . Co r r e s p o n d in g ly,
e a c h r o u n d in o u r m o d e l is a ¯ n it e t im e in t e r va l c o n t a in in g a ll p o s s ib le c o n n e c t io n s ei 2 E; i =
1 ; 2 ; : : : ; jEj, wh ic h h a p p e n e xa c t ly o n c e a t m o m e n t s t ( i) , wh e r e t( i ) ´ t( ei ) is t h e m o m e n t
o f c o n n e c t io n ei in t h e c u r r e n t r o u n d . W e a s s u m e t h a t a ll m o m e n t s t( i ) ; i = 1 ; 2 ; : : : ; jEj a r e
d is t in c t a n d u n ifo r m ly d is t r ib u t e d b e t we e n t h e b e g in n in g a n d t h e e n d o f e a c h r o u n d . Th e
e ®e c t o f s e qu e n t ia l c o m m u n ic a t io n s le a d s t o a s p e c i¯ c p a t t e r n o f t h e c lu s t e r g r o wt h , wh ic h is
s im ila r t o t h e in va s io n p e r c o la t io n . H o we ve r , t h e r u le s o f g r o wt h o f t h e c lu s t e r s o f in fo r m e d
p la ye r s a n d in va d e d s it e s in t h e p e r c o la t io n p r o b le m a r e n o t c o m p le t e ly id e n t ic a l.

L e t v¤ 2 V b e a ¯ xe d p la ye r wh o is t h e o r ig in o f t h e r u m o r a n d P = ( p1; p2; : : : ; pjEj ) is
a p e r m u t a t io n o f n u m b e r s ( 1 ; 2 ; : : : ; jEj ) s u c h t h a t t( p1 ) < t ( p2 ) < ¢ ¢ ¢ < t( pjEj ) in t h e ¯ r s t
r o u n d . D e n o t in g b y eij 2 E t h e e d g e c o n n e c t in g a d ja c e n t ve r t ic e s i 2 V a n d 8 j 2 V , we
d e ¯ n e a n o r d e r e d p a t h b e t we e n t h e ve r t ic e s i1 2 V a n d ik 2 V a s t h e s e qu e n c e o f c o n n e c t io n s
ei1i2; ei2i3 ; : : : ; eik¡1ik . Th e p a t h b e t we e n i1 a n d ik c o n d u c t s t h e r u m o r if t ( ei1i2 ) < t ( ei2i3 ) <
¢ ¢ ¢ < t( eik¡1ik ) . Give n t h e p e r m u t a t io n o f c a lls P , we will s a y t h a t t h e r u m o r s t a r t e d fr o m
v¤ r e a c h e s p la ye r v 2 V in t h e ¯ r s t r o u n d if t h e r e e xis t s a c o n d u c t in g p a t h b e t we e n v¤ a n d
v.

Th e s u b s e t V1 ½ V o f ve r t ic e s r e a c h a b le fr o m v¤ d u r in g t h e ¯ r s t r o u n d r e p r e s e n t s t h e
s e t o f p la ye r s g e t t in g in fo r m e d d u e t o p e r m u t a t io n o f c a lls P . Th e qu a n t it y o f in t e r e s t is
t h e n u m b e r o f in fo r m e d p la ye r s jV1jP a n d it s a ve r a g e t a ke n o ve r a ll p e r m u t a t io n s hjV1ji =P

P
jV1jP P robjV1jP . A c o n d u c t in g p a t h b e t we e n t wo a r b it r a r y ve r t ic e s is n o t n e c e s s a r ily s e lf-

a vo id in g . In d e e d , t h e p a t h m a y c o n t a in o n e o r m o r e lo o p s , wh ic h a p p e a r if b o t h a d ja c e n t
ve r t ic e s i a n d j in c o n n e c t io n eij b e lo n g in g t o t h e p a t h a r e a lr e a d y in fo r m e d b e fo r e t h e
m o m e n t t( eij ) . W e c a n c o in s u c h a c o n n e c t io n a s non-informative in c o n t r a s t t o a informative
c o n n e c t io n t h a t c o n d u c t s t h e r u m o r . Th e e xc lu s io n o f n o n -in fo r m a t ive c o n n e c t io n s fr o m a ll
c o n d u c t in g p a t h s r e m o ve s a ll p o s s ib le lo o p s . Th e n , t h e r e m a in in g in fo r m a t ive c o n n e c t io n s
fo r m a c o n n e c t e d g r a p h , wh ic h is a t r e e s p a n n in g t h e s u b s e t o f in fo r m e d p la ye r s V1 a n d is
r o o t e d a t v¤. B y d e ¯ n it io n , t h e ¯ r s t r o u n d is c o m p le t e if a ll p o s s ib le c o n n e c t io n s ei 2 E; i =
1 ; 2 ; : : : ; jEj h a p p e n e d e xa c t ly o n c e . A lt e r n a t ive ly, we c a n s a y t h a t t h e r o u n d is c o m p le t e
o n ly if s u b s e t V1 c o n t a in s a ll p o s s ib le ve r t ic e s r e a c h a b le fr o m v

¤ fo r t h e g ive n p e r m u t a t io n
P .

W h e n t h e ¯ r s t r o u n d is o ve r , t h e n e xt r o u n d s s t a r t c o n s e c u t ive ly wit h t h e s a m e s e qu e n c e
o f c o n n e c t io n s t ( i ) ; i = 1 ; 2 ; : : : ; jEj. P la ye r s r e c e ivin g t h e r u m o r in t h e ¯ r s t r o u n d c a n
s e r ve a s o r ig in s o f t h e s a m e r u m o r fo r t h e s e c o n d r o u n d . A s a b o ve , t h e r u m o r is s p r e a d in g
a lo n g t h e c o n d u c t in g p a t h s s t a r t e d a t t h e b o u n d a r y ve r t ic e s o f s u b s e t V1. ( A s u s u a l, we c a ll
a ve r t e x v 2 V t h e b o u n d a r y ve r t e x o f a s u b s e t V1 ½ V if v 2 V1 a n d a t le a s t o n e o f t h e
n e a r e s t n e ig h b o r s o f v in g r a p h G ( V; E ) d o e s n o t b e lo n g t o V1 ) . Th e c o lle c t io n o f in fo r m a t ive
c o n n e c t io n s in t h e s e c o n d r o u n d fo r m s a g r a p h , wh ic h is a fo r e s t wit h r o o t s a t t h e b o u n d a r y
ve r t ic e s o f V1. Th e fo r e s t s p a n s t h e s u b s e t o f p la ye r s V2 b e in g in fo r m e d d u r in g t h e s e c o n d
c o m p le t e r o u n d .

Co n t in u in g t h e p r o c e s s r o u n d b y r o u n d , we o b t a in a s e qu e n c e o f s u b s e t s o f p la ye r s Vi; i =
1 ; 2 ; : : : c h a r a c t e r iz e d b y t h e s iz e jVijP a n d t h e a ve r a g e s iz e hjViji fo r e a c h r o u n d a n d b y t h e
a ve r a g e c o r r e la t io n s b e t we e n t h e r o u n d s . Th e p r o c e s s is ¯ n is h e d wh e n a ll p la ye r s V b e c o m e
in fo r m e d wit h t h e r u m o r . Th e qu e s t io n is t h e a ve r a g e n u m b e r o f r o u n d s n e e d e d fo r t h e t o t a l
s p r e a d in g o f t h e r u m o r .

Th e a s s o c ia t e d p r o b le m , in va s io n p e r c o la t io n , h a s m a n y fo r m u la t io n s a s we ll [2 0 ]. W e



3 2 Rumor Spreading and Invasion Percolation

c h o o s e fr o m t h e m a p o p u la r ve r s io n , n a m e ly, t h e in va s io n b o n d p e r c o la t io n m o d e l [2 1 ].
S im ila r t o t h e ¯ r s t p r o b le m , we s t a r t wit h t h e g r a p h G ( V; E ) wit h s e t s o f ve r t ic e s a n d e d g e s
V a n d E. W e a s s ig n r a n d o m n u m b e r s pij 2 [0 ; 1 ] t o e a c h e d g e eij 2 E. In va s io n p e r c o la t io n
is a p r o c e s s o f s u c c e s s ive o c c u p a t io n o f t h e ve r t ic e s a n d e d g e s o f G ( V; E ) . A t t h e ¯ r s t s t e p ,
o n e o c c u p ie s a r a n d o m ly c h o s e n ve r t e x v¤ 2 V . Th e n , o n e c o n s id e r s a ll e d g e s a d ja c e n t t o
v¤ a n d o c c u p ie s t h e e d g e wit h t h e s m a lle s t pij t o g e t h e r wit h t h e s e c o n d ve r t e x b e lo n g in g t o
it . A t s u b s e qu e n t s t e p s , o n e ¯ n d s t h e e m p t y e d g e wit h t h e s m a lle s t pij c o n n e c t e d t o t h e
o c c u p ie d ve r t ic e s , a n d c h e c ks wh e t h e r t h is e d g e c o n n e c t s t wo o c c u p ie d ve r t ic e s o r n o t . In
t h e fo r m e r c a s e , t h e e d g e is c a lle d trapped s in c e it is s it u a t e d b e t we e n t wo o c c u p ie d ve r t ic e s .
If t h e e d g e is n o t t r a p p e d , it b e c o m e s o c c u p ie d t o g e t h e r wit h t h e e m p t y ve r t e x it c o n n e c t s
wit h t h e o c c u p ie d c lu s t e r . In t h is wa y, o n e c o n s t r u c t s a g r a p h o f o c c u p ie d e d g e s a n d ve r t ic e s
T ½ G( V; E ) , wh ic h is a t r e e s p a n n in g t h e c lu s t e r o f o c c u p ie d ve r t ic e s a t t h e g ive n s t a g e .

Th e d e s c r ib e d m o d e l wa s in t r o d u c e d b y B a r a b a s i [2 2 ] a n d c a lle d t h e in va s io n b o n d p e r c o -
la t io n m o d e l wit h a lo c a l t r a p p in g r u le t o d is t in g u is h it fr o m t h e o r d in a r y in va s io n b o n d p e r -
c o la t io n wh e r e t h e t r a p p e d e d g e s c a n b e o c c u p ie d a s we ll a s t h e n o n -t r a p p e d o n e s . B a r a b a s i
p r o ve d t h a t t h e t r a p p in g r u le d o e s n o t a ®e c t t h e s c a lin g a n d d yn a m ic p r o p e r t ie s o f g r o win g
c lu s t e r s o f o c c u p ie d ve r t ic e s a n d ,t h e r e fo r e , t h e t wo m o d e ls b e lo n g t o t h e s a m e u n ive r s a lit y
c la s s . Mo r e o ve r , t h e c o n s t r u c t io n o f t r e e T in t h e B a r a b a s i's m o d e l c o in c id e s wit h t h e P r im 's
a lg o r it h m fo r ¯ n d in g t h e s h o r t e s t s p a n n in g t r e e o f a we ig h t e d r a n d o m g r a p h [2 3 ]. In t h e
n e xt s e c t io n , we c o n s id e r a m o d ī c a t io n o f t h e P r im 's a lg o r it h m t o m a p it in t o t h e m o d e l
o f t r a n s m is s io n o f r u m o r s . Th e s u b s e qu e n t s e c t io n s will b e d e vo t e d t o t h e e xa c t s o lu t io n s
o f t h e la t t e r m o d e l fo r s im p li¯ e d g r a p h s G ( V; E ) a n d t h e c o m p a r is o n o f c lu s t e r g r o wt h in
m o d e ls o f t r a n s m is s io n o f r u m o r s a n d t h e in va s io n b o n d p e r c o la t io n .

2 . Th e Mo d i¯ e d Mo d e l o f In va s io n P e r c o la t io n

Th e m a in d i®e r e n c e b e t we e n t h e m o d e ls o f t r a n s m is s io n o f r u m o r s a n d t h e in va s io n b o n d
p e r c o la t io n is t h e m o n o t o n ic c h a r a c t e r o f t h e in va s io n p r o c e s s , wh ic h is n o t s u b d ivid e d in t o
¯ n it e t im e p e r io d s a p p e a r in g in t h e p r o p a g a t io n o f r u m o r s . Th e in va s io n p r o c e s s c o n t in u e s
p e r m a n e n t ly a n d s t o p s wh e n a ll ve r t ic e s o f g r a p h G( V; E ) b e c o m e o c c u p ie d . Th e p r o p a g a t io n
o f r u m o r s is in t e r m it t e d a t t h e e n d o f e a c h c o m p le t e r o u n d wh e n a ll p la ye r s r e a c h a b le fo r
t h e g ive n p e r m u t a t io n o f c a lls b e c o m e in fo r m e d . To e lim in a t e t h e d i®e r e n c e , we in t r o d u c e a
m o d i¯ e d m o d e l o f in va s io n p e r c o la t io n ( o r a m o d ī e d P r im 's a lg o r it h m ) .

A s b e fo r e , we b e g in wit h t h e g r a p h G ( V; E ) a n d t h e s e t o f r a n d o m we ig h t s p ( i; j ) 2 [0 ; 1 ]
a s s ig n e d t o e a c h e d g e eij 2 E. A g a in , we c h o o s e a ve r t e x v¤ 2 V a n d c o n s id e r it a s t h e
s t a r t in g p o in t o f a g r o win g c lu s t e r . Th e c lu s t e r g r o ws b y s u c c e s s ive a d d in g n e w o c c u p ie d
e d g e s . Th e o c c u p a t io n o f e d g e eij m e a n s t h e o c c u p a t io n o f a d ja c e n t ve r t ic e s i a n d j a s we ll.
Th e a d d it io n p r o c e s s yie ld s t wo r e s t r ic t io n s :

( a ) E a c h n e w e d g e we a r e g o in g t o o c c u p y c o n n e c t s t wo ve r t ic e s , o n e o f wh ic h b e lo n g s
t o t h e c lu s t e r a n d t h e o t h e r d o e s n o t .

Th is r u le g u a r a n t ie s t h a t t h e g r o win g c lu s t e r is a t r e e . Of t wo c o n n e c t e d e d g e s o f t h e
t r e e , we c a ll a predecessor t h e e d g e t h a t is c lo s e r t o t h e s t a r t in g p o in t . Th e o t h e r e d g e is t h e
successor.

( b ) E a c h n e w o c c u p ie d e d g e b e in g a s u c c e s s o r , h a s t h e we ig h t la r g e r t h a n it s p r e d e c e s s o r .
Th e e d g e s yie ld in g b o t h r u le s ( a ) a n d ( b ) a r e c a lle d e lig ib le fo r t h e g r o wt h . Th e m o d i¯ e d

m o d e l o f in va s io n p e r c o la t io n is d e ¯ n e d b y t h e fo llo win g s t e p s . Th e ¯ r s t s t e p is t h e o c c u p a t io n
o f t h e s t a r t in g ve r t e x v¤. Give n a c o n n e c t e d c lu s t e r o f e d g e s a n d ve r t ic e s C ( i ) o b t a in e d a ft e r



Su. Poghosyan and V. Poghosyan 3 3

i s t e p s , i = 1 ; 2 ; : : : , we s e le c t t h e s e t o f e d g e s E ( i ) e lig ib le fo r t h e g r o wt h ( fo r e d g e s a d ja c e n t
t o t h e s t a r t in g p o in t , t h e r u le ( b ) is o m it t e d ) . Ch o o s e in t h e s e t E ( i ) t h e e d g e eij wit h
m in im a l we ig h t p ( i; j ) a n d a d d it t o t h e c lu s t e r o f o c c u p ie d e d g e s a n d ve r t ic e s . In t h is wa y,
we o b t a in t h e c lu s t e r C ( i + 1 ) .

If, a ft e r s o m e n u m b e r o f s t e p s i1, t h e r e a r e n o e d g e s e lig ib le fo r g r o wt h , we ¯ x t h e c lu s t e r
C ( i1 ) a n d s t a r t t h e n e xt r o u n d o f g r o wt h . To t h is e n d , we t a ke t h e s a m e s e t o f r a n d o m
we ig h t s p ( i; j ) 2 [0 ; 1 ] a n d c o n s id e r t h e b o u n d a r y ve r t ic e s o f t h e s e t C ( i1 ) a s t h e s t a r t in g
p o in t s fo r t h e n e xt r o u n d . Th e c lu s t e r o f e d g e s a n d ve r t ic e s o b t a in e d a ft e r i-t h s t e p o f
t h e s e c o n d r o u n d is d e n o t e d b y C ( i1; i ) . Fo r e a c h s t e p o f t h e s e c o n d r o u n d , we d e ¯ n e t h e
s e t E ( i1; i) o f e d g e s e lig ib le fo r g r o wt h a n d c h o o s e a m o n g t h e m t h e e d g e eij wit h m in im a l
we ig h t p( i; j ) . Th e s e c o n d r o u n d c o n t in u e s d u r in g a n u m b e r o f s t e p s i2 u n t il o n e is a b le t o ¯ n d
e d g e s e lig ib le fo r g r o wt h . Th e s e t o f e d g e s a n d ve r t ic e s o c c u p ie d d u r in g t h e s e c o n d r o u n d is
C ( i1; i2 ) . Th e p r o c e s s p r o c e e d s r o u n d b y r o u n d u n t il t h e s e t o f ve r t ic e s in C ( i1; i2; : : : ; imax )
c o in c id e s wit h t h a t in G( V; E ) .

W e g e t a m o d i¯ e d m o d e l o f in va s io n b o n d p e r c o la t io n d is p la yin g a n in t e r m it t e n c e o f t h e
in va s io n p r o c e s s . In o r d e r t o g e t t h e c o r r e s p o n d e n c e b e t we e n t h e in t r o d u c e d m o d e l a n d t h e
r a n d o m c a ll m o d e l, we r e s t r ic t t h e le n g t h o f e a c h r o u n d in t h e la t t e r m o d e l t o t h e u n it t im e
in t e r va l. Th e n , we c a n id e n t ify t h e m o m e n t s o f c a lls t ( i) ; i = 1 ; 2 ; : : : ; jEj wit h t h e r a n d o m
n u m b e r s pij 2 [0 ; 1 ] a s s ig n e d t o e a c h e d g e eij 2 E. Th e c o n d it io n t h a t a ll pij a r e d is t in c t is
n o t e s s e n t ia l s in c e pij a r e c o n t in u o u s va r ia b le s . Th e c o n d it io n o f c o m p le t e n e s s o f e a c h r o u n d
is id e n t ic a l fo r b o t h m o d e ls if o n e t a ke s in t o a c c o u n t t h e a b ilit y o f a c lu s t e r t o g r o w d u r in g
t h e r o u n d .

3 . Th e On e -d im e n s io n a l L a t t ic e

In t h is s e c t io n , we illu s t r a t e t h e c o n s id e r e d m o d e ls wit h a s im p lī e d e xa m p le , wh e r e t h e
c o m m u n ic a t io n g r a p h G( V; E ) is a ¯ n it e o n e -d im e n s io n a l la t t ic e . Th e s e t o f ve r t ic e s V ½ Z
r e p r e s e n t in g t h e p la ye r s c o n s is t s o f L + 1 la t t ic e p o in t s i 2 V; i = 1 ; 2 ; : : : ; L + 1 . Th e s e t
o f e d g e s E r e p r e s e n t s L c o n n e c t io n s ej 2 E b e t we e n t h e n e ig h b o r in g ve r t ic e s j a n d j + 1 ,
j = 1 ; 2 ; : : : ; L.

Th e o r ig in o f t h e r u m o r is t h e ¯ r s t p la ye r i = 1 , a n d t ( j ) ´ t ( ej ) a r e t h e m o m e n t s o f c a lls
u s e d b y t h e c o n n e c t io n s ej; j = 1 ; 2 ; : : : ; L. Th e o r d e r o f c a lls c o r r e s p o n d s t o t h e p e r m u t a t io n
P = ( p1; p2; : : : ; pL ) s u c h t h a t t( p1 ) < t( p2 ) < ¢ ¢ ¢ < t( pL ) . Th e r u m o r r e a c h e s t h e p la ye r
k1 + 1 d u r in g t h e ¯ r s t r o u n d a n d d o e s n o t p r o p a g a t e fu r t h e r if

t ( 1 ) < t( 2 ) < ::: < t ( k1 ) ; t ( k1 ) > t ( k1 + 1 ) : ( 1 )

Co n s id e r k1 + 1 n u m b e r s t ( 1 ) ; t ( 2 ) ; : : : ; t ( k1 + 1 ) . A m o n g ( k1 + 1 ) ! p e r m u t a t io n s o f t h e s e
n u m b e r s , o n ly o n e is o r d e r e d a s

t ( 1 ) < t( 2 ) < ::: < t ( k1 ) < t( k1 + 1 ) ( 2 )

wit h p r o b a b ilit y 1 =( k1 + 1 ) !. Th e o r d e r ( 2 ) c a n b e b r o ke n a n d c o n ve r t e d in t o ( 1 ) in k1 wa ys
b y r e p la c in g a n y o f k1 ¯ r s t n u m b e r s wit h t( k1 + 1 ) . Th e r e fo r e , t h e p r o b a b ilit y o f o r d e r ( 1 )
is k1 t im e s g r e a t e r t h a n t h a t o f ( 2 ) a n d we g e t

P rob ( k1 ) =
k1

( k1 + 1 ) !
: ( 3 )



3 4 Rumor Spreading and Invasion Percolation

Th e r u m o r r e a c h e s t h e p la ye r k1 + 1 d u r in g t h e ¯ r s t r o u n d a n d t h e p la ye r k1 + k2 + 1
d u r in g t h e s e c o n d r o u n d b u t d o e s n o t p r o p a g a t e fu r t h e r if

t( 1 ) < t ( 2 ) < ¢ ¢ ¢ < t( k1 ) ; t( k1 + 1 ) < t( k1 + 2 ) < ¢ ¢ ¢ < t ( k1 + k2 )

b u t

t ( k1 ) > t( k1 + 1 ) ; t ( k1 + k2 ) > t( k1 + k2 + 1 )

To ¯ n d t h e p r o b a b ilit y P rob( k1; k2 ) , o n e h a s t o e xc lu d e P rob ( k1 + k2 ) fr o m t h e p r o d u c t o f
t wo p r o b a b ilit ie s 1 =k1! a n d P rob ( k2 ) :

P rob( k1; k2 ) =
k2

k1!( k2 + 1 ) !
¡ k1 + k2

( k1 + k2 + 1 ) !
:

Th e c a lc u la t io n o f fu r t h e r p r o b a b ilit ie s P rob ( k1; k2; : : : ; kn ) is a d ir e c t a p p lic a t io n o f t h e
in c lu s io n -e xc lu s io n p r in c ip le . Fo r in s t a n c e ,

P rob ( k1; k2; k3 ) = k3= ( k1!k2!( 1 + k3 ) !) ¡ k3=( ( k1 + k2 ) !( 1 + k3 ) !) ¡
( k2 + k3 ) = ( k1!( 1 + k2 + k3 ) !) + ( k1 + k2 + k3 ) =( 1 + k1 + k2 + k3 ) !

K n o win g t h e p r o b a b ilit ie s P rob( k1; k2; : : : ; ki ) , we c a n c a lc u la t e t h e e xp e c t e d va lu e s hkii in
t h e lim it L ! 1:

hkii =
1X

k1=1;:::;ki=1

kiP rob ( k1; k2; : : : ; ki )

Th e ¯ r s t s e ve r a l r e s u lt s a r e :

hk1i = e ¡ 1

hk2i = e2 ¡ 2 e

hk3i =
3 e

2
¡ 3 e2 + e3

hk4i = ¡
2 e

3
+ 4 e2 ¡ 4 e3 + e4

hk5i =
5 e

2 4
¡ 1 0 e

2

3
+

1 5 e3

2
¡ 5 e4 + e5

t h e n u m e r ic a l va lu e s o f wh ic h a r e :

hk1i = 1 : 7 1 8 2 8 1 8 2 8 : : :
hk2i = 1 : 9 5 2 4 9 2 4 4 2 : : :
hk3i = 1 : 9 9 5 7 9 1 3 6 9 : : :
hk4i = 2 : 0 0 0 0 3 8 8 5 0 : : :
hk5i = 2 :0 0 0 0 5 7 5 7 8 : : :



Su. Poghosyan and V. Poghosyan 3 5

On e c a n e xp e c t t h a t hkni ! 2 wh e n n ! 1. To p r o ve t h is c o n je c t u r e , it is s u ± c ie n t t o ¯ n d
t h e g e n e r a t in g fu n c t io n ( s e e A p p e n d ix )

R( x ) =
1X

m=1

hkmixm =
1 ¡ x

1 ¡ x e xp ( 1 ¡ x)

a n d ve r ify t h a t

R ( x) » 2 =( 1 ¡ x) + O ( x ¡ 1 )
in t h e vic in it y o f t h e p o in t x = 1 .

4 . Co n c lu s io n

In o u r wo r ks [2 4 ]{ [2 9 ], t o p p lin g o f g r a in s a t n o d e s ( g r a p h ve r t ic e s in A b e lia n s a n d p ile m o d e l)
wa s in t e r p r e t e d a s a t r a n s m is s io n o f t h e fu ll in fo r m a t io n a c c u m u la t e d in a ve r t e x, a c t iva t e d
a t t h e m o m e n t , t o a ll it s n e ig h b o r s ( k-b r o a d c a s t ) . Ta kin g in t o a c c o u n t t h a t a c t iva t io n o f
ve r t ic e s is p e r fo r m e d a c c o r d in g t o a p r e d e ¯ n e d r a n d o m o r d e r , a n d a s in g le t im e t a c t is
d e ¯ n e d t o b e a d is c r e t e t im e in t e r va l ( e qu a l t o t h e n u m b e r o f ve r t ic e s ) o f a c t iva t io n o f a ll
t h e ve r t ic e s , it is n e c e s s a r y t o e s t im a t e t h e a ve r a g e n u m b e r o f t a c t s r e qu ir e d fo r t h e fu ll
in fo r m a t io n e xc h a n g e / t r a n s m is s io n .

Th e e xa c t fo r m u la fo r t h e a ve r a g e n u m b e r o f t a c t s fo r ( n; n) la t t ic e s h a s n o t ye t b e e n
d e r ive d . N e ve r t h e le s s , b a s e d o n t h e r e qu ir e d n u m b e r o f e xp e r im e n t a l d a t a , s t a t is t ic a l c u r ve s
o f t h e m a in c h a r a c t e r is t ic s h a ve b e e n o b t a in e d , t h e s t u d y o f wh ic h m a d e it p o s s ib le t o s e t u p
a h yp o t h e s is ( r e s e a r c h m e t h o d s a n d r e s u lt s a r e n o t in c lu d e d in t h is p a p e r ) t h a t t h e a ve r a g e
n u m b e r o f t a c t s is 0 : 2 5 n.

S t u d y o f t h e m o d e ls o f r u m o r s p r e a d in g a n d in va s io n b o n d p e r c o la t io n , a im e d a t t h e
r e ve la t io n o f p o s s ib le c o n n e c t io n s b e t we e n t h e m , is p e r fo r m e d . It is s h o wn t h a t t h e r u m o r
r e a c h e s t h e r e c e ive r n o d e d u r in g o n e r o u n d if t h e r e is a c h a in o f s u c c e s s ive c a lls b e t we e n t h e
s o u r c e o f t h e r u m o r a n d t h a t n o d e . Give n t h a t t h e s e qu e n c e o f c a lls is t a ke n u n ifo r m ly a t r a n -
d o m fr o m t h e s e t o f a ll p o s s ib le s e qu e n c e s , a n a lyt ic a l p r o p e r t ie s o f in fo r m a t io n d is s e m in a t io n
h a ve b e e n in ve s t ig a t e d .

Th e r e s u lt s o b t a in e d m a ke it p o s s ib le t o im p r o ve t h e p e r c o la t io n r u le s a im e d a t m a p p in g
o n e m o d e l o n t o a n o t h e r , a n d vic e ve r s a . Fu t u r e wo r k will b e d e d ic a t e d t o t h e c o m p a r a t ive
a n a lys is b e t we e n r u m o r s p r e a d in g a n d in va s io n b o n d p e r c o la t io n m o d e ls .

5 . A p p e n d ix

W e d e ¯ n e a s e t o f a ll p a r t it io n s P( fk1; k2; : : : ; kng) o f a s e t o f n in t e g e r s fk1; k2; : : : kng a s a
s e t o f t h e fo llo win g 2 n¡1 s u b s e t s

P( fk1g ) = ffk1gg

P ( fk1; k2g ) = f ffk1g; fk2gg; ffk1; k2gg g
In g e n e r a l, r e c u r s ive ly, if t h e s e t o f m s u b s e t s o f fk1; k2; : : : ; kng Si; i = 1 ; 2 ; : : : ; m, is a
p a r t it io n

fS1; S2; : : : ; Smg 2 P( fk1; k2; : : : ; kng ) ( 4 )



3 6 Rumor Spreading and Invasion Percolation

t h e n

fS1; S2; : : : ; Sm; fkn+1gg 2 P( fk1; k2; : : : ; kn+1g ) a n d
fS1; S2; : : : ; Sm¡1; Sm [ fkn+1gg 2 P( fk1; k2; : : : ; kn+1g ) ( 5 )

a r e a ls o p a r t it io n s . E a c h o f Si; i = 1 ; 2 ; : : : ; m in ( 4 ) a n d ( 5 ) is a s e t o f k in t e g e r s S =
fl1; l2; : : : ; lkg, wh e r e li 2 N, i = 1 ; 2 ; : : : ; k. W e d e n o t e jSj = k a n d kSk = l1 + l2 + ¢ ¢ ¢ +
lk. Th e n , ( u s in g t h e in c lu s io n -e xc lu s io n p r in c ip le ) , we o b t a in a s u m o ve r a ll e le m e n t s o f
P( fk1; k2; : : : ; kng ) :

P r o b ( k1; k2; : : : ; k n ) =

nX

m =1

X

fS 1; S 2;::: ; S mg2P(fk1;k2;::: ;kng)

( ¡ 1 ) n +m
k S 1k! k S 2k! ¢ ¢ ¢ k S m ¡1k!

kS m k
( kS m k + 1 ) !

:

Th e r e fo r e , t h e a ve r a g e va lu e o f kn is

hkni =
1X

k1=1

1X

k2=1

: : :
1X

kn=1

kn P r o b ( k1; k2; : : : ; k n )

=
nX

m=1

X

fS1;S2;::: ;Smg2P(f1;2;::: ;ng)
( ¡ 1 ) n+m®jS1j®jS2j ¢ ¢ ¢ ®jSmj; ( 6 )

wh e r e ®n; n > 0 is t h e n-fo ld s u m

®n =
1X

k1=1

1X

k2=1

¢ ¢ ¢
1X

kn=1

1

( k1 + k2 + ¢ ¢ ¢ + kn ) !
( 7 )

To c a lc u la t e ( 7 ) wit h n = 1 ; 2 ; : : : , we in t r o d u c e t h e g e n e r a t in g fu n c t io n

fn ( x ) =

1X

k1=1

1X

k2=1

¢ ¢ ¢
1X

kn=1

xk1+k2+¢¢¢+kn

( k1 + k2 + ¢ ¢ ¢ + kn ) !
:

Th e d e r iva t ive o f fn ( x) c a n b e e xp r e s s e d in t h e fo llo win g wa y

d fn ( x )

d x
=

1X

k1=1

1X

k2=1

¢ ¢ ¢
1X

kn=1

xk1+k2+¢¢¢+kn¡1

( k1 + k2 + ¢ ¢ ¢ + kn ¡ 1 ) !

=

1X

k1=1

1X

k2=1

¢ ¢ ¢
1X

kn¡1=1

1X

kn=0

xk1+k2+¢¢¢+kn

( k1 + k2 + ¢ ¢ ¢ + kn ) !
= fn ( x ) + fn¡1 ( x ) : ( 8 )

W e m u lt ip ly b o t h s id e s o f t h e r e c u r s ive d i®e r e n t ia l e qu a t io n ( 8 ) b y zn a n d t a ke t h e s u m o ve r
n = 2 ; 3 ; : : : . In t r o d u c in g t h e g e n e r a t in g fu n c t io n o f t h e s e qu e n c e o f fu n c t io n s fn ( x ) :

F ( z; x ) =
1X

n=1

fn ( x ) z
n;



Su. Poghosyan and V. Poghosyan 3 7

a n d t a kin g in t o a c c o u n t t h a t

f1 ( x ) ´
1X

k1=1

xk1

k1!
= ex ¡ 1 ;

we o b t a in a d i®e r e n t ia l e qu a t io n fo r F ( z; x ) :

@F ( z; x )

@x
= ( z + 1 ) F ( z; x) + z ( 9 )

wit h in it ia l c o n d it io n s F ( z; 0 ) = 0 . Th e s o lu t io n o f ( 9 ) is

F ( z; x) =
z

z + 1

¡
ex(z+1) ¡ 1

¢
;

wh ic h c a n b e e xp a n d e d o ve r va r ia b le s x a n d z:

F ( z; x) =

1X

k=1

z ( z + 1 ) k¡1

k!
xk =

1X

k=1

kX

n=1

xkzn

( n ¡ 1 ) !( k ¡ n) !k =
1X

n=1

1X

k=n

xkzn

( n ¡ 1 ) !( k ¡ n ) !k :

Th e r e fo r e ,

fn ( x) =
1

( n ¡ 1 ) !
1X

k=0

xn+k

k!( n + k )
=

1

( n ¡ 1 ) !
x

0

¿ n¡1e¿ ¿:

Th u s , we o b t a in a n e xa c t e xp r e s s io n fo r ®n

®n = fn ( 1 ) = ( ¡1 ) n + e
nX

p=1

( ¡ 1 ) n+p
( p ¡ 1 ) ! ;

wh ic h a llo ws o n e t o c a lc u la t e t h e va lu e s o f ®n fo r va r io u s n:

®1 = e ¡ 1 ; ®2 = 1 ; ®3 = 12 ( e ¡ 2 ) ;
®4 =

3¡e
3

; ®5 =
1
8
( 3 e ¡ 8 ) ; ®6 = 130 ( 3 0 ¡ 1 1 e) :

U s in g t h e fa c t t h a t

1

e
=

1X

p=0

( ¡ 1 ) p
p!

;

we o b t a in a n a lt e r n a t ive r e p r e s e n t a t io n o f ®n:

®n = e
1X

p=0

( ¡ 1 ) p
( p + n) !

=
e

n!
¡ e

( n + 1 ) !
+

e

( n + 2 ) !
¡ ¢ ¢ ¢ :

N o t e t h a t
e

n!
¡ e

( n + 1 ) !
< ®n <

e

n!
;

i.e .,
n

n + 1

e

n!
< ®n <

e

n!
:



3 8 Rumor Spreading and Invasion Percolation

Th e r e fo r e , t h e a s ym p t o t ic s o f ®n fo r la r g e n is

®n '
e

n!
; n À 1 :

N o w, we c a n r e wr it e t h e e xp r e s s io n ( 6 ) fo r hkni in t h e fo llo win g fo r m

hkni =
1X

¾1=0

1X

¾2=0

¢ ¢ ¢
1X

¾n=0

±

Ã
nX

i=1

i¾i; n

!
nY

i=1

¡
( ¡ 1 ) 1+i®i

¢¾i (
Pn

i=1 ¾i ) !

¾1! ¾2! ¢ ¢ ¢ ¾n!
:

Th e c o r r e s p o n d in g g e n e r a t in g fu n c t io n is

R ( x) = 1 +
1X

n=1

hknixn =
1X

¾1=0

1X

¾2=0

¢ ¢ ¢
à 1Y

i=1

( ( ¡ 1 ) 1+i®i )
¾i

¾i!

! Ã 1X

i=1

¾i

!
! x
P 1

i=1 i¾i :

To c a lc u la t e R( x ) , we in t r o d u c e a n o t h e r g e n e r a t in g fu n c t io n

D ( x; z ) =

1X

¾1=0

1X

¾2=0

¢ ¢ ¢
à 1Y

i=1

( ( ¡ 1 ) 1+i®i ) ¾i
¾i!

!
z
P 1

i=1 ¾i x
P 1

i=1 i¾i ;

wh ic h c a n b e r e wr it t e n a s

D ( x; z ) =
1Y

i=1

à 1X

¾=0

( ( ¡1 ) 1+i®i )
¾
z¾xi¾

¾!

!

=
1Y

i=1

e xp
©
( ¡ 1 ) 1+i®ixiz

ª

= e xp

(
z

1X

i=1

( ¡ 1 ) 1+i®ixi
)

Th e fu n c t io n D ( x; z ) is t h e s e r ie s

D ( x; z ) =
1X

p=0

G ( x) p

p!
zp;

wh e r e

G( x ) =

1X

i=1

( ¡1 ) 1+i®ixi

=
1X

i=1

Ã
¡ 1 + e

iX

j=1

( ¡ 1 ) j¡1
( j ¡ 1 ) !

!
xi

=
x

x ¡ 1 + e
1X

j=1

Ã
( ¡ 1 ) j¡1
( j ¡ 1 ) !

1X

i=j

xi

!

=
x

x ¡ 1 +
e

1 ¡ x
1X

j=1

( ¡ 1 ) j¡1xj
( j ¡ 1 ) !

=
x

x ¡ 1
¡
1 + e1¡x

¢



Su. Poghosyan and V. Poghosyan 3 9

On t h e o t h e r h a n d , t h e fu n c t io n R ( x) c a n b e e xp r e s s e d b y G( x ) :

R ( x ) =

1X

p=0

G( x ) p =
1

1 ¡ G ( x) =
1 ¡ x

1 ¡ xe1¡x :

R ( x ) ' 2
1 ¡ x + O ( x ¡ 1 )

Th e r e fo r e ,

lim
n!1

hkni = 2 :

References

[1 ] B . B a ke r a n d R . S h o s t a k, \ Go s s ip s a n d t e le p h o n e s " , D iscrete M ath., vo l. 2 , p p . 1 9 1 -1 9 3 ,
1 9 7 2 .

[2 ] R .T. B u m b y, \ A p r o b le m wit h t e le p h o n e s " , SIAM J . Alg. D isc. M eth. vo l. 2 , p p . 1 3 -1 8 ,
1 9 8 1 .

[3 ] A . H a jn a l, E .C. Miln e r a n d E . S z e m e r e d i, \ A c u r e fo r t h e t e le p h o n e d is e a s e " , Canad.
M ath. B ull., vo l. 1 5 , p p . 4 4 7 -4 5 0 , 1 9 7 6 .

[4 ] T. Tijd e m a n , \ On a t e le p h o n e p r o b le m " , Nieuw Arch. W isk., vo l. 3 , p p . 1 8 8 -1 9 1 , 1 9 7 1 .

[5 ] A . S e r e s s , \ Qu ic k g o s s ip in g b y c o n fe r e n c e c a lls " , SIAM J . D isc. M ath., vo l. 1 , p p .
1 0 9 -1 2 0 , 1 9 8 8 .

[6 ] D .B . W e s t , \ Go s s ip in g wit h o u t d u p lic a t e t r a n s m is s io n s " , SIAM J . Alg. D isc. M eth.,
vo l. 3 , p p . 4 1 8 -4 1 , 1 9 8 2 .

[7 ] D .B . W e s t , \ A c la s s o f s o lu t io n s t o t h e g o s s ip p r o b le m , p a r t I" , D isc. M ath., vo l. 3 9 ,
n o . 3 , p p . 3 0 7 -3 2 6 , 1 9 8 2 ; \ p a r t II" , D isc. M ath., vo l. 4 0 , n o . 1 , p p . 8 7 -1 1 3 , 1 9 8 2 ; \ p a r t
III" , D isc. M ath., vo l. 4 0 , n o . 2 -3 , p p . 2 8 5 -3 1 0 , 1 9 8 2 .

[8 ] G. Fe r t in a n d A . R e s p a u d , \ A s u r ve y o n K n Äo d e l g r a p h s " , D iscrete Applied M athematics
vo l. 1 3 7 , n o . 2 , p p . 1 7 3 -1 9 5 , 2 0 0 3 .

[9 ] R . L a b a h n , \ K e r n e ls o f m in im u m s iz e g o s s ip s c h e m e s " , D iscr. M ath., vo l. 1 4 3 , p p .
9 9 -1 3 9 , 1 9 9 5 .

[1 0 ] R . L a b a h n , \ S o m e m in im u m g o s s ip g r a p h s " , Networks, vo l. 2 3 , p p . 3 3 3 -3 4 1 , 1 9 9 3 .

[1 1 ] G. Fe r t in a n d R . L a b a h n , \ Co m p o u n d in g o f g o s s ip g r a p h s " , Networks, vo l. 3 6 , p p .
1 2 6 -1 3 7 , 2 0 0 0 .

[1 2 ] Z. H o a n d M. S h ig e n o , \ N e w b o u n d s o n t h e m in im u m n u m b e r o f c a lls in fa ilu r e -t o le r a n t
Go s s ip in g " , Networks, vo l. 5 3 , p p . 3 5 -3 8 , 2 0 0 9 .

[1 3 ] K . A . B e r m a n a n d M. H a wr ylyc z , \ Te le p h o n e p r o b le m s wit h fa ilu r e s " , SIAM J . Alg.
D isc. M eth., vo l. 7 , p p . 1 3 -1 7 , 1 9 8 6 .

[1 4 ] R .W . H a d d a d , S . R o y a n d A . A . S c h a ®e r , \ On g o s s ip in g wit h fa u lt y t e le p h o n e lin e s " ,
SIAM J . Alg. D isc. M eth., vo l. 8 , p p . 4 3 9 -4 4 5 , 1 9 8 7 .

[1 5 ] T. H a s u n u m a a n d H . N a g a m o c h i, \ Im p r o ve d b o u n d s fo r m in im u m fa u lt -t o le r a n t g o s s ip
g r a p h s " , L NCS, vo l. 6 9 8 6 , p p . 2 0 3 -2 1 4 , 2 0 1 1 .

[1 6 ] L . Ga r g a n o , \ Tig h t e r t im e b o u n d s o n fa u lt -t o le r a n t b r o a d c a s t in g a n d g o s s ip in g " , Net-
works, vo l. 2 2 , p p . 4 6 9 -4 8 6 , 1 9 9 2 .



4 0 Rumor Spreading and Invasion Percolation

[1 7 ] K . Me n g e r , \ Zu r a llg e m e in e n K u r ve n t h e o r ie " , F und. M ath., vo l. 1 0 , p p . 9 6 -1 1 5 , 1 9 2 7 .

[1 8 ] D . J. D a le y a n d D . G. K e n d a ll, \ E p id e m ic s a n d r u m o r s " , Nature, vo l. 2 0 4 , 1 1 1 8 , 1 9 6 4 ,
d x.d o i.o r g / 1 0 .1 0 3 8 / 2 0 4 1 1 1 8 a 0

[1 9 ] R . K a r p , C. S c h in d e lh a u e r , S . S h e n ke r a n d B . V o c kin g , \ R a n d o m iz e d r u m o r s p r e a d in g " ,
In F oundations of Computer Science, P roceedings. 41st Annual Symposium on IE E E ,
p p . 5 6 5 -5 7 4 , 2 0 0 0 .

[2 0 ] D . W ilkin s o n a n d J. F. W ille m s e n , \ In va s io n p e r c o la t io n : a n e w fo r m o f p e r c o la t io n
t h e o r y" , J ournal of P hysics A: M athematical and General, vo l. 1 6 , n o . 1 4 , p p . 3 3 -6 5 ,
1 9 8 3 .

[2 1 ] R . Ch a n d le r , J. K o p lik, K . L e r m a n , J. W ille m s e n , \ Ca p illa r y d is p la c e m e n t a n d p e r c o -
la t io n in p o r o u s m e d ia " , J ournal of F luid M echanics vo l. 1 1 9 , 2 4 9 -2 6 7 , 1 9 8 2 .

[2 2 ] A .-L . B a r a b a s i, \ D e n s it y fu n c t io n a l a n d d e n s it y m a t r ix m e t h o d s c a lin g lin e a r ly wit h
t h e N u m b e r o f a t o m s " , P hys. R ev. L ett., 76, 3 7 5 0 , 1 9 9 6 .

[2 3 ] R .C.P r im ,\ S h o r t e s t c o n n e c t io n n e t wo r ks a n d s o m e g e n e r a liz a t io n s " , B ell System Tech-
nical J ournal, vo l. 3 6 , n o . 6 , p p . 1 3 8 9 { 1 4 0 1 , 1 9 5 7 .

[2 4 ] V . H . H o vn a n ya n , S u . S . P o g h o s ya n a n d V . S . P o g h o s ya n , \ N e w m e t h o d s o f c o n s t r u c t io n
o f fa u lt -t o le r a n t Go s s ip g r a p h s " , IE E E P roceedings of the International Conference on
Computer Science and Information Technologies (CSIT'2013), D OI: 1 0 .1 1 0 9 / CS ITe c h -
n o l.2 0 1 3 .6 7 1 0 3 4 1 .

[2 5 ] V .H . H o vn a n ya n , S u .S . P o g h o s ya n a n d V .S . P o g h o s ya n , \ Me t h o d o f L o c a l In t e r c h a n g e
t o In ve s t ig a t e Go s s ip P r o b le m s " , Transactions of IIAP of the NAS of R A, M athematical
P roblems of Computer Science, vo l. 4 0 , p p . 5 -1 2 , 2 0 1 3 .

[2 6 ] V .H . H o vn a n ya n , S u .S . P o g h o s ya n a n d V .S . P o g h o s ya n , \ Me t h o d o f L o c a l In t e r c h a n g e
fo r t h e In ve s t ig a t io n o f Go s s ip P r o b le m s : p a r t 2 " , Transactions of IIAP of the NAS of
R A, M athematical P roblems of Computer Science, vo l. 4 1 , p p . 1 5 -2 2 , 2 0 1 4 .

[2 7 ] V . H . H o vn a n ya n , S u . S . P o g h o s ya n a n d V .S . P o g h o s ya n , \ Gr a p h P lo t t e r : a S o ft wa r e
To o l fo r t h e In ve s t ig a t io n o f Fa u lt -t o le r a n t Go s s ip Gr a p h s " , P roceedings of International
Conference CSIT-2013, p p . 2 0 -2 2 .

[2 8 ] V . H . H o vn a n ya n , S u . P o g h o s ya n a n d V . P o g h o s ya n , \ Fa u lt -t o le r a n t Go s s ip Gr a p h s
B a s e d o n W h e e l Gr a p h s " , Transactions of IIAP of the NAS of R A, M athematical P rob-
lems of Computer Science, vo l. 4 2 , p p . 4 3 -5 3 , 2 0 1 4 .

[2 9 ] V . H . H o vn a n ya n , S u . P o g h o s ya n a n d V .P o g h o s ya n , \ Op e n p r o b le m s in g o s -
s ip / b r o a d c a s t s c h e m e s a n d t h e p o s s ib le a p p lic a t io n o f t h e m e t h o d o f lo c a l in t e r c h a n g e " ,
P roceedings of International Conference CSIT 2015, p p . 7 3 -7 8 .

Submitted 19.06.2019, accepted 26.11.2019.



Su. Poghosyan and V. Poghosyan 4 1

´³Ùµ³ë³ÝùÇ ï³ñ³ÍáõÙÁ ¨ Ý»ñó÷³ÝóáÕ³Ï³Ý å»ñÏáɳódz

êáõñ»Ý ê. äáÕáëÛ³Ý ¨ ì³Ñ³·Ý ê. äáÕáëÛ³Ý

ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï

e-mail: psuren55@yandex.ru, povahagn@gmail.com

²Ù÷á÷áõÙ

Ø»Ýù áõëáõÙݳëÇñáõÙ »Ýù µ³Ùµ³ë³ÝùÇ ï³ñ³ÍÙ³Ý ¨ ÏáÕ³ÛÇÝ Ý»ñó÷³ÝóáճϳÝ
å»ñÏáɳódzݻñÇ Ùá¹»ÉÝ»ñÁ` Ýå³ï³Ï áõݻݳÉáí µ³ó³Ñ³Ûï»É ¹ñ³Ýó ѳí³Ý³Ï³Ý
ϳåí³ÍáõÃÛáõÝÁ: ´³Ùµ³ë³ÝùÇ ï³ñ³ÍÙ³Ý Ùá¹»ÉÁ Ýϳñ³·ñáõÙ ¿ ¹ñ³ ï³ñ³ÍáõÙÁ
ѳçáñ¹³Ï³Ý Ñ»é³Ëáë³½³Ý·»ñÇ å³ñµ»ñ³µ³ñ ÏñÏÝí»Éáõ ³ñ¹ÛáõÝùáõÙ, ÇëÏ ÏáÕ³ÛÇÝ
Ý»ñó÷³ÝóáÕ³Ï³Ý å»ñÏáɳódzݻñÇ Ùá¹»ÉÁ í»ñ³µ»ñáõÙ ¿ ͳÏáïÏ»Ý ÙÇç³í³ÛñáõÙ
Ñ»ÕáõÏÇ ï³ñ³ÍÙ³ÝÁ: ´³Ùµ³ë³ÝùÇ ï³ñ³ÍÙ³Ý Ùá¹»ÉáõÙ Ù»Ï ï³ÏïÇ ÁÝóóùáõÙ
Ûáõñ³ù³ÝãÛáõñ ѳݷáõÛó ϳï³ñáõÙ ¿ ÙdzÛÝ Ù»Ï ½³Ý·` ½³Ý·³Ñ³ñ»Éáõ å³ÑÇÝ Çñ
ïÇñ³å»ï³Í áÕç ï»Õ»ÏáõÃÛáõÝÁ ÷á˳Ýó»Éáí ѳñ¨³ÝÝ»ñÇÝ: ÀݹëÙÇÝ` µ³Ùµ³ë³ÝùÁ
Ù»Ï ÷áõÉÇ ÁÝóóùáõ٠ѳëÝáõÙ ¿ ëï³óáÕÇÝ` µ³Ùµ³ë³ÝùÇ ³ÕµÛáõñÇ ¨ ëï³óáÕÇ ÙÇç¨
ѳçáñ¹³Ï³Ý ½³Ý·»ñÇ ßÕóÛÇ ³éϳÛáõÃÛ³Ý ¹»åùáõÙ: ¼³Ý·»ñÇ Ñ³çáñ¹³Ï³ÝáõÃÛáõÝÝ
ÁÝïñíáõÙ ¿ µáÉáñ Ñݳñ³íáñ ѳçáñ¹³Ï³ÝáõÃÛáõÝÝ»ñÇ ß³ñùÇó` ѳí³ë³ñ³ã³÷
å³ï³Ñ³Ï³ÝáõÃÛ³Ý ëϽµáõÝùáí (ѳݷáõÛóÝ»ñÇ ï»Õ³÷áËáõÃÛáõÝ): Ø»Ýù ѳٻٳïáõÙ
»Ýù µ³Ùµ³ë³ÝùÇ ï³ñ³ÍÙ³Ý Ùá¹»ÉÁ ÏáÕ³ÛÇÝ Ý»ñó÷³ÝóáÕ³Ï³Ý å»ñÏáɳódzÛÇ
Ñ»ï` Ùá¹»ÉÝ»ñÇ ÷á˳¹³ñÓ ³ñï³å³ïÏ»ñáõÙÝ»ñÇ Çñ³Ï³Ý³óÙ³Ý Ýå³ï³Ïáí
å»ñÏáɳódzÛÇ Ï³ÝáÝÝ»ñÇ ³ÝÑñ³Å»ßï µ³ñ»É³íáõÙÝ»ñ ³é³ç³¹ñ»Éáõ ѳٳñ:

´³Ý³ÉÇ µ³é»ñ` µ³Ùµ³ë³ÝùÇ ËݹÇñ, ÇÝýáñÙ³ódzÛÇ ï³ñ³ÍáõÙ, ÏáÕ³ÛÇÝ
Ý»ñó÷³ÝóáÕ³Ï³Ý å»ñÏáɳódz:

Ðàñïðîñòðàíåíèå ñïëåòåí è èíâàçèâíàÿ ïåðêîëÿöèÿ

Ñóðåí Ñ. Ïîãîñÿí è Âààãí Ñ. Ïîãîñÿí

Èíñòèòóò ïðîáëåì èíôîðìàòèêè è àâòîìàòèçàöèè ÍÀÍ ÐÀ
e-mail: psuren55@yandex.ru, povahagn@gmail.com

Àííîòàöèÿ

Ìû èçó÷àåì ìîäåëè ðàñïðîñòðàíåíèÿ ñïëåòåí è ðåáåðíîé èíâàçèâíîé
ïåðêîëÿöèè ñ öåëüþ îáíàðóæåíèÿ âîçìîæíîé ñâÿçè ìåæäó íèìè. Ìîäåëü
ðàñïðîñòðàíåíèÿ ñïëåòåí îïèñûâàåò ðàñïðîñòðàíåíèå êàê âñëåäñòâèå èç-
çà ïåðèîäè÷åñêîãî ïîâòîðåíèÿ ïîñëåäîâàòåëüíûõ òåëåôîííûõ çâîíêîâ, â òî
âðåìÿ êàê ðåáåðíàÿ èíâàçèâíàÿ ïåðêîëÿöèÿ îòíîñèòñÿ ê ðàñïðîñòðàíåíèþ
æèäêîñòè â ïîðèñòîé ñðåäå. Âî âðåìÿ îäíîãî ðàóíäà ðàñïðîñòðàíåíèÿ
ñëóõîâ êàæäûé óçåë âûïîëíÿåò âûçîâ òîëüêî îäèí ðàç, ïðè ýòîì ïåðåäàâàÿ
âñþ èíôîðìàöèþ, äîñòóïíóþ â ìîìåíò âûçîâà, ñâîèì ñîñåäÿì. Ñïëåòíÿ
äîñòèãàåò óçëà-ïîëó÷àòåëÿ â òå÷åíèå îäíîãî ðàóíäà ïðè íàëè÷èè öåïî÷êè
ïîñëåäîâàòåëüíûõ âûçîâîâ ìåæäó èñòî÷íèêîì ñïëåòíè è óçëîì-ïîëó÷àòåëåì.



4 2 Rumor Spreading and Invasion Percolation

Ïîñëåäîâàòåëüíîñòü âûçîâîâ âûáèðàåòñÿ ðàâíîìåðíî ñëó÷àéíûì îáðàçîì èç
íàáîðà âñåõ âîçìîæíûõ ïîñëåäîâàòåëüíîñòåé (ïåðåñòàíîâîê óçëîâ). Ìû
ñðàâíèâàåì ìîäåëü ðàñïðîñòðàíåíèÿ ñïëåòåí ñ ðåáåðíîé èíâàçèâíîé ïåðêîëÿöèåé
ñ öåëüþ âûäâèæåíèÿ íåîáõîäèìîé îïòèìèçàöèè ïðàâèë ïåðêîëÿöèè äëÿ
äîñòèæåíèÿ îòîáðàæåíèÿ îäíîé ìîäåëè íà äðóãóþ, è, íàîáîðîò.

Êëþ÷åâûå ñëîâà: ïðîáëåìà ñïëåòíè, ðàñïðîñòðàíåíèå èíôîðìàöèè,
ðåáåðíàÿ èíâàçèâíàÿ ïåðêîëÿöèÿ.