2A

A: Interpreting Graph-like Artifacts Upon landing, the archeologists discover a large cache of alien artifacts supposedly left by a (now-extinct) civilization. The magnetic-storage facilities found in alien underground cities contain much data, a significant part of which appears to be the description of about 10000 giant Graphs (each includes from 1 to 10 million nodes and from 10 to 100 million undirected edges). Our linguists are working day and night to decode the accompanying documents, but with very little success so far (we are not even sure if the aliens’ language was an alphabet-based one). In this situation, unfounded speculations about the true nature of the Graphs are rampant within your expedition. Some suspect that the Graphs encode a network of pre-desert rivers and streams on Ares, others argue that these are the schemes of intergalactic trade routes, yet others surmise that we are dealing with large-scale back-ups of all-Aresian WorldWideWeb, and the well-informed few are confident that these are the long-lost maps for the advanced bonus levels of DukeNukem3D. You (+ the other two GraphTheorists in the expedition) decide to use the properties of the graphs themselves to rule out some of these ludicrous versions. You set out to determine the likely features of Graphs (number of connected components, distribution of node-degrees, etc) based on the way in which they were created: **by an instantaneous process OR by a prolonged growth (nodes and/or edges added over time) OR by a "compounded" growth (the well-connected nodes are more likely to become even-better-connected in the future) OR by "merger" growth (several large sub-graphs merge to create a super-Graph); ** by a single omnipotent Creator OR by cooperating (or competing ?) co-authors; ** modeling a civilization-made object OR some natural phenomena; ** modeling something random (or chaotic?). You should 1) develop models and determine the "signatures" (i.e., the collections of graph-traits) corresponding to as many of the above "graph-creation-modes" as you can; 2) design algorithm(s) to determine the likely creation-mode of a given Graph (Note: given the large size of the graphs in question, the ability to quickly rule-out some creation-modes (by working with a randomly selected sub-graph) would be a big advantage.); 3) test your algorithms on simulated graphs (illustrating different creation-modes) and on some large graph available on the Web (e.g., a graph of web-sites related to a specific key-word; see http://www.cs.cornell.edu/Courses/cs685/2002fa/data/gr0.California).