7
$\begingroup$

My analysis of an engineering problem reduced to analysis of the Laplacian of a (random) bipartite graph. There are a few particular questions I am interested in, but not sure which direction to take at the moment. Below, I am outlining the problem. Would really appreciate any advice.

The Graph

I have an undirected weighted complete bipartite graph $G = (V_1, V_2, E)$, with $\vert V_1 \vert = n_1$, $\vert V_2 \vert = n_2$, $n_1 + n_2 \equiv n$. Each vertex from $V_1$ is connected with each one from $V_2$. $G$ is obviously connected. Edge weights are positive i.i.d. random variables: $e_{ij} \in (e_\text{min}, e_\text{max})$, where $e_\text{min},e_\text{min} \in \mathbb{R}_+$ and $e_\text{min} \ll e_\text{max}$.

The edge weights of $G$ can be represented by a (random) matrix $S \in \mathbb{R}_+^{n_1 \times n_2}$: each element of this matrix, $s_{ij}$, represents a weight of the edge that connects $v_i \in V_1$ and $v_j \in V_2$. In this case, weighted adjacency matrix, $A \in \mathbb{R}_+^{n \times n}$, and Laplacian matrix, $L = D - A$, will have the following block structures: $$ A = \begin{pmatrix} 0 & S\\ S^\top & 0 \end{pmatrix},\quad L = \begin{pmatrix} D_1 & -S\\ -S^\top & D_2 \end{pmatrix}, $$ where $D_1 = \text{diag}(\sum_{j=1}^{n_2} s_{1j}, \dots, \sum_{j=1}^{n_2} s_{n_1j})$ and $D_2 = \text{diag}(\sum_{i=1}^{n_1} s_{i1}, \dots, \sum_{i=1}^{n_1} s_{in_2})$.

Analysis and Questions

Given a graph instance, $G$, I am interested in inferring its edge weights from resistance distances I can "query" for each pair of the vertices. It can be shown that the resistance distance between $v_i$ and $v_j$ can be expressed as follows [1]: $$ r_{ij} = L^{\dagger}_{ii} + L^{\dagger}_{jj} - 2L^{\dagger}_{ij}, $$ where $L^{\dagger}$ is the Moore-Penrose pseudoinverse of the Laplacian, which can be expressed as $L^{\dagger} = (L + \frac{1}{n}J)^{-1} - \frac{1}{n}J$, where $J$ is an $n \times n$ matrix of all ones [1]. The resistance distance can be also expressed as [2]: $$ r_{ij} = \frac{\det L(i,j)}{\det L(i)} = \frac{\det L(i,j)}{\det L(j)}, $$ where $L(i)$ is denotes $L$ without the $i$-th row and column, and $L(i,j)$ denotes $L$ without $i$-th and $j$-th both rows and columns.

Given a set $\{r_{ij}\}$ for $G$, I want to resolve the above system of equations for the unknown variables $\{s_{kl}\}$.

Q1: Is it possible to show that there exists a (non-)unique solution?

The problem is that $r_{ij} = \det L(i,j) / \det L(i)$ leads to a system of polynomial equations, and I have never dealt with. Any suggestions how to approach Q1?

Q2: Suppose, the system for $s_{kl}$ is underdetermined (i.e., we don't have enough $r_{ij}$ values). Is there a way to analyze the distribution of the random graphs over the solution space, i.e., $\mathbb{P}(\{s_{kl}\} \vert \{r_{ij}\})$?

Given that determinants, $\det L(i,j)$ and $\det L(i)$, can be represented as products of the corresponding eigenvalues, Laplacian spectral theory and random matrix theory can probably be the right thing to start with. However, I am only slightly familiar with the former and have no idea whether methods of the latter can help answer my question. Do I need to take this path in my analysis, or there are better ways I should consider?

References

[1] Bapat, R. B. (2010). Graphs and matrices. Chapter 10. New York (NY): Springer.

[2] Bapat, R. B., Gutmana, I., & Xiao, W. (2003). A simple method for computing resistance distance. Zeitschrift für Naturforschung A, 58(9-10), 494-498.

$\endgroup$

1 Answer 1

2
$\begingroup$

By a strange coincidence, this circle of questions is studied in the extremely recent arXiv.org preprint by V. Vengerovsky.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.