1 Replies - 3202 Views - Last Post: 12 March 2016 - 08:01 PM

#1 nosssa  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 1
  • Joined: 12-March 16

How to reduce Adjacency Matrix memory usage

Post icon  Posted 12 March 2016 - 06:29 PM

My assignment is to read a file which describes a graph and code both, Depth first and Breadth first searches. The file contains the number of nodes in the first row and after that the nodes that make up an edge.


Similar to this example:
6
1 2
2 5
5 3
4 5
1 5
3 6

However for my assignment I need to read a non directional graph with 72.000 nodes. Even though I was able to do both searches with Adjacency lists my assignment also requires me to use adjacency matrix which uses a lot more memory (n^2).

With 72.000 nodes I'm currently using 5gb of memory just to store it, is there a way to reduce this?

I was considering the use of only half of the matrix since it is symmetrical with the other side of the main diagonal, but I'm not sure if I would be capable of performing the searches after.

If any info is missing, inform me. Thank you.

Is This A Good Question/Topic? 1
  • +

Replies To: How to reduce Adjacency Matrix memory usage

#2 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12186
  • View blog
  • Posts: 45,250
  • Joined: 27-December 08

Re: How to reduce Adjacency Matrix memory usage

Posted 12 March 2016 - 08:01 PM

Quote

I was considering the use of only half of the matrix since it is symmetrical with the other side of the main diagonal, but I'm not sure if I would be capable of performing the searches after.

You're spot on. Since the adjacency matrix is symmetric, you only need the upper triangular half or the lower triangular half. You'll have all the information necessary for these search algorithms.

Also, since the adjacency matrix entries are all 0's and 1's, you can use a byte[][] or boolean[][], which will take up less memory than storing int elements.

If you are working with large networks for more than a classroom setting, it might be worthwhile to investigate the literature on how to effectively represent graphs. This is actually a very important issue, given that much of the internet structure can be represented as a graph. For example, Google's ranking engine computes the dominant eigenvector of a stochastic matrix corresponding to a directed web graph where the directed adjacency relation corresponds to hyperlinks. The normalized Laplacian provides a lot of information regarding random walks on the underlying graph. Eigenvalues and eigenvectors of the adjacency matrix also provide insight and control into NP-Hard graph invariants like the independence number and chromatic number.

I found one such paper for large, sparse matrices.

This is a very good question. Let me feature it and move it to our Discussion Lounge forum for folks to discuss. :)
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1