Non-backtracking RW

NBRW

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)