Skip to main content
added 633 characters in body
Source Link
Balazs
  • 3.2k
  • 26
  • 30

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 The structure of scientific collaboration networks or Who is the best connected scientist? A study of scientific coauthorship networks as well as Clustering and preferential attachment in growing networks. 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, Emergence of scaling in random networks. Some of this work is reviewed nicely in Statistical Mechanics of Complex Networks. The model by Barabasi et al is studied in mathematical terms by Bollobas-Riordan-Spencer-Tusnady's The degree sequence of a scale-free random graph process.

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.

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 The structure of scientific collaboration networks or Who is the best connected scientist? A study of scientific coauthorship networks as well as Clustering and preferential attachment in growing networks. 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, Emergence of scaling in random networks. Some of this work is reviewed nicely in Statistical Mechanics of Complex Networks. The model by Barabasi et al is studied in mathematical terms by Bollobas-Riordan-Spencer-Tusnady's The degree sequence of a scale-free random graph process.

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 The structure of scientific collaboration networks or Who is the best connected scientist? A study of scientific coauthorship networks as well as Clustering and preferential attachment in growing networks. 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, Emergence of scaling in random networks. Some of this work is reviewed nicely in Statistical Mechanics of Complex Networks. The model by Barabasi et al is studied in mathematical terms by Bollobas-Riordan-Spencer-Tusnady's The degree sequence of a scale-free random graph process.

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.

Source Link
Balazs
  • 3.2k
  • 26
  • 30

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 The structure of scientific collaboration networks or Who is the best connected scientist? A study of scientific coauthorship networks as well as Clustering and preferential attachment in growing networks. 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, Emergence of scaling in random networks. Some of this work is reviewed nicely in Statistical Mechanics of Complex Networks. The model by Barabasi et al is studied in mathematical terms by Bollobas-Riordan-Spencer-Tusnady's The degree sequence of a scale-free random graph process.