----- > [!proposition] Proposition. ([[bipartite graph projection's adjacency matrix is nearly gramian]]) > Let $G$ be a [[bipartite graph]] with [[incidence matrix]] $\b B$. The [[projection of a bipartite network|projection of]] $\b B$ onto its items equals $\b B^{\top} \b B - \text{diag}(\b B^{\top}\b B).$ > (That is, it equals $\b B ^{\top}\b B$ with all [[diagonal]] elements set to zero.) > \ > The projection of $\b B$ onto its groups equals $$ > [!proof]- Proof. ([[bipartite graph projection's adjacency matrix is nearly gramian]]) > Recall that $b_{ij}=\text{(edge weight)}$ if item $j$ belongs to group $i$ and $0$ if not. WLOG all edge weights equal $1$ (so $\b B$ is just an unweighted [[incidence matrix]]). Let $g$ denote the number of groups in $G$. > > Let $P$ denote the [[adjacency matrix]] of the [[projection of a bipartite network|projection]] of $G$ onto its items. Write $P_{ij}=w$ iff items $i$ and $j$ share a group in common and $0$ if not, where $w$ denotes the number of groups they share. > > The product $B_{ki}B_{kj}$ also equals $1$ iff $i$ and $j$ share the group $k$ in common and $0$ if not. To find out how many groups $w$ that $i$ and $j$ share in common we check over all $k$: $w=\sum_{k=1}^{g} B_{ki}B_{kj}=\sum_{k=1}^{g}(B_{}^{\top})_{ik}B_{kj}= (B^{\top})_{:,i}B_{j,:}.$ > By [[matrix product|matrix multiplication dot product formulation]], this corresponds to entry $ij$ of $B^{\top}B$. Thus we conclude that $P=B^{\top}B$ with weights organized as discussed. ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```