Changeset - 06fad9499398
Parent rev.
Child rev.
[Not reviewed]
0 2 0
Tom Bannink - 8 years ago 2017-03-01 13:19:29
tombannink@gmail.com
Add TODO list to mathematica notebook
2 files changed with 24 insertions and 6 deletions:
cpp/showgraphs.m
22
4
cpp/switchchain.cpp
2
2
0 comments (0 inline, 0 general)
cpp/showgraphs.m
➞
Show inline comments
 
(* ::Package:: *)
 

			




	
	
	
		
 
Needs["ErrorBarPlots`"]

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
(* ::Section:: *)

			




	
	
	
		
 
(*TODO*)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
(* ::Text:: *)

			




	
	
	
		
 
(*- Compute  Sum over i<j<k  of  (1-Exp[- d_i d_j / (2E)]) * (1 - Exp[-d_j d_k / (2E)]) * (1 - Exp[-d_k d_i / (2E)]) .*)

			




	
	
	
		
 
(*   Only depends on degree sequence. Can be done with current data.*)

			




	
	
	
		
 
(*- Do a single very long run to see if there are any weird things after many steps*)

			




	
	
	
		
 
(*- 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*)

			




	
	
	
		
 
(*   (b) How often does this procedure work/fail. Might still be faster to do switchings from Erdos-Gallai.*)

			




	
	
	
		
 
(*- Improve runtime*)

			




	
	
	
		
 
(*   (a) Don't remove/add edges from the std::vector. Simply replace them*)

			




	
	
	
		
 
(*   (b) Better triangle counting? (I doubt it)*)

			




	
	
	
		
 
(*   (c) Do not choose the three permutations with 1/3 probability: choose the "staying" one with a very low probability. Should still be a valid switch chain?*)

			




	
	
	
		
 
(*- ?*)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
(* ::Section:: *)

			




	
	
	
		
 
(*Visualize graphs*)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
gsraw=Import[NotebookDirectory[]<>"graphdata.m"];

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
ListPlot[gsraw[[2]],Joined->True,PlotRange->All,AxesLabel->{"Step","Triangles"}]

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
gs=Map[Graph[#,GraphLayout->"CircularEmbedding"]&,gsraw[[1]]];

			




	
	
	
		
 
gs2=Map[Graph[#,GraphLayout->Automatic]&,gsraw[[1]]];

			




	
	
		
 
@@ -33,24 +52,25 @@ gsraw=Import[NotebookDirectory[]<>"graphdata_merged.m"];

			




	
	
	
		
 

			




	
	
	
		
 
newData=Import[NotebookDirectory[]<>"graphdata_tau_multi4.m"];

			




	
	
	
		
 
mergedData=Import[NotebookDirectory[]<>"graphdata_merged.m"];

			




	
	
	
		
 
Export[NotebookDirectory[]<>"graphdata_merged_new.m",Join[mergedData,newData]]

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
(* ::Subsection:: *)

			




	
	
	
		
 
(*Plot empirical distribution of maximum degree*)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
maxDegrees=Map[{#[[1]],Max[#[[3]]]}&,gsraw];

			




	
	
	
		
 
maxDegrees=GatherBy[maxDegrees,{#[[1,2]]&,#[[1,1]]&}];

			




	
	
	
		
 
(* maxDegrees[[ tau index, n index, run index,  ntau or dmax ]] *)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
Histogram[maxDegrees[[1,-1,All,2]],PlotRange->{{0,2000},{0,100}},AxesLabel->{"d_max","frequency"}]

			




	
	
	
		
 
Histogram[maxDegrees[[2,-1,All,2]],PlotRange->{{0,2000},{0,100}},AxesLabel->{"d_max","frequency"}]

			




	
	
	
		
 
Histogram[maxDegrees[[3,-1,All,2]],PlotRange->{{0,2000},{0,100}},AxesLabel->{"d_max","frequency"}]

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
(* ::Subsection:: *)

			




	
	
	
		
 
(*Plot triangle count over "time" in Markov chain instances*)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
numPlots=15;

			




	
	
		
 
@@ -64,28 +84,26 @@ labels=Map["{n,tau} = "<>ToString[#[[1]]]&,selectedData];

			




	
	
	
		
 
ListPlot[coarseData,Joined->True,PlotRange->{minCount,maxCount},DataRange->{0,maxTime},PlotLegends->labels]

			




	
	
	
		
 
(* Map[ListPlot[#,Joined->True,PlotRange\[Rule]{minCount,maxCount},DataRange\[Rule]{0,maxTime}]&,coarseData] *)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
(* ::Subsection:: *)

			




	
	
	
		
 
(*Plot average #triangles vs n*)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
averages=Map[{#[[1]],Mean[#[[2,1;;-1]]]}&,gsraw];

			




	
	
	
		
 
(* Sort by n *)

			




	
	
	
		
 
averages=SortBy[averages,#[[1,1]]&];

			




	
	
	
		
 
(* Split by n,tau *)

			




	
	
	
		
 
averagesGrouped=GatherBy[averages,{#[[1,1]]&,#[[1,2]]&}];

			




	
	
	
		
 
(* averagesGroupes[[ n index, tau index , run index, {ntau, tri, ds} ]] *)

			




	
	
	
		
 
averagesGrouped=Transpose[averagesGrouped];

			




	
	
	
		
 
(* averagesGrouped[[ tau index, n index, run index ]] *)

			




	
	
	
		
 
averagesGrouped=GatherBy[averages,{#[[1,2]]&,#[[1,1]]&}];

			




	
	
	
		
 
(* averagesGrouped[[ tau index, n index, run index , {ntau, tri, ds} ]] *)

			




	
	
	
		
 
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]]]/Sqrt[Length[#]]]

			




	
	
	
		
 
}&,averagesGrouped,{2}];

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
ErrorListPlot[averagesErrorBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels]

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
ListLogPlot[averagesErrorBars[[All,All,1]],Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"},PlotLegends->taulabels]

			




        

    


    
    

    

        

                

                    cpp/switchchain.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -75,25 +75,25 @@ int main() {

			




	
	
	
		
 
    // Degrees follow a power-law distribution with some parameter tau

			




	
	
	
		
 
    // Expect:  #tri = const * n^{ something }

			




	
	
	
		
 
    // The goal is to find the 'something' by finding the number of triangles

			




	
	
	
		
 
    // for different values of n and tau

			




	
	
	
		
 
    float tauValues[] = {2.2f, 2.5f, 2.8f};

			




	
	
	
		
 

			




	
	
	
		
 
    Graph g;

			




	
	
	
		
 

			




	
	
	
		
 
    std::ofstream outfile("graphdata.m");

			




	
	
	
		
 
    outfile << '{';

			




	
	
	
		
 
    bool outputComma = false;

			




	
	
	
		
 

			




	
	
	
		
 
    for (int numVertices = 2000; numVertices <= 10000; numVertices += 1000) {

			




	
	
	
		
 
    for (int numVertices = 4000; numVertices <= 8000; numVertices += 1000) {

			




	
	
	
		
 
        for (float tau : tauValues) {

			




	
	
	
		
 

			




	
	
	
		
 
            DegreeSequence ds(numVertices);

			




	
	
	
		
 
            powerlaw_distribution degDist(tau, 2, numVertices);

			




	
	
	
		
 
            //std::poisson_distribution<> degDist(12);

			




	
	
	
		
 

			




	
	
	
		
 
            // For a single n,tau take samples over several instances of

			




	
	
	
		
 
            // the degree distribution

			




	
	
	
		
 
            for (int degreeSample = 0; degreeSample < 200; ++degreeSample) {

			




	
	
	
		
 
                // Generate a graph

			




	
	
	
		
 
                // might require multiple tries

			




	
	
	
		
 
                for (int i = 1; ; ++i) {

			




	
	
		
 
@@ -109,25 +109,25 @@ int main() {

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                SwitchChain chain;

			




	
	
	
		
 
                if (!chain.initialize(g)) {

			




	
	
	
		
 
                    std::cerr << "Could not initialize Markov chain.\n";

			




	
	
	
		
 
                    return 1;

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                std::cout << "Starting switch Markov chain with n = "

			




	
	
	
		
 
                          << numVertices << ", tau = " << tau << ". \t"

			




	
	
	
		
 
                          << std::flush;

			




	
	
	
		
 

			




	
	
	
		
 
                constexpr int mixingTime = 15000;

			




	
	
	
		
 
                constexpr int mixingTime = 20000;

			




	
	
	
		
 
                constexpr int measureTime = 10000;

			




	
	
	
		
 
                constexpr int measureSkip =

			




	
	
	
		
 
                    100; // Take a sample every 100 steps

			




	
	
	
		
 
                constexpr int measurements =

			




	
	
	
		
 
                    (measureTime - 1) / measureSkip + 1;

			




	
	
	
		
 
                int movesDone = 0;

			




	
	
	
		
 

			




	
	
	
		
 
                int triangles[measurements];

			




	
	
	
		
 

			




	
	
	
		
 
                for (int i = 0; i < mixingTime; ++i) {

			




	
	
	
		
 
                    if (chain.doMove())

			




	
	
	
		
 
                        ++movesDone;

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: kalli-3869095
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support