Graphs with fractal properties? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T22:53:40Z http://mathoverflow.net/feeds/question/5781 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5781/graphs-with-fractal-properties Graphs with fractal properties? DoubleJay 2009-11-17T05:22:42Z 2013-02-06T08:19:19Z <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/5782#5782 Answer by Jon Awbrey for Graphs with fractal properties? Jon Awbrey 2009-11-17T05:34:30Z 2009-11-18T13:22:03Z <p>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.</p> <p>A lot of knot theory can be tackled by a similar tack.</p> <p><strong>Addenda</strong></p> <p>For an introduction to asymptotic enumeration and random graphs (mentioned several times below), see:</p> <ul> <li>Edgar M. Palmer (1985), <i>Graphical Evolution : An Introduction to the Theory of Random Graphs</i>, John Wiley and Sons, New York, NY. <a href="http://portal.acm.org/citation.cfm?id=4050" rel="nofollow">http://portal.acm.org/citation.cfm?id=4050</a></li> </ul> <p>For one of the inaugural applications of graph theory to social networks, see:</p> <ul> <li>Frank Harary, Robert Z. Norman, and Dorwin Cartwright (1965), <i>Structural Models : An Introduction to the Theory of Directed Graphs</i>, Wiley, New York, NY. <a href="http://www.ams.org/featurecolumn/archive/networks7.html" rel="nofollow">http://www.ams.org/featurecolumn/archive/networks7.html</a></li> </ul> <p>For applications to geography, there's this eBook:</p> <ul> <li>Arlinghaus, Sandra L.; Arlinghaus, William C.; Harary, Frank (2002), <i>Graph Theory and Geography : An Interactive View</i>, Wiley, New York, NY. <a href="http://deepblue.lib.umich.edu/handle/2027.42/58623" rel="nofollow">http://deepblue.lib.umich.edu/handle/2027.42/58623</a></li> </ul> <p>For recursive and self-similar graphs in knot theory, an ever-good springboard is:</p> <ul> <li>Louis H. Kauffman's home page : <a href="http://www.math.uic.edu/~kauffman/" rel="nofollow">http://www.math.uic.edu/~kauffman/</a></li> </ul> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/5810#5810 Answer by Boris Bukh for Graphs with fractal properties? Boris Bukh 2009-11-17T11:34:39Z 2009-11-17T11:34:39Z <p>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 <a href="http://www.math.ucla.edu/~bsudakov/pseudo-random-survey.pdf" rel="nofollow">survey by Sudakov and Krivelevich</a>. In a way of motivation, it will also be useful to get acquainted with the <a href="http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma" rel="nofollow">Szemerédi regularity lemma</a>, as it morally says that every graph can be decomposed in a few pseudorandom graphs.</p> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/5830#5830 Answer by Jason Dyer for Graphs with fractal properties? Jason Dyer 2009-11-17T15:51:46Z 2009-11-17T15:51:46Z <p>You could start with graphs directly based on fractals, like the <a href="http://mathworld.wolfram.com/SierpinskiGraph.html" rel="nofollow">Sierpinksi Graph</a> or the Koch Graph.</p> <p>For future searching, these are called "self-similar graphs".</p> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/5848#5848 Answer by Steven Gubkin for Graphs with fractal properties? Steven Gubkin 2009-11-17T18:16:39Z 2009-11-17T18:16:39Z <p>You might be interested in an object called the Random Graph <a href="http://en.wikipedia.org/wiki/Rado_graph" rel="nofollow">http://en.wikipedia.org/wiki/Rado_graph</a>, 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."</p> <p>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): <a href="http://golem.ph.utexas.edu/category/2009/11/fraisse_limits.html#more" rel="nofollow">http://golem.ph.utexas.edu/category/2009/11/fraisse_limits.html#more</a> </p> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/5880#5880 Answer by David Eppstein for Graphs with fractal properties? David Eppstein 2009-11-17T22:28:24Z 2009-11-17T22:28:24Z <p>Your idea of transforming nodes into sets of nodes sounds a lot like graph grammars — see e.g. <a href="http://en.wikipedia.org/wiki/Graph_rewriting" rel="nofollow">this Wikipedia article</a>.</p> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/5881#5881 Answer by Harrison Brown for Graphs with fractal properties? Harrison Brown 2009-11-17T22:29:47Z 2009-11-17T22:29:47Z <p>Okay, so Steven's right -- there is a (countably infinite) graph which is <em>totally</em> 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.</p> <p>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.)</p> <p>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 <a href="http://en.wikipedia.org/wiki/Lexicographical%5Fproduct%5Fof%5Fgraphs" rel="nofollow">notion</a> 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...)</p> <p>If you want "looks the same to certain graph invariants," then expander graphs are well worth looking at.</p> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/5884#5884 Answer by Harrison Brown for Graphs with fractal properties? Harrison Brown 2009-11-17T23:34:06Z 2009-11-17T23:34:06Z <p>So social networks in particular have some rather different properties than generic graphs. In particular they tend to be <a href="http://en.wikipedia.org/wiki/Scale-free%5Fnetwork" rel="nofollow">scale-free</a>, which a random graph (in the usual model) probably is not.</p> <p>Scale-free graphs <em>do</em> 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.)</p> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/10690#10690 Answer by Swapnil Bhatia for Graphs with fractal properties? Swapnil Bhatia 2010-01-04T10:35:50Z 2010-01-04T10:35:50Z <p>Fractal properties'' is not too precise a question.</p> <p>Nonetheless, here's one idea:</p> <p>Let A be the adjacency matrix of an undirected graph. </p> <p>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.)</p> <p>Interpret the resulting matrix as the adjacency matrix of a graph. </p> <p>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.)</p> <p>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.)</p> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/15027#15027 Answer by kakaz for Graphs with fractal properties? kakaz 2010-02-11T20:25:45Z 2010-02-11T20:25:45Z <p>You may consider <a href="http://en.wikipedia.org/wiki/Cayley%5Fgraph" rel="nofollow">Cayley Graphs</a>. 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.</p> http://mathoverflow.net/questions/5781/graphs-with-fractal-properties/15067#15067 Answer by Ben Golub for Graphs with fractal properties? Ben Golub 2010-02-12T03:50:55Z 2010-02-12T03:50:55Z <p>Related to Swapnil's point, Kronecker graphs have been used to model real large networks: see <a href="http://arxiv.org/PS_cache/arxiv/pdf/0812/0812.4905v2.pdf" rel="nofollow">Kronecker graphs: An Approach to Modeling Networks</a>.</p>