Skip to main content
edited title
Link
Ben Golub
  • 1.1k
  • 6
  • 20

Neighborhood overlap matrix for a bipartite graph -- expression for its inverse?

deleted 3 characters in body
Source Link
Ben Golub
  • 1.1k
  • 6
  • 20

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap N_j|,$$ the number of vertices in the neighborhoods of both $i$ and $j$. (So the diagonal entry $a_{ii}$ is the degree of vertex $i$.)

Another way of expressing this matrix is to consider a $n$-by-$m$ matrix $C$ such that $c_{ij}=1$ if and only if vertices $i \in V$ and $j \in W$ are adjacent in $G$; then note that $A=CC^T$. From this we see immediately $A$ is positive semidefinite.

The question: Can we find an explicit"explicit" or particularly interpretable expression for the inverse of $A$, when it exists$A$ is invertible?

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap N_j|,$$ the number of vertices in the neighborhoods of both $i$ and $j$. (So the diagonal entry $a_{ii}$ is the degree of vertex $i$.)

Another way of expressing this matrix is to consider a $n$-by-$m$ matrix $C$ such that $c_{ij}=1$ if and only if vertices $i \in V$ and $j \in W$ are adjacent in $G$; then note that $A=CC^T$. From this we see immediately $A$ is positive semidefinite.

The question: Can we find an explicit or particularly interpretable expression for the inverse of $A$, when it exists?

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap N_j|,$$ the number of vertices in the neighborhoods of both $i$ and $j$. (So the diagonal entry $a_{ii}$ is the degree of vertex $i$.)

Another way of expressing this matrix is to consider a $n$-by-$m$ matrix $C$ such that $c_{ij}=1$ if and only if vertices $i \in V$ and $j \in W$ are adjacent in $G$; then note that $A=CC^T$. From this we see immediately $A$ is positive semidefinite.

The question: Can we find an "explicit" or interpretable expression for the inverse of $A$, when $A$ is invertible?

Source Link
Ben Golub
  • 1.1k
  • 6
  • 20

Neighborhood overlap matrix for a graph -- expression for its inverse?

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap N_j|,$$ the number of vertices in the neighborhoods of both $i$ and $j$. (So the diagonal entry $a_{ii}$ is the degree of vertex $i$.)

Another way of expressing this matrix is to consider a $n$-by-$m$ matrix $C$ such that $c_{ij}=1$ if and only if vertices $i \in V$ and $j \in W$ are adjacent in $G$; then note that $A=CC^T$. From this we see immediately $A$ is positive semidefinite.

The question: Can we find an explicit or particularly interpretable expression for the inverse of $A$, when it exists?