From 3349f6d40bd8e90ecdb9453284492c6de8cec4b3 2017-04-03 15:26:48
From: Tom Bannink <tombannink@gmail.com>
Date: 2017-04-03 15:26:48
Subject: [PATCH] Add TODO and plots on GCM-2

---

diff --git a/showgraphs.m b/showgraphs.m
index 42beccd4041b9dccdceb090f5778542b37bf61fb..b01c4b7166b42164e71b3c552af6615d6661a216 100644
--- a/showgraphs.m
+++ b/showgraphs.m
@@ -12,9 +12,16 @@ Needs["ErrorBarPlots`"]
 (*   Do configuration model, starting with the vertex with highest degree and keeping track of a "forbidden list" meaning dont pair something that is not allowed*)
 (*   (a) How close is this to uniform ? At least w.r.t. the measure of #triangles*)
 (*   (b) How often does this procedure work/fail. Might still be faster to do switchings from Erdos-Gallai.*)
+(*   (c) Compare two greedy ways: (c1) first take highest and finish all its pairings  (c2) take new highest after every single pairing*)
+(*   (d) Time evolution for GCM on top of Erdos-Gallai time evolution.*)
 (**)
 (*- Count #moves that result in +-k triangles (one move could create many triangles at once!)*)
 (**)
+(*- For a graph snapshot: for all V shapes, compute the number of ways to make it into a triangle:*)
+(*  Let u1,u2 be the endpoints of the V. For all neighbors v1 of u1 and v2 of u2, see of v1,v2 has an edge. Meaning, if we were to select randomly an u1 edge and an u2 edge, then whats the probability that it can be used to switch the V into a triangle.*)
+(**)
+(*- Why does GCM-2 start with very low #triangles*)
+(**)
 (*- Improve runtime*)
 (*   (a) Better direct triangle counting? (I doubt it)*)
 (*   (b) Better triangle counting by only keeping track of CHANGES in #triangles*)
@@ -65,12 +72,14 @@ Grid[Partition[gs,10],Frame->All]
 (*Data import and data merge*)
 
 
-gsraw=Import[NotebookDirectory[]<>"data/graphdata.m"];
+gsraw=Import[NotebookDirectory[]<>"data/graphdata_partial.m"];
 gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *)
 
 
 gdata=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}];
 (* gdata[[ tau index, n index, run index , {ntau, #tris, ds} ]] *)
+nlabels=Map["n = "<>ToString[#]&,gdata[[1,All,1,1,1]]];
+taulabels=Map["tau = "<>ToString[#]&,gdata[[All,1,1,1,2]]];
 
 
 newData=Import[NotebookDirectory[]<>"data/graphdata_3.m"];
@@ -122,13 +131,14 @@ Show[ListPlot[avgAndProp,AxesOrigin->{0,0},AxesLabel->{"degree-sequence-property
 
 numPlots=20;
 selectedData=gdata[[5,-1]][[-numPlots;;-1]];
+measureSkip=1;
 minCount=Min[Map[Min[#[[2]]]&,selectedData]];
 maxCount=Max[Map[Max[#[[2]]]&,selectedData]];
 maxTime=Max[Map[Length[#[[2]]]&,selectedData]];
-skipPts=Max[1,Round[maxTime/100]]; (* Plotting every point is slow. Plot only once per `skipPts` timesteps *)
+skipPts=Max[1,Round[maxTime/200]]; (* Plotting every point is slow. Plot only once per `skipPts` timesteps *)
 coarseData=Map[#[[2,1;;-1;;skipPts]]&,selectedData];
 labels=Map["{n,tau} = "<>ToString[#[[1]]]&,selectedData];
-ListPlot[coarseData,Joined->True,PlotRange->{minCount,maxCount},DataRange->{0,200*maxTime},PlotLegends->labels]
+ListPlot[coarseData,Joined->True,PlotRange->{minCount,maxCount},DataRange->{0,measureSkip*maxTime},PlotLegends->labels]
 (* Map[ListPlot[#,Joined->True,PlotRange\[Rule]{minCount,maxCount},DataRange\[Rule]{0,maxTime}]&,coarseData] *)
 
 
@@ -143,7 +153,8 @@ getMixingTime[values_]:=Module[{avg},
     FirstPosition[values,_?(#<=avg&)][[1]]
 ]
 (* gdata[[ tau index, n index, run index , {ntau, #tris, ds} ]] *)
-mixingTimes=Map[{#[[1,1]],(1/#[[1,1]])200 * getMixingTime[#[[2]]]}&,gdata,{3}];
+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[#]]]}&
 ,mixingTimes,{2}];
@@ -151,7 +162,8 @@ ErrorListPlot[mixingTimesBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"n
 
 
 (* For n fixed, look at function of tau *)
-mixingTimes=Map[{#[[1,2]],(1/#[[1,1]])200 * getMixingTime[#[[2]]]}&,gdata,{3}];
+measureSkip=1;
+mixingTimes=Map[{#[[1,2]],(1/#[[1,1]])measureSkip * getMixingTime[#[[2]]]}&,gdata,{3}];
 mixingTimesBars=Map[
     {{#[[1,1]],Mean[#[[All,2]]]},ErrorBar[StandardDeviation[#[[All,2]]]]}&
 ,mixingTimes[[All,-1]],{1}];
@@ -206,9 +218,42 @@ Show[ListPlot[exponents,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","t
 
 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}];
-nlabels=Map["n = "<>ToString[#]&,averagesGrouped[[1,All,1,1,1]]];
-taulabels=Map["tau = "<>ToString[#]&,averagesGrouped[[All,1,1,1,2]]];
 
 
 (* TableForm[histograms,TableHeadings->{taulabels,nlabels}] *)
 TableForm[Transpose[histograms],TableHeadings->{nlabels,taulabels}]
+
+
+(* ::Section:: *)
+(*Greedy configuration model*)
+
+
+(* ::Subsection:: *)
+(*#triangles(GCM) distribution vs #triangles(SwitchChain)*)
+
+
+timeWindow=Round[Length[gdata[[1,1,1,2]]]/10];
+getStats[run_]:=Module[{avg,stddev},
+    avg=N[Mean[run[[2,-timeWindow;;-1]]]];
+    stddev=N[StandardDeviation[run[[2,timeWindow;;-1]]]];
+    {run[[1]],(run[[2,1]]-avg)/stddev,Map[N[(#-avg)/stddev]&,run[[4]]]}
+]
+stats=Map[getStats,gdata,{3}];
+
+
+histograms=Map[Histogram[#[[1,3]],PlotRange->{{-8,8},Automatic},PlotLabel->"ErdosGallai deviation: "<>ToString[#[[1,2]]]]&,stats,{2}];
+
+
+TableForm[histograms,TableHeadings->{taulabels,nlabels}]
+
+
+(* ::Subsection:: *)
+(*Greedy CM success rates*)
+
+
+(* gdata[[ tau index, n index, run index , {ntau, #tris, ds, greedyTriangles} ]] *)
+successrates=Map[Length[#[[4]]]&,gdata,{3}];
+
+rateHistograms=Map[Histogram[#,{10},PlotRange->{{0,100},Automatic}]&,successrates,{2}];
+TableForm[rateHistograms,TableHeadings->{taulabels,nlabels}]
+(*TableForm[Transpose[rateHistograms],TableHeadings->{nlabels,taulabels}]*)