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

A Combinatorial Formula for Information Flow in a Network

Woong Kook (국웅)
Department of Mathematics, University of Rhode Island, Kingston, Rhode Island, U.S.A.

2010/04/09 Fri 4PM-5PM

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 $\mathcal{G}$ , 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 $\mathcal{G}$ . In this talk, we prove an intriguing combinatorial formula for I_ab:

$I_{ab}=\kappa(G)/\kappa(G_{a\ast b})$ ,

where $\kappa(G)$ 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.

Tags: 국웅

This entry was posted on Thursday, March 25th, 2010 at 3:00 pm and is filed under 2010, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.