Saturday 11:00–11:45 in Dining

The NetworkL python package

Moreno Bonaventura

Audience level:
Intermediate

Description

NetworkL.github.io is an experimental python package which supports the manipulation and efficient (L)ongitudinal analysis of large-scale time-varying graphs. NetworkL reduces the memory load of the Distance Matrix up to 50% and performs re-computation of shortest paths in centiseconds after edges updates. The package opens the possibility to perform real-time network analysis on streaming data.

Abstract

Graphs are the most popular way to represent and analyse a variety of real-world system and data sets from different domains. Today data grow fast and change rapidly over time.

NetworkL (http://networkl.github.io/) is an experimental python package I wrote to supports the manipulation and efficient (L)ongitudinal analysis of large-scale time-varying graphs. NetworkL includes a set of optimized algorithms and data structures which create the basics to carry out network analysis of large time-varying networks even on commodity workstations.

In particular it implements a smart way to representation the full distance matrix of the network as a sparse matrix. This reduces the memory load up to 50%. Moreover, NetworkL include an implementation of the Ramalingam&Reps algorithm to recompute all the shortest paths length. Re-computations are performed in centiseconds regardless of the graph size. This performances makes NetworkL particularly suitable for the analysis of (L)ongitudinal network data-sets.

Biblio: Ramalingam, G., & Reps, T. (1996). On the computational complexity of dynamic graph problems. Theoretical Computer Science, 158(1), 233-277.