Slowly changing weighted random choice data structure

I am writing a stochastic simulation in python which involves a changing bipartite multi-graph (or equivalently a normal graph with edges with integer weights), and includes randomly drawing edges and nodes from each set of nodes, and modifying them.

What kind of data structure or data structures do I need to store my graph in, if I do need the following operations with roughly the following frequencies, and I care about speed as long as the memory stays below 3GB?

Remove an edge                  1000000
Add a new node-1                 200000 (plus at setup)
Add a new node-2                      0 (except at setup)
Draw a random edge              1750000
Add an existing edge             750000 (plus at setup)
Add a completely new edge        300000 (plus at setup)
Copy the data structure            2500 (and 100 manual setups)

I am currently storing a pandas.Series, mapping a multi-index describing the pairs (node-1, node-2) to Integer weights. This leads to the series' setitem method hogging ca. 40% of computation time, from ca. 300000 calls, which is whenever I add a new node-1 plus at setup. (The other adjustments are done using series.values[i:] += 1 and similar.)

I have considered using an OrderedDict, but the weighted random choice (which makes the majority of calls) needs index access to the values (for bisecting) and keys (for returning them), which the class does not provide.

What should I use?