Optimal data structure for a time-windowed streaming graph in order to compute fast statistics
There's an efficient streaming algorithm for computing the average degree.  Note that if you have the sum of the degrees and the number of vertices, you can compute the average -- so we'll try to keep track of those two values.

Also note that if you delete or insert an edge, it is easy to update the sum of the degrees.  If you delete or insert a vertex, it is easy to update the number of vertices.

Taking all of this into account, we do $O(1)$ work (amortized) per time step, and at every time step we can infer the average degree.  This is as efficient as one could possibly hope for.