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

Changeset - cd465118bb78

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Tom Bannink - 8 years ago 2017-03-13 13:10:40
tom.bannink@cwi.nl

Update TODO list in Mathematica notebook

1 file changed with 10 insertions and 8 deletions:

showgraphs.m

0 comments (0 inline, 0 general)

showgraphs.m

➞

Show inline comments

@@ @@ -5,38 +5,40 @@ Needs["ErrorBarPlots`"] @@
 (* ::Section:: *)
 (*TODO*)
 (* ::Text:: *)
 (*- Experimental mixing time as function of n. At (n,tau)=(1000,2.5) it seems to be between 10.000 and 20.000 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 direct triangle counting? (I doubt it)*)
 (*   (b') Better triangle counting by only keeping track of CHANGES in #triangles*)
 (*   (c) Do not choose the three permutations with 1/3 probability: choose the "staying" one with zero probability. Should still be a valid switch chain?*)
 (**)
 (*- Experimental mixing time as function of n. At (n,tau)=(1000,2.5) it seems to be between 10.000 and 20.000 steps.*)
 (**)
 (*- Count #moves that result in +-k triangles (one move could create many triangles at once!)*)
 (**)
 (*- Improve runtime*)
 (*   (a) Better direct triangle counting? (I doubt it)*)
 (*   (b) Better triangle counting by only keeping track of CHANGES in #triangles*)
 (* ::Subsection:: *)
 (*Done*)
 (* ::Text:: *)
 (*- Do a single very long run: nothing weird seems to happen with the triangle counts. Tried 10 million steps.*)
 (**)
 (*- 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)]) .*)
 (*  Computing the f(i,j) = (1-Exp[..]) terms is fine, but then computing Sum[ f(i,j) f(j,k) f(i,k) ) ] over n^3 entries is very slow.*)
 (*  *)
 (*  - Improve runtime*)
 (*   (a) Don't remove/add edges from the std::vector. Simply replace them. Done, is way faster for large n.*)
 (*   (b) Do not choose the three permutations with 1/3 probability: choose the "staying" one with zero probability. Should still be a valid switch chain?*)
 (*  *)
 (*  *)
 (* ::Section:: *)
 (*Visualize graphs*)

0 comments (0 inline, 0 general)