Reliability polynomial calculation
Some suggestions:


_recursive isn't a particularly descriptive name. A lot of things can be recursive. _relpoly_recursive may be a better name. 
You can factor out the Poly call

s = sympy.Poly(p*rec_contracted + (1-p)*rec_deleted, p)


also note that I've removed the redundant parentheses. 
Calling simplify on the result is completely useless, since rel is a Poly and Poly instances are always stored in canonical (expanded) form. 
What is the value of going through the edges randomly? Don't you end up going through all of them.
As I noted in a comment, modifying the graph in-place seems problematic. I can't tell for sure just by looking at the code if it does the right thing or not. It seems that you should rather move the 

H = nx.MultiGraph(G)


line to the top of the recursive function, and operate on H instead of G in the function.