Como funcionam matriz de adjacência, lista de adjacência e matriz de incidência?

Nos meus estudos sobre representação de grafos, aprendi que existem três formas principais: matriz de adjacência, lista de adjacência e matriz de incidência. No começo fiquei em dúvida sobre quando usar cada uma.

• A matriz de adjacência é uma tabela em que as linhas e colunas representam os nós.
  
• Se o grafo for não direcionado, a matriz é simétrica (ex.: se A está ligado a B, então B também está ligado a A).
• Se o grafo for direcionado, a matriz não é necessariamente simétrica: a posição [A,B] pode ter valor (aresta de A para B), mas [B,A] pode estar vazia (não existe volta).
• Isso mostra claramente a direção das conexões.
• A lista de adjacência é mais eficiente para grafos grandes, pois lista apenas os vizinhos que realmente existem para cada nó.
• A matriz de incidência relaciona nós e arestas, sendo útil em análises mais específicas, como problemas de fluxo.

Pergunta:

Qual dessas representações seria mais adequada para um grafo muito grande, com milhões de nós, mas poucas conexões entre eles?