# Graphs with fractal properties?

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.

-
Expander graphs are in fact not very related to selfsimilar graphs. They are some kind of graph skeletons which has property that they expand in good way the whole graph of a given family of graphs. The meaning of term expand here is that from every vertex of expander graph of some graph family there is near to other vertexes of this graphs, so You may search though family graph by picking vertexes from expander and then random picking paths through family graph. As expander is smaller than family graph, it usually gives You simpler and computational efficient algorithm of searching etc –  kakaz Feb 11 '10 at 20:31

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".

-

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

-
The Rado graph is self-similar in a very precise way, as well, which you didn't mention. Furthermore it's the only (non-trivial) countable example of such a self-similar graph. –  Harrison Brown Nov 17 '09 at 22:31

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.

-

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

-

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

-

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.

-

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.)

-
Well, the idea behind the project is that I can find enough data about social networks to develop a way to do it much more efficiently. Also, I'd be willing to tolerate a pretty large amount of error - it just needs to look generically right. For instance, if I could figure out the general traits of social networks of a dense urban, then I could generate a big city just by some set of rules and a few data points about it. This is actually more like procedural generation than regular compression. However, the task it quite daunting, both from the data-collection and computing standpoints. –  DoubleJay Nov 18 '09 at 0:50
Ahh. Well, certainly there are "random graph models" that are known to have more social-network-like properties than the Erdos-Reyni model, which I think are generically pretty good - the degree sequence is a power-law distribution, the diameter is small, etc. Here's a construction which might work fairly well: Assign to each vertex a "sociableness" which is distributed by a power law. Now draw a graph at random, such that v_i and v_j are adjacent with probability proportional to the product of their sociableness. This should be scale-free, and otherwise nice. –  Harrison Brown Nov 18 '09 at 3:05

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.)

-

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.

-

Try this in MATLAB for fun:

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

-

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.