To insert individual citation into a bibliography in a word-processor,
select your preferred citation style below and drag-and-drop it into the document.
Phys Rev E Stat Nonlin Soft Matter Phys, Vol. 64, No. 2 Pt 2. (August 2001) Key: citeulike:48
Formatted Citation
Show HTML
Likes
(beta)
This copy of the article hasn't been liked by anyone yet.
Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
Newmann Strogatz & Watts produce some unsurprising, but rigorous, results using nothing cleverer than probability generating functions. Expected number of neighbours, second neighbours, and degrees of vertices discovered by picking an edge at random and then seeing what you get at the ends are all quantities which can be expressed nicely in terms of the degree distribution's generating function. As, surprisingly, is cluster size. You can come up with some nice results about when the phase transition to give you the giant component happens... and they turn out to be nicely intuitive too (you'll see a giant component when the expected number of second neighbours is more than the expected number of nieghbours). The authors produce some novel asymptotic results about cluster size distribution too.
Having bashed out the theory, they perform a cursory check with some simulations and then go on to perform a very nice analysis on just how much you can discover about a network just from knowing its degree distribution. They take a dataset of Fortune 1000 directorships and try to deduce what clustering coefficients one would expect to see in the set from plugging the observed degree distribution into their results from the first part. It turns out to fit rather well.
There are some things which don't work so well, such as interlocks between board members. Hollywood collaborations too exhibit some other social factor which the model doesn't capture.
As an aside, this is the first paper I've seen which proposes modelling Barabási degree distributions as a power law with an exponential cutoff. They reckon the power law fit is a bit rough around the edges, and cite [http://www.pnas.org/cgi/content/full/97/21/11149 Classes of small-world networks] by Amaral, Barthélémydagger, and Stanley along with [http://www.pnas.org/cgi/content/full/98/2/404 The structure of scientific collaboration networks] by Newman.
CiteULike organises scholarly (or academic) papers or literature and provides bibliographic
(which means it makes bibliographies) for universities and higher education establishments.
It helps undergraduates and postgraduates. People studying for PhDs or in postdoctoral (postdoc) positions.
The service is similar in scope to EndNote or RefWorks or any other reference manager
like BibTeX, but it is a social bookmarking service for scientists and humanities researchers.
Notes for this article
There are no reviews yet
