The NetworkL python package
summary
NetworkL is a Python package that implements the Ramalingam&Reps algorithm and a sparse distance-matrix plus biconnected decomposition to shrink stored pairwise distances, reduces the memory load up to 50%, and recomputes all shortest-path lengths in centiseconds after edge updates. The code runs on commodity hardware (an 8 GB laptop) and shows big savings on sampled graphs (~20,000 nodes), trading preprocessing of a block-cut tree for fast incremental updates and substantial memory reduction versus a full n×n distance matrix.
AI-written summary · about
chapters (15)
- 0:00NetworkL introduction
- 1:11Project origins
- 3:46Why dynamic analysis matters
- 5:55Distances in graph algorithms
- 8:51Memory challenges with distances
- 11:20Sparse geodetic matrix
- 14:55BCC decomposition benefits
- 18:09Block-cut tree and distances
- 21:47Sparse BCC geodetic matrix
- 24:01Performance tests
- 27:59Time complexity trade-offs
- 29:21NetworkL Python package
- 30:34Live demo distance updates
- 33:37Real-world application in startup analysis
- 35:05Q&A
related talks
01h 12mSocial Network Analysis in Python
31mSimple Models and Exact Algorithms for Computing Network Modules
28mNetworkX is Fast Now: Graph Analytics Unleashed
02h 47mNetwork Analysis Made Simple
40mRun Large-Scale Graph Analytics Using The Most Popular Graph Analytics Library Available
32mZero Code Change GPU-Powered Graph Analytics with NetworkX and cuGraph
27m100x Faster NetworkX: Dispatching to GraphBLAS
24mNetworkX - your Unexpected Assistant for Clustering Analysis