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

Changeset - c039c549918d

Parent rev.

Child rev.

[Not reviewed]

0 2 2

Tom Bannink - 8 years ago 2017-02-20 16:28:34
tombannink@gmail.com

Add start of triangle counting for powerlaws

4 files changed with 75 insertions and 23 deletions:

cpp/power_law_sampling_0706.1062.pdf

bin+new file

cpp/showgraphs.m

cpp/switchchain.cpp

cpp/triangle_counting_algorithms.pdf

bin+new file

0 comments (0 inline, 0 general)

cpp/power_law_sampling_0706.1062.pdf

➞

Show inline comments

		new file 100644
		binary diff not shown

cpp/showgraphs.m

➞

Show inline comments

 (* ::Package:: *)
 Needs["ErrorBarPlots`"]
 (* ::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]]];
 Grid[Partition[gs,10],Frame->All]
 (* ::Section:: *)
 (*Plot triangle counts*)
 gsraw=Import[NotebookDirectory[]<>"graphdata.m"];
 Map[ListPlot[#[[2]],Joined->True,PlotRange->All]&,gsraw[[1;;3]]]
 averages=Map[{#[[1]],Mean[#[[2,-1000;;-1]]]}&,gsraw];
 averagesGrouped=GatherBy[averages,#[[1]]&];
 averagesErrorBars=Map[
 {{#[[1,1]],Mean[#[[All,2]]]},
 ErrorBar[StandardDeviation[#[[All,2]]]/Sqrt[Length[#]]]
 }&,averagesGrouped];
 ErrorListPlot[averagesErrorBars,Joined->True,PlotMarkers->Automatic,AxesLabel->{"n","\[LeftAngleBracket]triangles\[RightAngleBracket]"}]

cpp/switchchain.cpp

➞

Show inline comments

 #include "exports.hpp"
 #include "graph.hpp"
 #include <algorithm>
 #include <fstream>
 #include <iostream>
 #include <numeric>
 #include <random>
 #include <vector>
 #include "graph.hpp"
 #include "exports.hpp"
 // Its assumed that u,v are distinct.
 // Check if all four vertices are distinct
 bool edgeConflicts(const Edge& e1, const Edge& e2) {
     return (e1.u == e2.u || e1.u == e2.v || e1.v == e2.u || e1.v == e2.v);
+}
@@ @@ -64,20 +64,35 @@ class SwitchChain { @@
     std::mt19937 mt;
     std::uniform_int_distribution<> edgeDistribution;
     std::uniform_int_distribution<> permutationDistribution;
 };
 int main() {
     // Goal:
     // 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
     Graph g;
     std::ofstream outfile("graphdata.m");
     outfile << '{';
     bool outputComma = false;
     for (int numVertices = 500; numVertices <= 1000; numVertices += 100) {
         // Generate a random degree sequence
         std::mt19937 gen(std::random_device{}());
     // 50 nodes with average degree 12
     DegreeSequence ds(50);
     std::poisson_distribution<> degDist(7);
         // average degree 12
         DegreeSequence ds(numVertices);
         std::poisson_distribution<> degDist(12);
         // For a single n, take samples over several instances of
         // the degree distribution
         for (int degreeSample = 0; degreeSample < 10; ++degreeSample) {
             // Try at most 10 times to generate a valid sequence
             bool validGraph = false;
             for (int i = 0; i < 10; ++i) {
                 std::generate(ds.begin(), ds.end(),
                               [&degDist, &gen] { return degDist(gen); });
@@ @@ -89,42 +104,51 @@ int main() { @@
             if (!validGraph) {
                 std::cerr << "Could not create graph from degree sequence.\n";
                 return 1;
+            }
             std::sort(ds.begin(), ds.end());
     std::cout << "Degree sequence:";
     for (auto i : ds)
         std::cout << ' ' << i;
     std::cout << std::endl;
             //std::cout << "Degree sequence:";
             //for (auto i : ds)
             //    std::cout << ' ' << i;
             //std::cout << std::endl;
             SwitchChain chain;
             if (!chain.initialize(g)) {
                 std::cerr << "Could not initialize Markov chain.\n";
                 return 1;
+            }
     std::ofstream outfile("graphdata.m");
     outfile << '{';
     outfile << '{' << g;
             std::cout << "Starting switch Markov chain" << std::endl;
             constexpr int mixingTime = 15000;
             constexpr int measureTime = 5000;
             int movesDone = 0;
     constexpr int movesTotal = 10000;
     int triangles[movesTotal];
     for (int i = 0; i < movesTotal; ++i) {
             int triangles[measureTime];
             for (int i = 0; i < mixingTime; ++i) {
                 if (chain.doMove())
                     ++movesDone;
+            }
             for (int i = 0; i < measureTime; ++i) {
                 if (chain.doMove())
                     ++movesDone;
                 triangles[i] = chain.g.countTriangles();
         if (i % (movesTotal / 50) == (movesTotal / 50 - 1))
             outfile << ',' << chain.g;
+            }
     outfile << '}' << ',' << '{' << triangles[0];
     for (int i = 1; i < movesTotal; ++i)
             if (outputComma)
                 outfile << ',';
             outputComma = true;
             outfile << '{' << numVertices << ',' << '{';
             outfile << triangles[0];
             for (int i = 1; i < measureTime; ++i)
                 outfile << ',' << triangles[i];
             outfile << '}' << '}';
     std::cout << movesDone << '/' << movesTotal << " moves succeeded."
               << std::endl;
             std::cout << movesDone << '/' << mixingTime + measureTime
                       << " moves succeeded." << std::endl;
+        }
+    }
     outfile << '}';
     return 0;
+}

cpp/triangle_counting_algorithms.pdf

➞

Show inline comments

		new file 100644
		binary diff not shown

0 comments (0 inline, 0 general)