Dynamic graphs

New to Julia
1

I have been using LightGraphs.jl successfully, together with MetaGraphs.jl, and I recommend it to everybody.
I am toying with the idea of dynamic networks, where links are created and destroyed according to various prescriptions relating to degrees, and subject to different probability distributions. I know that one can add and remove edges from graphs using LightGraphs, but how efficiently. I removing edges an O(nv(graphs)) operations, or O(1)? Is it possible to remove an edge between two specific nodes? Of course, I can perform some experiments, but perhaps somebody has insight based on past experience. Also, are there alternative approaches I should consider? I am moving towards temporal networks.

Thanks!

2

In a graph g, edges are stored in g.fadjlist (“forward adjacency list”), which is a sorted vector of nodes connected to each node i.

Removing an edge between nodes i and j thus requires O(k) operations, where k = \max(\deg i, \deg j), and \deg i is the degree (number of neighbours) of node i.

3

depending on the size of your graphs, adjacency matrices might be the best option for fast edge modification

4

Keeping in mind that I could spend time on experiments, my graphs have about 250,000 nodes and about 1.5 million edges.
When you say adjacency matrix, it would have to be in sparse format. In which case, the cost is not immediately clear. If I could store the full adjacency matrix, then of course, the cost isO(1).