Skip to content

Instantly share code, notes, and snippets.

@zhouzhuojie
Created August 16, 2013 15:17
Show Gist options
  • Save zhouzhuojie/6250807 to your computer and use it in GitHub Desktop.
Save zhouzhuojie/6250807 to your computer and use it in GitHub Desktop.
Non-backtracking RW
Non-backtracking RW
=====================
Preview URL:
http://bit.ly/16U4JHf
Basic Idea
-------------
1. Push $P'(e_{ij}, e_{jk}) \geq P(j,k) $
2. However, overall the best non-backtracking probability $P'(e_{ij}, e_{jk}) = \frac{1}{k_j-1}$
Current Progress
-------------
* Divide the neighbors into two groups, $C_1$ and $C_2$
* if $|C_1| = |C_2|$, trivial, pick another one in the opposite group
* if $|C_1| \neq |C_2|$, arbitrarily take one node $v$ from the larger group:
* we now have three groups: $\{v\}, C_1, C_2$
* make sure each node has the probability of $\frac{1}{d-1}$ being picked.
Current Experimental Results (Updating, using corrected probability now.)
--------------
##### NRMSE $[y]$ vs Degree $[x]$
Graph: as733
![](http://i1336.photobucket.com/albums/o641/00zzj/BTRW/cnrmse_as733_zpsb154de01.png)
Graph: facebook0
![](http://i1336.photobucket.com/albums/o641/00zzj/BTRW/cnrmse_facebook0_zpsb9130d77.png)
##### NRMSE $[y]$ vs Query Cost $[x]$
Graph: as733
![](http://i1336.photobucket.com/albums/o641/00zzj/BTRW/nrmse_facebook0_zps540fe87b.png)
Graph: facebook0
![](http://i1336.photobucket.com/albums/o641/00zzj/BTRW/nrmse_as733_zps7aa35cab.png)
Graph: facebook107
![](http://i1336.photobucket.com/albums/o641/00zzj/BTRW/nrmse_facebook107_zpsed49a1c0.png)
Graph: facebook1912
![](http://i1336.photobucket.com/albums/o641/00zzj/BTRW/nrmse_facebook1912_zps10b60175.png)
Graph: facebook3437
![](http://i1336.photobucket.com/albums/o641/00zzj/BTRW/nrmse_facebook1912_zps10b60175.png)
Brainstorming
----------
* Divide nodes into groups
* if two nodes belongs to the same cluster, put them in the same group
* if two nodes belongs to different cluster, put them in different groups
* (This is quite similar to stratified sampling...)
* Apply MTO to assist us dividing groups
* Non-cross-cutting edges => same group
* Cross-cutting edge => different group
* Groups allocation as the theory background
* Referrence
* _Improving Asymptotic Variance of MCMC Estimators: Non-reversible Chains are Better_, Technical Report, from Department of Statistics, University of Toronto, July 2004. [pdf](http://arxiv.org/pdf/math/0407281v1.pdf)
* Talks about how to improve the asymptotic variance of MCMC estimators
* Based on Non-reversible Chains
* _Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling._ Sigmetrics 2012. [pdf](http://arxiv.org/pdf/1204.4140v1.pdf)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment