7
$\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.

Improve this question
$\endgroup$
1
  • $\begingroup$ If consider it is adjacency matrix of signed graph, then rank(A)=1 is equivalent to the signed graph is global structural balance. $\endgroup$
    – chloe
    Commented Mar 2 at 14:06

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\endgroup$
4
  • 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 ♦
    Commented Aug 23, 2016 at 16:03
  • $\begingroup$ Thanks for the feedback, I've revised the answer so that it's hopefully a little clearer. $\endgroup$
    – MachineEpsilon
    Commented Aug 24, 2016 at 8:16
  • $\begingroup$ "Since the complete graph has rank 𝑛" If the complete graph has self-edges (diagonal elements are one), does that collapse the rank to 1? $\endgroup$
    – Sia Rezaei
    Commented Jan 17, 2023 at 22:34
  • $\begingroup$ That would depend on the convention used to represent loops. For simple graphs, often loops are defined as adding 2 to the appropriate diagonal in the adjacency matrix. $\endgroup$
    – MachineEpsilon
    Commented Feb 13, 2023 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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