2 ms·
Are the adjacency matrices in graph theory really usually dense?
by bee_rider 1y ago
Are the adjacency matrices in graph theory really usually dense?
- Malipeddi 1y agoSame thing caught my eye. They are usually sparse.
- michelpp 1y agoYep, for any decent sized graph, sparse is an absolute necessity, since a dense matrix will grow with the square of the node size, sparse matrices and sparse matrix multiplication is complex and there are multiple kernel approaches depending on density and other factors. SuiteSparse [1] handles these cases, has a kernel JIT compiler for different scenarios and graph operations, and supports CUDA as well. Worth checking out if you're into algebraic graph theory. Using SuiteSparse and the standard GAP benchmarks, I've loaded graphs with 6 billion edges into 256GB of RAM, and can BFS that graph in under a second. [2] [1] https://github.com/DrTimothyAldenDavis/GraphBLAS https://github.com/DrTimothyAldenDavis/GraphBLAS [2] https://onesparse.com/ https://onesparse.com/
- michelpp 1y agoFor a powerful sparse adjacently matrix C library check out SuiteSparse GraphBLAS, there are binding for Python, Julia and Postgres. https://github.com/DrTimothyAldenDavis/GraphBLAS https://github.com/DrTimothyAldenDavis/GraphBLAS
- contravariant 1y agoTechnically the article is saying the graphs are dense. Which might make sense, but using sparse matrices to represent sparse graphs is not unusual.
- hoten 1y agoThe article doesn't say "graphs are usually dense". It just asserts that if you use an adjacency list, the graph is likely dense. Otherwise it makes little sense to use for a sparse graph.
- devnullbrain 1y agoAn adjacency matrix seems like they gave the example most likely to irritate the mathematically inclined and confuse the outsider. Nested array access isn't that unusual.