6
$\begingroup$

If you have a graph represented by an adjacency matrix, what intuitively in terms of the original graph would low rank correspond to?

I am interested in this for both directed and undirected graphs.

This is relevant because low rank is very important in common techniques such as non-negative matrix factorization and it would be interesting to understand what the assumptions mean for graphs.

$\endgroup$
5
$\begingroup$

I'm not sure if your question is easy to answer, but I will try to provide an intuition. I am not an expert in non-negative matrix factorisation so I can't explain the connections there.

Let's restrict out attention to simple, undirected graphs $G$ with $n$ vertices. I will assume by low-rank you mean, low-rank of the adjacency matrix. These properties are derived from here Here's are a characterisation low-rank graphs:

  • the graph with no vertices is the only graph with rank 0
  • a complete bipartite graph is the only connected graph with rank 2
  • a complete tripartite graph is the only connected graph with rank 3

Rank is known to be preserved between subgraphs as follows:

  • if H is an induced subgraph of G, then $rank(H) \leq rank(G) $.
  • Let $G = G1 \cup G2 \cup··· \cup G_n$, where $G_1, G_2,...,G_n$ are connected components of G, then $rank(G) = \sum_i^n rank(G_i)$

Since the complete graph has rank $n$, it follow from this that $largest \_clique(G) \leq rank(G)$.

What is the rank of an average graph? Consider this simple model of a random graph $G$: for every pair of vertices flip a fair coin to determine whether there is an edge between them. It has been shown that with very high probability $G$ has rank $n$.

This suggests to me that low rank graphs are locally sparse or have a densely connected component but have lots of isolated vertices. A graph picked at random is likely to be full rank, however.

$\endgroup$
  • 2
    $\begingroup$ +1 for clear useful information. Note that the sense of "almost surely" in the paper you reference is nonstandard: there is always a finite chance that the rank will be less than $n$ in the random Bernoulli graph on $n$ vertices, whereas the usual meaning of "almost surely" is zero chance. $\endgroup$ – whuber Aug 23 '16 at 16:03
  • $\begingroup$ Thanks for the feedback, I've revised the answer so that it's hopefully a little clearer. $\endgroup$ – MachineEpsilon Aug 24 '16 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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