1
$\begingroup$

I apologize if this is the wrong place or too trivial a question for this community. What is the best data structure to store a time-windowed streaming graph in order to compute fast statistics over all nodes in the graph, for e.g., running computation of average degree?

I believe the best way to describe this is as follows: Let $G=(V,E)$ be a sparse time-evolving network modeled as an undirected graph with $n$ nodes and $m \geq n$ edges over time (in hours) $t = t_0, t_1, \dots $. Suppose further, that at any time point $t_i$, any edges that are more than $k$ hours are removed. In addition, nodes that have no edges connecting to it are removed.

My idea (for e.g. the average degree) is as follows: keep track of an array of edge arrival times as well as a degree array of size $n$ where each element represents the total degree. At any new time point $t_i$, we would add 1 to the degree array corresponding to the two nodes with the new edge. We would then remove all edges that are older than $k$ hours (i.e. added before $t_i-k$). Any nodes that are edge-less are removed. At all time points, a running average of the degree is computed by taking the average of the degree array.

If I'm not mistaken, this algorithm would be $O(n)$ in run-time and $O(n)$ in space. Is there any better way of doing this?

The best data structure I could find from previous posts such as this one, recommend adjancency lists. Additionally, is there any advantage in using disjoint set data structures such as in the post here?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! 1. I find the description hard to follow. What is the meaning of $time(e)$? Why are the times $t_0,t_1,\dots,$ rather than $0,1,\dots$? What does "more than $k$ time older than the newest $t_i$" mean -- can you be more precise, and formulate this into a condition in terms of $time(\cdot)$ and $t_i$ and $k$? 2. Can you be any more precise about "best"? What metric would you like to minimize? Worst-case running time per update? Amortized time? Something else? $\endgroup$ – D.W. Nov 5 '15 at 20:44
  • $\begingroup$ Sorry for the confusion. I meant to say, at each time point $0, 1, \dots$, we receive a new set of nodes and edges. We add these nodes and edges to the graph. I mean to say $time(e)$ just to keep track of which edge was added at what time. I realize now that this is a poorly written description on my part. $\endgroup$ – rshroff08 Nov 5 '15 at 21:09
  • $\begingroup$ By "more than $k$ time older$, we remove all edges that were added before some finite amount of time. For instance, 1 hour before the latest edge and node information was received. 2. I want to have small space requirement and improve worst-case running time per update. $\endgroup$ – rshroff08 Nov 5 '15 at 21:17
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.