Graphs, Networks and Applications

The space of all undirected graphs (while countable) is unbounded. But, it is seldom treated as a homogeneous domain such as the ``integers'', or an algebraic ``field'' of order 2. This is a mistake.

``Closure'' has proven to be one technique for exploring the space of ``networks'' which can be considered to be very large graphs with several hundreds of nodes. The can be undirected (symmetric), directed (asymmetric) or mixed. While there are many statistical methods of analyzing networks, they tend to yield only global properties. Closed set analysis can reveal much finer detail.

One analytic technique is reduction. All nodes are closed in an irreducible network. The irreducible ``core'' of any network is unique (upto isomorphism). In this irreducible core, every node is a part of a chordless circuit of length 4, or more. Thus they are the exact antithesis of chordal graphs. They are often an order of magnitude smaller. Consequently, they can be used to identify local network features of interest.

The reduction process used to emphasize the global structure of a network can also be used to define a similarity relation which partitions the domain of all undirected graphs.