most recent 30 from http://mathoverflow.net 2013-05-20T20:44:54Z http://mathoverflow.net/feeds/question/45586 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45586/the-diameter-of-the-erdos-component-of-the-collaboration-graph Mark Sapir 2010-11-10T18:50:53Z 2011-05-21T19:02:41Z

<p><a href="http://www.oakland.edu/enp/trivia/" rel="nofollow">This </a> site claims that the diameter of the Erdös component of the collaboration graph in 2004 was 23. What is it now? Is it increasing or decreasing with time? Recall that the vertices of the collaboration graph are mathematicians and two vertices are connected if the mathematicians co-author a paper. MathSci allows one to find the collaborative distance between any two mathematicians. So in principle one can find the diameter just by using MathSci. In general (and more seriously) is there a mathematical theory which describes the growth of "real life" networks like the collaborative graph? </p> <p><b> Update 1</b> A process that I had in mind is something like this. At every step one of the following things can happen.</p> <ol> <li><p>A new vertex $a$ is born with some probability $p$. Usually that vertex is a "student" of some other vertex $x$. We can connect $a$ and $x$ by an edge.</p></li> <li><p>A randomly chosen vertex $y$ gets connected with a randomly chosen vertex $z$. But the probability for choosing $z$ is not uniform. Those vertices that are closer to $y$ have more chances getting connected to $y$. </p></li> <li><p>A randomly chosen vertex "dies" (with some probability $q$) meaning it does not participate in new edges any longer. </p></li> </ol> <p><b> Update 2. </b> Many thanks to Balazs and Joseph for their answers. But the first question still remains: what is the diameter of the Erdös component now? </p>

http://mathoverflow.net/questions/45586/the-diameter-of-the-erdos-component-of-the-collaboration-graph/45597#45597 Joseph O'Rourke 2010-11-10T20:28:37Z 2010-11-10T20:28:37Z

<p>The paper "Some analyses of Erdös collaboration graph" by Vladimir Batagelj and Andrej Mrvar (<a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6VD1-40B84V7-5&amp;_user=825413&amp;_coverDate=05%252F31%252F2000&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1535877740&amp;_rerunOrigin=google&amp;_acct=C000044660&amp;_version=1&amp;_urlVersion=0&amp;_userid=825413&amp;md5=726818dbcd30e0e11e5f6540d2e86bff&amp;searchtype=a" rel="nofollow"><em>Social Networks</em> Volume 22, Issue 2, May 2000, Pages 173-186</a>) is filled with fascinating data and analysis as of 2000. (Because this is a decade old, it does not answer your question.) Here is their figure of "cliques of the main core," with many recognizable names (if you can read them at this resolution!). <br /> <img src="http://cs.smith.edu/~orourke/MathOverflow/ErdosCliques.jpg" alt="alt text"> <br /> I see many (63) later papers that cite this one, but none that directly update it for this specific Erdös graph.</p>

http://mathoverflow.net/questions/45586/the-diameter-of-the-erdos-component-of-the-collaboration-graph/45619#45619 Balazs 2010-11-10T23:15:27Z 2010-11-10T23:33:12Z

<p>There is a very large literature on this, written by people doing "network science". One of the names you might want to look up is that of Mark Newman, see for example his papers <a href="http://xxx.lanl.gov/abs/cond-mat/0007214" rel="nofollow">The structure of scientific collaboration networks</a> or <a href="http://xxx.lanl.gov/abs/cond-mat/0011144" rel="nofollow">Who is the best connected scientist? A study of scientific coauthorship networks</a> as well as <a href="http://arxiv.org/abs/cond-mat/0104209" rel="nofollow">Clustering and preferential attachment in growing networks</a>. Another important player in this field is Albert-Laszlo Barabasi, whose group had a model (for the web graph) which is somewhat similar to what you suggest, <a href="http://xxx.lanl.gov/abs/cond-mat/9910332" rel="nofollow">Emergence of scaling in random networks</a>. Some of this work is reviewed nicely in <a href="http://xxx.lanl.gov/abs/cond-mat/0106096" rel="nofollow">Statistical Mechanics of Complex Networks</a>. The model by Barabasi et al is studied in mathematical terms by Bollobas-Riordan-Spencer-Tusnady's <a href="http://onlinelibrary.wiley.com/doi/10.1002/rsa.1009/abstract" rel="nofollow">The degree sequence of a scale-free random graph process</a>.</p> <p>To answer your specific question on the diameter, I would expect it to be quite small ("six degress of separation"); whether it decreases in time must depend on the relative rate of birth of new vertices versus new edges (collaborations). If you take a finite graph and add completely random links, then already a few links lead to a diameter which is logarithmic in the size of the network. I think this remains the case also if you weigh your edge creation mechanism by the distance of the vertices; I once played with a model where the only new edges were created between 2-step neighbours, which still lead to small diameter.</p>

http://mathoverflow.net/questions/45586/the-diameter-of-the-erdos-component-of-the-collaboration-graph/65668#65668 Goldstern 2011-05-21T19:02:41Z 2011-05-21T19:02:41Z

<p>In the long run, the diameter will grow. Let k be an upper bound to the number of years between a mathematician's first and last publication. Then nk years after Erdos' last publication, all new nodes in the Erdos component will have Erdos number at least n, so the diameter will be at least n. </p> <p>(I am assuming here that there <em>will</em> be new nodes, which is not true for very large values of n. Also, I am assuming that k is constant, but only to keep the estimate "nk" simple.) </p>