Summary of recent ideas

1014 Recent Ideas

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)
    * Given the edges defined as the nodes, we have a Markov Chain with transition matrix defined as 
$$P(e_{ab}, e_{cd}) = 
\begin{cases} 
1/(k_b-1) & \text{if $e_{ab}$ and $e_{cd}$ share common node $b$} \\
0 & otherwise
\end{cases}  
$$

----


![](http://i1336.photobucket.com/albums/o641/00zzj/13_ExpDrawing_zps2b4367cf.png)

**_Theorem_**: Given an edge-induced graph and two nodes $a$ and $b$ (i.e. two edges in the original graph), its common neighbors forms a complete graph. Denote the set of their common neighbors as $D$, and $d=|D|$. Assume the edge between $a,b$ is a cross-cutting edge, and the optimal cut divides the d common neighbors into two groups: $(d-c)/2$ and $(d+c)/2$, and for all possible subset of $M\subset D$, then $$|M|(|M|-c)\leq E_{M}(d+1), $$ where $E_{M}$ is the sum of the probability flow of external edges of $M$.


**_Proof_**: Proof by contradiction. We need to find  $M_0\subset D$ such that $$|M_0|(|M_0|-c)> E_{M}(d+1),$$and the configuration/partition of $D$ is impossible. As indicated in the theorem, edge $e_{ab}$ is a cross-cutting edge, then we need to prove 
$$  m_0\left(\frac{d-c}{2} + 1\right)\frac{1}{d+1}  > \frac{1}{2}\left(m_0\left( \frac{d-c}{2} + 2 + \frac{d+c}{2} - m_0 \right)\frac{1}{d+1} + E_{M_0}\right), $$where $m_0 = |M_0|$. The left side is the number of cross-cutting edges that are associated with $M_0$, and the right side is half of the total number of edges that are connected to $M_0$ (the internal edges in $M_0$ are not counted). If this inequlity holds, then we can drag $M_0$ from one side of the optimal cut to the other, which flips the cross-cutting edges and non-cross-cutting edges. Thus it yields to smaller number of total cross-cutting edges, which contradicts to the assumption in the theorem.

The inequality can be simplified as $$m_0(m_0-c)>E_{M_0}(d+1),$$ Q.E.D.


Observations
-----------

There are some observation of the theorem:

* $c$ is the difference between two partitions of $D$.
* If there exists $E_{M_0} = 0$, then $c\neq 0$, which means the common neighbors cannot be divided evenly.
* If $c>0$, and there exists $E_{M_0}(d+1) < m_0(m_0-c)$, then the current configuration is impossible, and the worst case scenarios for the new partitions is $c \leftarrow c+1$.
* We can continuously let $c \leftarrow c+1$ until there are no subset of $M_0\subset D$ satisfied that
$$E_{M_0}(d+1) < m_0(m_0-c),$$ we denote the largest possible $c$ as $c^*$.


**_Lemma_**: Given edge-induced graph $\tilde{G}$, and for any $a,b$ in the graph, if 
$c^*>1$, then edge $e_{ab}$ cannot be cross-cutting.



**_Proof_**: Assume edge $e_{ab}$ is cross-cutting, there must be at least $(d+c^*)/2$ cross-cutting edges connecting to either $a$ or $b$ (without losing generality, let it be $a$). Since 
$$
\begin{align}
 (d+c^*)/2(d+1) > \frac{1}{2}\max\{w_a, w_b\}  &= \frac{1}{2} \\
 \Rightarrow  c^* &>1,
\end{align}
$$ where $w_a = \sum_{x}P(a,x) = 1$. Then edge $e_{ab}$ cannot be cross-cutting. Therefore, if $c^*>1$, we can drag $a$ from one side of the optimal cut to the other, which yields to smaller number of cross-cutting edges. Q.E.D.