From ba07c54759974a3c375319ba1fbd426849839c89 2017-05-15 12:17:38 From: Tom Bannink Date: 2017-05-15 12:17:38 Subject: [PATCH] Split and rename Mathematica notebook --- diff --git a/showgraphs.m b/triangle_analysis.m similarity index 75% rename from showgraphs.m rename to triangle_analysis.m index a45e7c774226241582a008c8b1702d35455b8089..a665023c7c105737590d4831948ff15431fb23b8 100644 --- a/showgraphs.m +++ b/triangle_analysis.m @@ -16,14 +16,11 @@ Needs["ErrorBarPlots`"] (**) (*- GCM success rates: for the degree sequences where it "always fails", look at the degree sequence. Does it have a low/high number of degree 1 nodes? Is the maximum degree very low/high?*) (**) -(*- Use different starting point for switch chain that is closer to uniform:*) -(* 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*) +(*- Does GCM start closer to uniform?*) +(* (a) How close 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.*) -(* The initial #triangles in GCM2 is somewhere between 0 and 5 standard deviations below the average #triangles, whereas the #triangles in Erdos-Gallai can be as high as 100 standard deviations above the average.*) -(* TODO: Not only compare number of standard deviations but also percentage above/below average.*) +(* TODO: Investigate #triangles not only in number of standard deviations but also percentage above/below average.*) (**) (*- Count #moves that result in +-k triangles (one move could create many triangles at once!)*) (**) @@ -51,17 +48,24 @@ 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).*) -(**) + + +(* ::Subsection:: *) +(*Observations on `Greedy Configuration Model'*) + + +(* ::Text:: *) (*- 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.*) +(*Success rate of GCM seems to be correlated with mixing time from Erdos-Gallai: higher success rate implies lower mixing time. *) (**) -(* *) +(*The initial #triangles in GCM2 is somewhere between 0 and 5 standard deviations below the average #triangles, whereas the #triangles in Erdos-Gallai can be as high as 100 standard deviations above the average.*) (* ::Section:: *) @@ -207,66 +211,6 @@ histograms=Map[Histogram[#[[All,2]],PlotRange->{plotRangeByTau[#[[1,1,2]]],Autom TableForm[Transpose[histograms],TableHeadings->{nlabels,taulabels}] -(* ::Section:: *) -(*Triangle exponent*) - - -(* When importing from exponent-only-data file *) -gsraw=Import[NotebookDirectory[]<>"data/graphdata_exponent.m"]; -gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *) -averagesGrouped=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}]; - - -(* When importing from general file *) -averages=Map[{#[[1]],Mean[#[[2,1;;-1]]]}&,gsraw]; -(* averages=SortBy[averages,#[[1,1]]&]; (* Sort by n *) *) -averagesGrouped=GatherBy[averages,{#[[1,2]]&,#[[1,1]]&}]; (* Split by n,tau *) - - -(* averagesGrouped[[ tau index, n index, run index , {ntau, avgtri} ]] *) -nlabels=Map["n = "<>ToString[#]&,averagesGrouped[[1,All,1,1,1]]]; -taulabels=Map["tau = "<>ToString[#]&,averagesGrouped[[All,1,1,1,2]]]; -averagesErrorBars=Map[ -{{#[[1,1,1]],Mean[#[[All,2]]]}, -ErrorBar[StandardDeviation[#[[All,2]]]] -}&,averagesGrouped,{2}]; - - -ErrorListPlot[averagesErrorBars,Joined->True,PlotMarkers->Automatic,PlotRange->All,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels] - - -ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels] - - -(* ::Subsection:: *) -(*Fitting the log-log-plot*) - - -loglogdata=Log[averagesErrorBars[[All,All,1]]]; -fits=Map[Fit[#,{1,logn},logn]&,loglogdata]; -fitsExtra=Map[LinearModelFit[#,logn,logn]&,loglogdata]; - - -fitsExtra[[1]]["ParameterConfidenceIntervalTable"] -fitsExtra[[1]]["BestFitParameters"] -fitsExtra[[1]]["ParameterErrors"] -fitsExtra[[1]]["ParameterConfidenceIntervals"] - - -Show[ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels],Plot[fits,{logn,1,2000}]] - - -tauValues=averagesGrouped[[All,1,1,1,2]]; -exponents=Transpose[{tauValues,fits[[All,2,1]]}]; -Show[ListPlot[exponents,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","triangle-law-exponent"},PlotRange->{{2,3},{0,1.6}}],Plot[3/2(3-tau),{tau,2,3}]] - - -tauValues=averagesGrouped[[All,1,1,1,2]]; -exponentsErrorBars=Map[{{#[[1]],#[[2]]["BestFitParameters"][[2]]},ErrorBar[#[[2]]["ParameterConfidenceIntervals"][[2]]-#[[2]]["BestFitParameters"][[2]]]}&, -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}]] - - (* ::Section:: *) (*Greedy configuration model*) diff --git a/triangle_exponent_plots.m b/triangle_exponent_plots.m new file mode 100644 index 0000000000000000000000000000000000000000..af61d1223c4fb6a47a3c62c48e505bd2fd7567fe --- /dev/null +++ b/triangle_exponent_plots.m @@ -0,0 +1,73 @@ +(* ::Package:: *) + +Needs["ErrorBarPlots`"] + + +(* ::Section:: *) +(*Triangle exponent*) + + +(* ::Text:: *) +(*Expected number of triangles is the following powerlaw*) + + +(* ::DisplayFormula:: *) +(*#triangles = const\[Cross]n^(T(\[Tau])) where T(\[Tau])=3/2 (3-\[Tau])*) + + +(* When importing from exponent-only-data file *) +gsraw=Import[NotebookDirectory[]<>"data/graphdata_exponent.m"]; +gsraw=SortBy[gsraw,#[[1,1]]&]; (* Sort by n *) +averagesGrouped=GatherBy[gsraw,{#[[1,2]]&,#[[1,1]]&}]; + + +(* averagesGrouped[[ tau index, n index, run index , {ntau, avgtri} ]] *) +nlabels=Map["n = "<>ToString[#]&,averagesGrouped[[1,All,1,1,1]]]; +taulabels=Map["tau = "<>ToString[#]&,averagesGrouped[[All,1,1,1,2]]]; +averagesErrorBars=Map[ +{{#[[1,1,1]],Mean[#[[All,2]]]}, +ErrorBar[StandardDeviation[#[[All,2]]]] +}&,averagesGrouped,{2}]; + + +ErrorListPlot[averagesErrorBars,Joined->True,PlotMarkers->Automatic,PlotRange->All,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels] + + +ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels] + + +(* ::Subsection:: *) +(*Fitting the log-log-plot*) + + +loglogdata=Log[averagesErrorBars[[All,All,1]]]; +fits=Map[Fit[#,{1,logn},logn]&,loglogdata]; +fitsExtra=Map[LinearModelFit[#,logn,logn]&,loglogdata]; + + +fitsExtra[[1]]["ParameterConfidenceIntervalTable"] +fitsExtra[[1]]["BestFitParameters"] +fitsExtra[[1]]["ParameterErrors"] +fitsExtra[[1]]["ParameterConfidenceIntervals"] + + +Show[ListLogLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels],Plot[fits,{logn,1,2000}]] + + +(* ::Subsection:: *) +(*Plot of T(\[Tau])*) + + +tauValues=averagesGrouped[[All,1,1,1,2]]; +exponents=Transpose[{tauValues,fits[[All,2,1]]}]; +Show[ListPlot[exponents,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","T(\[Tau])"},PlotRange->{{2,3},{0,1.6}}],Plot[3/2(3-tau),{tau,2,3}]] + + +(* ::Subsection:: *) +(*T(\[Tau]) including error bars*) + + +tauValues=averagesGrouped[[All,1,1,1,2]]; +exponentsErrorBars=Map[{{#[[1]],#[[2]]["BestFitParameters"][[2]]},ErrorBar[#[[2]]["ParameterConfidenceIntervals"][[2]]-#[[2]]["BestFitParameters"][[2]]]}&, +Transpose[{tauValues,fitsExtra}]]; +Show[ErrorListPlot[exponentsErrorBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"tau","T(\[Tau])"},PlotRange->{{2,3},{0,1.6}}],Plot[3/2(3-tau),{tau,2,3}]]