# This worksheet generates data for
# "Using Markov chains to determine expected propagation time for probabilistic zero forcing"
# by Yu Chan, Emelie Curl, Jesse Geneson, Leslie Hogben, Kevin Liu, Issac Odegard, and Michael Ross
# It contains the code for computing the expected propagation time of
# complete graphs.
|
|
def ApxEpt(n,e): #approximate EPT for complete graph of order n, e terms of summation computed
A=zero_matrix(RDF,n)
for i in range(n): #generate Markov matrix using probability of forcing k more vertices
b=i+1 #number of blue vertices
for k in range(n-i):
A[i,i+k]=binomial(n-b,k)*(1-(1-b/(n-1))^b)^k*(1-b/(n-1))^(b*(n-b-k))
EPT=0
for r in IntegerRange(1,e): #estimate EPT with powers of Markov matrix
EPT=EPT+r*((A^r)[0,n-1]-(A^(r-1))[0,n-1])
return EPT
|
|
#generates the data in the appendix table with EPT values for Kn
eptk = list()
for k in [2..100]: #range of orders to check
x = ApxEpt(k,200)
print x
eptk.append((k,x))
1.0 2.0 2.50263157895 2.83189594079 3.0716430326 3.24768851559 3.38290012177 3.49034748863 3.57753223999 3.6501377417 3.7124116877 3.76715299193 3.81610909035 3.86040211393 3.90079163993 3.9378173015 3.97188365175 4.00331281411 4.03237514662 4.05930631601 4.08431707206 4.10759886652 4.12932668712 4.14966014885 4.16874385949 4.18670777223 4.20366779581 4.21972663222 4.23497473058 4.24949128612 4.2633452636 4.27659643932 4.28929644523 4.30148978624 4.31321480126 4.32450454693 4.33538759436 4.34588873743 4.35602961549 4.36582925489 4.37530453467 4.3844705818 4.39334110248 4.40192865615 4.41024487924 4.41830066534 4.42610630828 4.43367161367 4.44100598422 4.44811848346 4.45501788174 4.46171268815 4.4682111714 4.47452137203 4.4806511084 4.48660797798 4.4923993556 4.49803238968 4.50351399754 4.50885086042 4.51404941879 4.51911586834 4.52405615698 4.52887598292 4.53358079404 4.53817578857 4.54266591699 4.54705588516 4.5513501586 4.5555529678 4.55966831443 4.56369997837 4.5676515254 4.57152631545 4.57532751131 4.57905808759 4.58272083995 4.58631839447 4.58985321695 4.59332762231 4.5967437837 4.60010374159 4.60340941249 4.60666259749 4.60986499045 4.61301818583 4.61612368617 4.61918290921 4.6221971946 4.6251678102 4.62809595799 4.63098277962 4.63382936151 4.63663673962 4.6394059038 4.64213780184 4.64483334313 4.64749340201 4.65011882084 1.0 2.0 2.50263157895 2.83189594079 3.0716430326 3.24768851559 3.38290012177 3.49034748863 3.57753223999 3.6501377417 3.7124116877 3.76715299193 3.81610909035 3.86040211393 3.90079163993 3.9378173015 3.97188365175 4.00331281411 4.03237514662 4.05930631601 4.08431707206 4.10759886652 4.12932668712 4.14966014885 4.16874385949 4.18670777223 4.20366779581 4.21972663222 4.23497473058 4.24949128612 4.2633452636 4.27659643932 4.28929644523 4.30148978624 4.31321480126 4.32450454693 4.33538759436 4.34588873743 4.35602961549 4.36582925489 4.37530453467 4.3844705818 4.39334110248 4.40192865615 4.41024487924 4.41830066534 4.42610630828 4.43367161367 4.44100598422 4.44811848346 4.45501788174 4.46171268815 4.4682111714 4.47452137203 4.4806511084 4.48660797798 4.4923993556 4.49803238968 4.50351399754 4.50885086042 4.51404941879 4.51911586834 4.52405615698 4.52887598292 4.53358079404 4.53817578857 4.54266591699 4.54705588516 4.5513501586 4.5555529678 4.55966831443 4.56369997837 4.5676515254 4.57152631545 4.57532751131 4.57905808759 4.58272083995 4.58631839447 4.58985321695 4.59332762231 4.5967437837 4.60010374159 4.60340941249 4.60666259749 4.60986499045 4.61301818583 4.61612368617 4.61918290921 4.6221971946 4.6251678102 4.62809595799 4.63098277962 4.63382936151 4.63663673962 4.6394059038 4.64213780184 4.64483334313 4.64749340201 4.65011882084 |
#generate plot in Appendix 2
logn = list()
llogn = list()
a = var('a')
sp = plot(2.5+1.4*log(log(a+0.0)), (a, 1, 100),color='black')
sp += scatter_plot(eptk, facecolor='gray', markersize=10, axes_labels=['$n$','']) #EPT Kn
#sp.show()
show(sp)
|
|
|