AENC/switchchain Changeset - fda8425fac05 · Centrum Wiskunde & Informatica (CWI)

Changeset - fda8425fac05

Parent rev.

Child rev.

[Not reviewed]

0 3 0

Tom Bannink - 8 years ago 2017-05-08 17:45:02
tombannink@gmail.com

Add scatter plot of GCM success rate vs mixing time

3 files changed with 46 insertions and 22 deletions:

cpp/switchchain.cpp

data/README

showgraphs.m

0 comments (0 inline, 0 general)

cpp/switchchain.cpp

➞

Show inline comments

@@ @@ -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;

data/README

➞

Show inline comments

@@ @@ -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

showgraphs.m

➞

Show inline comments

@@ @@ -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.3<tau<2.7},{{0,800},tau>2.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.3<tau<2.7},{{0,800},tau>2.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}]
 (*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}]

0 comments (0 inline, 0 general)