Topology of graph space

[maxcollard]

I'm sort of a mathematically-minded person, and so I was curious: what are the various standard topologies used graph space? What are the topological properties / invariants of graph space / various subspaces under these topologies? Since "graph random variables" are just maps from some event space to graph space, these topological properties will dramatically influence the behavior of such maps.

Also, Jovo mentioned in class that there are ways of measuring "distance" between graphs, which implies that there are metrics on graph space; this opens up a bunch of new questions related to graphs as a metric space, and all of the "niceness" that entails. What are the most common of these metrics, and as above, what are the properties of the topologies they induce on graph space?

[ElanHR]

I can't answer with too much certainty but in a graphical models course (Machine Learning in Complex Domains) we often compared graphs by comparing and matching subcliques. I believe this could work given fixed vertices but I have no idea how this would extend to dynamically adding vertices.

A clique in this case is a fully connected subgraph (eg. a node of one is always a clique, two nodes are a clique if they're connected, three nodes are a clique if they each connect to the other two etc...)

http://en.wikipedia.org/wiki/Topological_graph_theory#Graphs_as_topological_spaces

[maxcollard]

That comparison you give sounds interesting; I'd have to look at how it would fit the metric axioms.

It's notable that the article you give talks about treating a particular graph as a topological space (e.g. as a subset of R^n via a particular embedding), rather than treating the entire space of all possible graphs as a topological space. An individual graph inherits many possible topologies (at the very least from the restriction of the numerous norms on the euclidean space it's embedded in); I'm more interested in characterizing the open sets in graph space itself.

[jtmatterer]

Remember that for a fixed number of vertices, graph space only contains a finite number of points (and even in the case of a variable |V|, it is countable). Recall that a random variable is simply a function that is measurable with respect to two sigma-algebras. So, since graph space is at worst countable, we can always use the total sigma-algebra. So whatever topology you enforce on graph space wont affect the behavior of graph-valued random variables.