From fda8425fac05e19516f1936c4d7b161479ba040e 2017-05-08 17:45:02 From: Tom Bannink Date: 2017-05-08 17:45:02 Subject: [PATCH] Add scatter plot of GCM success rate vs mixing time --- diff --git a/cpp/switchchain.cpp b/cpp/switchchain.cpp index b14a8ecfd6c5fdbcea2373c39d7f623ca350ea99..9fccb10b01bc2834dd2111e27d01d2d80a505953 100644 --- a/cpp/switchchain.cpp +++ b/cpp/switchchain.cpp @@ -66,6 +66,8 @@ class SwitchChain { // // Assumes degree sequence does NOT contain any zeroes! // +// method2 = true -> take highest degree and finish its pairing completely +// method2 = false -> take new highest degree after every pairing bool greedyConfigurationModel(DegreeSequence& ds, Graph& g, auto& rng, bool method2) { // Similar to Havel-Hakimi but instead of pairing up with the highest ones // that remain, simply pair up with random ones @@ -189,7 +191,7 @@ int main() { outfile << '{'; bool outputComma = false; - for (int numVertices = 200; numVertices <= 1000; numVertices += 100) { + for (int numVertices = 200; numVertices <= 2000; numVertices += 400) { for (float tau : tauValues) { DegreeSequence ds(numVertices); @@ -232,11 +234,13 @@ int main() { int successrate2 = 0; for (int i = 0; i < 100; ++i) { Graph gtemp; + // Take new highest degree every time if (greedyConfigurationModel(ds, gtemp, rng, false)) { ++successrate1; greedyTriangles1.push_back(gtemp.countTriangles()); g1 = gtemp; } + // Finish all pairings of highest degree first if (greedyConfigurationModel(ds, gtemp, rng, true)) { ++successrate2; greedyTriangles2.push_back(gtemp.countTriangles()); @@ -269,7 +273,7 @@ int main() { //constexpr int measureSkip = // 200; // Take a sample every ... steps int mixingTime = 0; - constexpr int measurements = 5000; + constexpr int measurements = 50000; constexpr int measureSkip = 1; diff --git a/data/README b/data/README index 96d0d8ff5fc6c5a18e09f16da2a467f3da04acf5..66604b254d4aac72d45a5c2dea5dcf8857cb0093 100644 --- a/data/README +++ b/data/README @@ -9,3 +9,12 @@ graphdata_exponent.m measurements = 50 measureSkip = 200 +graphdata_gcm_partial.m + ?? + +graphdata_partial.m + output: {{n,tau},triangleseq,ds,greedyTriangles1,greedyTriangles2,greedySeq1,greedySeq2} + degreeSamples = 200 + mixingTime = 0 + measurements = 50000 + measureSkip = 1 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}]