ept_kn

1487 days ago by geneson

# 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)