diff --git a/showgraphs.m b/showgraphs.m index 79fbfec0387c8a75edf66b7e06e28162b73742a2..a45e7c774226241582a008c8b1702d35455b8089 100644 --- a/showgraphs.m +++ b/showgraphs.m @@ -52,12 +52,14 @@ Needs["ErrorBarPlots`"] (*- Experimental mixing time as function of n. At (n,tau)=(1000,2.5) it seems to be between 10.000 and 20.000 steps.*) (* Done. Seems to be something like (1/2)(32-26(tau-2))n so we run it for that time without the factor (1/2).*) (**) -(*- GCM1: Greedy Configuration Model 1: take highest degree and completely do all its pairings (at random)*) -(*- GCM2: Greedy Configuration Model 2: take highest degree and do a single pairing, then take new highest degree. So this matters mostly if there are multiple high degree nodes*) +(*- GCM1: Greedy Configuration Model 1: take highest degree and do a single pairing, then take new highest degree*) +(*- GCM2: Greedy Configuration Model 2: take highest degree and completely do all its pairings (at random)*) +(*The difference does not matter if one node is by far the highest.*) (*The success rates, conditioned on the degree sequence being graphical, is almost always higher using GCM2. For certain degree sequences the success rate of GCM2 can be 0.9 higher than that of GCM1. (i.e. amost always works vs almost always fails).*) (*For tau > ~2.3 the success rate of GCM2 seems to be higher than 80% for most sequences.*) (*For tau < ~2.3 the success rate of GCM2 can drop to less than 10% for some sequences but for many sequences it is still larger than 80%.*) (**) +(*Success rate of GCM seems to be correlated with mixing time from Erdos-Gallai: higher success rate implies lower mixing time.*) (**) (* *) @@ -83,7 +85,7 @@ Grid[Partition[gs,10],Frame->All] (*Data import*) -gsraw=Import[NotebookDirectory[]<>"data/graphdata.m"]; +gsraw=Import[NotebookDirectory[]<>"data/graphdata_partial.m"]; gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *) @@ -175,7 +177,7 @@ getMixingTime[values_]:=Module[{avg}, measureSkip=1; mixingTimes=Map[{#[[1,1]],(1/#[[1,1]])measureSkip * getMixingTime[#[[2]]]}&,gdata,{3}]; mixingTimesBars=Map[ - {{#[[1,1]],Mean[#[[All,2]]]},ErrorBar[StandardDeviation[#[[All,2]]]/Sqrt[Length[#]]]}& + {{#[[1,1]],Mean[#[[All,2]]]},ErrorBar[StandardDeviation[#[[All,2]]](*/Sqrt[Length[#]]*)]}& ,mixingTimes,{2}]; ErrorListPlot[mixingTimesBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","~~mixing time divided by n"},PlotLegends->taulabels] @@ -190,15 +192,27 @@ mixingTimesBars=Map[ Show[ ErrorListPlot[mixingTimesBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","~~mixing time divided by n, for n = 1000"},PlotRange->{{2,3},{0,30}}] -,Plot[(32-26(tau-2)),{tau,2,3}]] +,Plot[(32-20(tau-2)),{tau,2,3}]] (* ::Subsection:: *) -(*Triangle exponent: Plot average #triangles vs n*) +(*Plot #triangles distribution for specific (n,tau)*) + + +plotRangeByTau[tau_]:=Piecewise[{{{0,30000},tau<2.3},{{0,4000},2.32.7}},Automatic] +histograms=Map[Histogram[#[[All,2]],PlotRange->{plotRangeByTau[#[[1,1,2]]],Automatic}]&,averagesGrouped,{2}]; + + +(* TableForm[histograms,TableHeadings->{taulabels,nlabels}] *) +TableForm[Transpose[histograms],TableHeadings->{nlabels,taulabels}] + + +(* ::Section:: *) +(*Triangle exponent*) (* When importing from exponent-only-data file *) -gsraw=Import[NotebookDirectory[]<>"data/graphdata_partial.m"]; +gsraw=Import[NotebookDirectory[]<>"data/graphdata_exponent.m"]; gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *) averagesGrouped=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}]; @@ -253,18 +267,6 @@ Transpose[{tauValues,fitsExtra}]]; Show[ErrorListPlot[exponentsErrorBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","triangle-law-exponent"},PlotRange->{{2,3},{0,1.6}}],Plot[3/2(3-tau),{tau,2,3}]] -(* ::Subsection:: *) -(*Plot #triangles distribution for specific (n,tau)*) - - -plotRangeByTau[tau_]:=Piecewise[{{{0,30000},tau<2.3},{{0,4000},2.32.7}},Automatic] -histograms=Map[Histogram[#[[All,2]],PlotRange->{plotRangeByTau[#[[1,1,2]]],Automatic}]&,averagesGrouped,{2}]; - - -(* TableForm[histograms,TableHeadings->{taulabels,nlabels}] *) -TableForm[Transpose[histograms],TableHeadings->{nlabels,taulabels}] - - (* ::Section:: *) (*Greedy configuration model*) @@ -282,7 +284,7 @@ getStats[run_]:=Module[{avg,stddev}, stats=Map[getStats,gdata,{3}]; -histograms=Map[Histogram[{#[[1,4]]},PlotRange->{{0,2},Automatic},PlotLabel->"ErdosGallai="<>ToString[NumberForm[#[[1,3]],3]]<>"\[Cross]average. stddev="<>ToString[NumberForm[#[[1,2]],3]]<>"\[Cross]average"]&,stats,{2}]; +histograms=Map[Histogram[{#[[1,4]]},PlotRange->{{0,5},Automatic},PlotLabel->"ErdosGallai="<>ToString[NumberForm[#[[1,3]],3]]<>"\[Cross]average. stddev="<>ToString[NumberForm[#[[1,2]],3]]<>"\[Cross]average"]&,stats,{2}]; TableForm[histograms,TableHeadings->{taulabels,nlabels}] @@ -305,4 +307,13 @@ TableForm[rateHistograms,TableHeadings->{taulabels,nlabels}] (*TableForm[Transpose[rateHistograms],TableHeadings->{nlabels,taulabels}]*) +(* ::Subsection:: *) +(*Compare success rate with mixing time*) + + +successrates2=Map[{Length[#[[4]]],Length[#[[5]]],getMixingTime[#[[2]]]}&,gdata,{3}]; +(* { GCM1 rate, GCM2 rate, mixing time from ErdosGallai } *) + +scatterPlots=Map[ListPlot[#[[All,{1,3}]],PlotRange->{All,All},PlotStyle->PointSize[Large]]&,successrates2,{2}]; +TableForm[scatterPlots,TableHeadings->{taulabels,nlabels}]