Graphs vs matrices (when $0$ weight edges are allowed)

145 Views Asked by At

In short: weighted graphs are equivalent to matrices, where a $0$ entry means that an edge is absent; what if $0$ weights for existing edges is allowed?


It is often claimed, including by myself for the last 20 years, that matrices are equivalent to weighted graphs: any $n\times n$ matrix is equivalent to the graph $G=(V,E)$ where $V = \{1, 2, \dots, n\}$ and $E = \{(i,j), M_{i,j}\ne 0\}$, with weights $\omega(i,j) = M_{i,j}$.

This is based on the (generally implicit) assumption that a $0$ weight is equivalent to a non-edge, i.e. there cannot be any $0$ weight edge.

Then, one may translate many graphs concepts and problems into equivalent matrix concepts and problems, and conversely.

However, one may very well consider graphs where some existing edges have $0$ weight. In this case, weighted graphs are no longer strictly equivalent to matrices, and I am concerned by the implications of this fact.

In particular, are there graphs concepts that have no matrix equivalent when $0$ weighted edges are allowed?

Of course, one may use a special value other than $0$ for non-edges in the matrix, but what consequences would this have on matrix operations? I fear some would not make graph sense anymore.

Example:

Consider a graph of friendship relations between individuals, weighted by the number of times they met in a month, say. Certainly, having not met a friend for a month does not mean you are not friends anymore. For any pair of friends $(u,v)$, one may study the number of friends $|N(v)\cap N(u)|$ they have in common, as a function of the number of times they met $\omega(u,v)$. Certainly, the friends that did not met each other still have a higher probability to have friends in common than two random non-connected individuals.