Graphs with fractal properties?

Question

For the purposes of a research project, I am wondering if there are any resources on graphs with fractal properties, by which I mean self-similarity in particular. For instance, imagine a graph where nodes could be transformed into subgraphs that were the same as the larger graph, and their nodes could be transformed likewise, etc. I don't mean a graph that is literally exactly like that - but it should have self-similarity at different levels as if it had been created that way, with maybe a little randomness thrown in afterwards.

I was told that Expander graphs were something like what I was looking for, but from what little I understand of their definition, they seem more related to small-world theory than to what I'm looking for.

Edit: I'm because I'm trying ot figure out a way in which representations of social and geographic networks of people could be compressed, probably with significant loss but maintaining basic properties.

Answer 1

You might be interested in an object called the Random Graph http://en.wikipedia.org/wiki/Rado_graph, which "is the unique (up to isomorphism) countable graph R such that for any finite graph G and any vertex v of G, any embedding of G − v as an induced subgraph of R can be extended to an embedding of G into R. As a result, the Rado graph contains all finite and countably infinite graphs as induced subgraphs."

There is currently a very nice discussion on the n-category cafe in connection with Fraisse limits (a model theoretic approach to constructing such objects): http://golem.ph.utexas.edu/category/2009/11/fraisse_limits.html#more

Answer 2

Okay, so Steven's right -- there is a (countably infinite) graph which is totally self-similar, called the Rado graph. It's self-similar in the following way: If you partition its vertex set into two (or in general finitely many) parts, and consider the induced subgraph on each of those parts, one of those subgraphs will be isomorphic to the whole graph.

There are two other graphs with this property: the complete graph on countably infinitely many vertices, and the empty graph on countably many vertices. Up to isomorphism, these are the only countable such graphs. (or so Diestel tells me, and the proof actually isn't that hard.)

If you're looking for weaker forms of self-similarity... I'm not sure exactly what it is you want, then. You say something about "transforming nodes into subgraphs that are the same as the larger graph," but there's no reason you can't do something like that with a generic graph. There's a notion of graph product along these lines, where you replace the vertices of a graph by copies of another graph and then connect the new graphs according to the old one. So starting with a graph G, one could certainly construct $G \cdot G$, and $G \cdot G \cdot G$, and so on and so forth... but I don't know if this sequence has a limit (or even in what category that would make sense -- presumably the category of graphs and embeddings, but...)

If you want "looks the same to certain graph invariants," then expander graphs are well worth looking at.

Answer 3

You could start with graphs directly based on fractals, like the Sierpinksi Graph or the Koch Graph.

For future searching, these are called "self-similar graphs".

Answer 4

What you look for is probably pseudorandom graphs. These are graphs whose statistical properties are same on all (large) scales. More precisely, the density of edges (or more generally density of any fixed graph) is close to some constant for all subgraphs of large size. For small subgraphs, you cannot expect such properties hold since by Ramsey's theorem we can always find very special subgraph in an arbitrary graph. For a good introduction to pseudorandom graph, as well as some less common bits of knowledge, have a look at survey by Sudakov and Krivelevich. In a way of motivation, it will also be useful to get acquainted with the Szemerédi regularity lemma, as it morally says that every graph can be decomposed in a few pseudorandom graphs.

Answer 5

Related to Swapnil's point, Kronecker graphs have been used to model real large networks: see Kronecker graphs: An Approach to Modeling Networks.

Answer 6

Your idea of transforming nodes into sets of nodes sounds a lot like graph grammars — see e.g. this Wikipedia article.

Answer 7

So social networks in particular have some rather different properties than generic graphs. In particular they tend to be scale-free, which a random graph (in the usual model) probably is not.

Scale-free graphs do have some kind of self-similarity, and I'd recommend reading the literature on them. I don't know off the top of my head, though, whether scale-freeness is enough to give a good (probably lossy) compression algorithm -- presumably you know, of course, that in general you can't store a graph using fewer than O(n^2) bits. (Some naturally-occurring networks are also sparse, though, which means you can do asymptotically better with an incidence list.)

Answer 8

``Fractal properties'' is not too precise a question.

Nonetheless, here's one idea:

Let A be the adjacency matrix of an undirected graph.

Take the Kronecker product of A with itself. (Note: Kronecker product of matrices X and Y is the block matrix made of blocks X * Y_{ij}. See Wikipedia for details.)

Interpret the resulting matrix as the adjacency matrix of a graph.

By the definition of the Kronecker product, you get a kind of self-similarity. (Indeed, the adjacency matrix itself, if ``plotted'' would look like a fractal.)

I suppose a similar thing holds when you take the graph product mentioned above. (Perhaps the strong product aka co-normal product is equivalent to Kronecker product of matrices.)

Answer 9

You may consider Cayley Graphs. Although it is not self-similar in every case, there are many examples of such structures in it, and it follow from some monoid ( "group without inverse elements") definition by means of finite number of generators. The advantage of using it is that they have great theory of finite group presentation behind it. In fact they are even used to represent Iterated Systems which may be considered as actions of elements from such graph on some geometrical subset of a Cartesian or complex surface.

Answer 10

Try this in MATLAB for fun:

a=rand(10);a=round(.5*(a+a')); %random adjacency matrix

a2=kron(a,a); a4=kron(a2,a2); figure, imagesc(a);figure, imagesc(a2); figure, imagesc(a4);

Answer 11

Look at my Publication Semenov A.S. Fractal architectures and so on

Answer 12

In computer science, one way of providing a semantics for programs is by using infinite trees to model do-loops in finite flow-graphs. Dana Scott and Marshall Hall are the earliest I recall. Arbib and Manes later on.

A lot of knot theory can be tackled by a similar tack.

Addenda

For an introduction to asymptotic enumeration and random graphs (mentioned several times below), see:

• Edgar M. Palmer (1985), Graphical Evolution : An Introduction to the Theory of Random Graphs, John Wiley and Sons, New York, NY. http://portal.acm.org/citation.cfm?id=4050

For one of the inaugural applications of graph theory to social networks, see:

• Frank Harary, Robert Z. Norman, and Dorwin Cartwright (1965), Structural Models : An Introduction to the Theory of Directed Graphs, Wiley, New York, NY. http://www.ams.org/featurecolumn/archive/networks7.html

For applications to geography, there's this eBook:

• Arlinghaus, Sandra L.; Arlinghaus, William C.; Harary, Frank (2002), Graph Theory and Geography : An Interactive View, Wiley, New York, NY. http://deepblue.lib.umich.edu/handle/2027.42/58623

For recursive and self-similar graphs in knot theory, an ever-good springboard is:

• Louis H. Kauffman's home page : http://www.math.uic.edu/~kauffman/