Constructing Adjacency Arrays from Incidence Arrays

Graph construction, a fundamental operation in a data processing pipeline, is typically done by multiplying the incidence array representations of a graph, ${\mathbf{E}}_{\mathrm{i}\mathrm{n}}$ and ${\mathbf{E}}_{\mathrm{o}\mathrm{u}\mathrm{t}}$, to produce an adjacency array of the graph, $\mathbf{A}$, that can be processed with a variety of algorithms. This paper provides the mathematical criteria to determine if the product $\mathbf{A}={\mathbf{E}}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{\mathsf{T}}{\mathbf{E}}_{\mathrm{i}\mathrm{n}}$ will have the required structure of the adjacency array of the graph. The values in the resulting adjacency array are determined by the corresponding addition $\oplus$ and multiplication $\otimes$ operations used to perform the array multiplication. Illustrations of the various results possible from different $\oplus$ and $\otimes$ operations are provided using a small collection of popular music metadata.