Rex Zhou zhouzhuojie
zhouzhuojie
/ 9.12 Theorems and Experiments
Created
September 13, 2013 00:42
9.12 Theorems and Experiments
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| NB_DEGREE_2: Divide the neighbors into 2 groups | |
| NB_DEGREE_4: Divide the neighbors into 4 groups | |
| Facebook0 | |
|  | |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|  | |
|  | |
| ---- | |
|  |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ### as 733, zoomed | |
|  | |
|  | |
| ### facebook0, zoomed | |
|  | |
|  |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Recent Ideas | |
| ============ | |
| Edge-induced Graph | |
| ----------------- | |
| * Edge-induced Graph | |
| * Edge -> Node (Mapping edges into nodes) | |
| * From edge to edge, the probability is associated with the node that connecting two edges, i.e. the probability of transfer from edge $e_{ab}$ to $e_{bc}$ is $\frac{1}{k_b-1}$ (non-backtrack to its self) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Recent Ideas | |
| ============ | |
| Edge-induced Graph | |
| ----------------- | |
| * Edge-induced Graph | |
| * Edge -> Node (Mapping edges into nodes) | |
| * From edge to edge, the probability is associated with the node that connecting two edges, i.e. the probability of transfer from edge $e_{ab}$ to $e_{bc}$ is $\frac{1}{k_b-1}$ (non-backtrack to its self) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Recent Ideas | |
| ============ | |
| Edge-induced Graph | |
| ----------------- | |
| * Edge-induced Graph | |
| * Edge -> Node (Mapping edges into nodes) | |
| * From edge to edge, the probability is associated with the node that connecting two edges, i.e. the probability of transfer from edge $e_{ab}$ to $e_{bc}$ is $\frac{1}{k_b-1}$ (non-backtrack to its self) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|  | |
| _**Theorem** Given a graph $G$, and its corresponding edge-induced graph $G^*$. If $A, B, C$ forms an triangle in $G$, and $k_C=2$, then the edge $\{e,f\}$ is not a cross-cutting edge in $G^*$._ | |
| _**Proof**_: Prove by contradiction. Let's assume the edge $\{e,f\}$ in $G^*$ is a cross-cutting edge. When $k_C=2$, $P(e,f) = 1/2*(k_C-1) = 1/2$. Given the assumption that $e, f$ are from different partitions, so whenever we try to partition $d$ into $e's$ or $f's$ part, the probability flow connected to $e$ or $f$ must be larger than $1/2$, which makes us can simply drag the one from one partition to another to achieve smaller conductance. | |
| _**Theorem** Given a graph $G$, and its corresponding edge-induced graph $G^*$. If $A, B, C$ forms an triangle in $G$, and $k_A= 2$ and $k_B= 2$, then the edge $\{e,f\}$ is not a cross-cutting edge in $G^*$._ | |
| _**Proof**_: According to the first theorem, edge $\{e,d\}$ and $\{d, f\}$ are not cross-cutting, then edge $\{e, f\}$ cannot |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| New Experimental Result | |
| ================== | |
|  | |
| zoomed: | |
|  |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Experiments: | |
| * Only consider the 3-degree node rewiring in edge-induced graph | |
| * Not include the non-backtracking part | |
| Observations: | |
| * Previous experiments are invalid due to some implementation bugs | |
| * Only rewiring the 3-degree node is not efficient, sometimes worse than normal SRW. | |
| * The second graph's bias can be interpreted as how do we deal with the probability after removing an edge in the edge-induced graph. We can discuss about it later today. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 3-degree based rewiring only | |
| Facebook0 | |
|  | |
| Zoomed | |
|  |