To Do

1. Finish the abstract.
2. Investigate the connected component claim of the 2003 paper that finding connected components in an evolving graph is NP Complete
   • Is it NPC? What part of the temporal aspect makes it NPC?
     • Would it still be NPC in our different temporal domains? Clearly there would be variation from a single point in time to an interval to multiple points in time.
   • What is the definition of a connected component in a temporal graph?
     • How would that change if we use the different notions of temporal domain (now, interval, disjoint interval, all time)?
   • Would it have different meanings at different time points?
3. Revisit the 2012 Temporal clustering paper
   • What do they mean by cluster? temporal cluster?
4. Look at the wikipedia datasets. Does an article node change over time? If the article is merged with another, is that reflected? Or if an article is split?
   • Are there document-document edges along with editor-document edges?

Notes

1. We have these different notions of time that we want to investigate. Different “places” to do our temporal measures:
   • Now (single point in time)
   • Contiguous Interval (interval with start and end points, inclusive)
   • Non-contiguous Interval (set of intervals, with some points in time not included, possibly disjoint)
   • All time (every point in time)
2. For disjoint intervals, how do we look at the gaps and include edges or nodes?
   • Do we include edges that are extant completely across the gap(s)?
     • Edges or nodes that exist in all intervals included?
     • Edges or nodes that exist throughout the gaps are included in the interval? That is, for an edge to be considered in a disjoint interval, it must continue to exist from the end of one interval through the beginning of the next to be considered.
3. We need to look back at how vertices change over time
   • We originally had a notion that connectedness is important based on some inherent characteristics of the node
   • So, for example, we only want to consider circuses that have more than 3 travelling groups
     • When a circus gains a third or loses its third group, the node changes importance to us. It changes whether or not we consider it, or how we rank it.
   • Or, another example, we only want to consider wikipedia articles that have $x$ or more words from a specific list in them.
     • When an article is edited and the $x$th word is added by the editor, that document is now more important to us, or important enough to include as a node in our graph
     • When the $x$th word is removed so the article only has $x-1$ special words, we then treat that document differently
   • Filtering vertices out that don’t have the properties we’re looking for.
     • Alternatively treating them differently