Woong Kook (국웅), A Combinatorial Formula for Information Flow in a Network

In 1989, Stephenson and Zelen derived an elegant formula for the information I_ab contained in all possible paths between two nodes a and b in a network, which is described as follows. Given a finite weighted graph G and its Laplacian matrix L, the combinatorial Green’s function , of G is the inverse of L+J, where J is the all 1’s matrix. Then, it was shown that I_ab=(g_aa+g_bb-2g_ab)^-1, where g_ij is the (i,j)-th entry of . In this talk, we prove an intriguing combinatorial formula for I_ab:

,

where is the complexity, or tree-number, of G, and G_a*b is obtained from G by identifying two vertices a and b. We will discuss several implications of this new formula, including the equivalence of I_ab and the effective conductance between two nodes in electrical networks.