matrix_rain
pygraphblas
matrix_rain | pygraphblas | |
---|---|---|
1 | 7 | |
21 | 338 | |
- | 0.0% | |
10.0 | 0.0 | |
over 1 year ago | 5 months ago | |
Python | Python | |
MIT License | Apache License 2.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
matrix_rain
pygraphblas
-
Large Photonic Processor Solves Graph Problems
This is interesting to me because it's advancing the work on the notion of quantum graph problem solving.
I'm sure we've all heard how quantum computers can be used in the future to decrypt information from today. There's a lot of research out there on how QC may be able to efficiently factor large semiprimes and bust our existing cryptographic algorithms, but to me this is the more mundane side of QC.
The exciting side to me is that many graph problems, particularly whole graph problems like connectivity and shortest paths have a potential quantum advantage. This is particularly advantageous for sparse and hypersparse graphs that have billions of nodes but relatively low node degree. Language Models, chemical assay databases, proteomics, causal inference, and fraud detection are just a few problems that involve huge sparse graphs that could get a huge boost from quantum.
And to show my own bias here [1], I think the future of graph algorithms, including quantum, is expressing them in Linear Algebraic form with the GraphBLAS API. Using the GraphBLAS, you can write your algorithm in a mathematical form using the multiplication of adjacency matrices that is then synthesized to some optimal form for a given architecture.
The same code you write can then be run on a variety of backends, currently CPUs and CUDA using SuiteSparse's new JIT, but soon FPGAs and yes, quantum computers. Parallelism will become so broad and conceptually divergent that you won't even be able to conceive of an efficient hand written single function for all possible platforms.
[1] https://github.com/Graphegon/pygraphblas
- pygraphblas/Introduction-to-GraphBLAS-with-Python.ipynb at main · Graphegon/pygraphblas
- GraphBLAS with Python
-
APL deserves its Renaissance too
Yes, multiplying graph adjacency matrices over a min-tropical semiring produces shortest paths. APL supports this syntactically, but how does it function in the real world? What if the matrices are extremely sparse, like almost all real world graphs are? Syntax is the easy the problem. The hard problem is having very sparse graphs with billions of nodes and many billions of edges. How is your square matrix going to deal with that? Sparse and hypersparse graph computing is hard, which is not syntactically relevant.
Python does not have this terse a syntax, but it gets very close with multiple bindings to the SuiteSparse GraphBLAS Hypersparse graph processing libraries, which intrinsically supports sparse graphs and a very large number of operators, including the tropical min/max ones. Suitesparse doesn't provide syntax (that's the easy part), it provides the hard part, sparse and hypersparse data structures and very complex dynamic, parallel graph processing optimizations including JIT compilation of GPU accelerated operations.
Here's a notebook that shows your shortest path example using Python and the GraphBLAS. While it's a trivial example, it can scale the the largest graphs possible to use today using SuiteSparse:
https://github.com/Graphegon/pygraphblas/blob/main/demo/Intr...
-
Math Ventures Club
Using Linear Algebra to solve Graph problems, in particular, algebra over Tropical Semirings. Here's a great, but not graph specific, introduction to the advanced math behind the subject by Madeline Brandt:
https://www.youtube.com/watch?v=S_bVv7Lau-s
There is an open source effort to bring this style of mathematical analysis to graph optimization problems (shortest path, resource scheduling, etc) called the GraphBLAS:
https://graphblas.github.io/
I am the author of the pygraphblas Python binding around the GraphBLAS library, you can find a lot of examples in the demo notebooks shown in the README:
https://github.com/Graphegon/pygraphblas
- Show HN: A new Triangle Graph Centrality algorithm
- Show HN: Sierpiński and Other Kronecker Graphs with the GraphBLAS
What are some alternatives?
telegram - A Matrix-Telegram hybrid puppeting/relaybot bridge
NetworkX - Network Analysis in Python
libmaths - A Python library created to assist programmers with complex mathematical functions
global-chem - A Knowledge Graph of Common Chemical Names to their Molecular Definition
duckyPad - Do-It-All Mechanical Macropad
traph - A terminal/cmd graph algorithm visualiser
array-language-comparisons - A comparison of array languages & libraries: APL, J, BQN, Uiua, Q, Julia, R, NumPy, Nial, Futhark, Dex, Ivy, SaC & ArrayFire.