Linked: The New Science of Networks 160
| Linked: The New Science of Networks | |
| author | Albert-László Barabási |
| pages | 229 |
| publisher | Perseus Publishing |
| rating | 10 |
| reviewer | kurtkilgor |
| ISBN | 0738206679 |
| summary | An introduction to scale-free networks and their broad applications |
It turns out that in the past few years, a decent amount of progress has been made on this front, largely thanks to the Internet. The Internet allows scientists to exchange information and speed up research, but more pertinently it is a test subject for these kinds of large-scale interaction problems. Linked: The New Science of Networks presents both the story of how the science has developed, and what it means. Unlike much popular scientific literature, the author himself is an active participant in the field.
The biggest surprise and most important lesson of the book is that the Internet, cellular biology, society, matter, and an incredible array of other seemingly unrelated things all form a particular type of structure called a scale-free network. These types of networks have only been described in detail recently, and their study promises to be as fundamental and rewarding as, for instance, waves or diffusion. The presence of the same structure in many unrelated situations suggests that there is a deep physical or mathematical principle which governs them.
The discovery of this principle is the subject of the first half of the book, which is a sort of detective story that leads from the most primitive concepts of graphs, as pioneered by Euler, to the state of the art. It is very interesting in itself to see how inconsistencies in mathematical models have led people to develop more and more accurate ideas of how such networks function. There is a tiny amount of math in the footnotes available for those who want it, but generally no prior knowledge is required. The author writes with plenty of anecdotes, especially in the beginning starting out with such introductions as this one of Paul Erdos:
"One afternoon in late 1920s Budapest, a seventeen-year-old youth cantered with a weird gait through the streets and stopped in front of an elegant shoe shop that sold custom-made shoes ... After knocking on the store's door-an act that would have seemed just as odd back then as today-he entered, ignoring the saleswoman at the counter, and went up to a fourteen-year-old boy in the back of the shop.'Give me a four digit number,' he said.
'2,532,' came the wide-eyed boy's reply . . .
'The square of it is 6,441,024,' he continued. 'Sorry, I am getting old and I cannot tell you the cube.'"
For another example of both the writing style and the unusual content, the author humorously describes the discovery of a similarity between Bose-Einstein condensation and economic monopoly:
"Essentially Microsoft takes it all. As a node, it is not just slightly bigger than its next competitor. In the number of its consumers it simply cannot be compared. We all behave like extremely social Bose particles, convenience condensing us into a faceless mass of Windows users. As we purchase new computers and install Windows, we carefully feed and maintain the condensate developed around Microsoft. The operation systems market carries the basic signatures of a network that has undergone Bose-Einstein condensation, displaying clear winner-takes-all behavior."
The rest of the book devotes a chapter to a particular example of a network: epidemics, the Internet, economics, etc. One thing is abundantly clear: the more we know about how these things work, the better we'll be able to curb DDOS attacks, stop disease, and control economic failures. An unlikely example of a scale-free network is the cell. It turns out that the interactions among a cell's proteins can be modeled this way, and if we could only understand it, we would be able to come up with treatments analytically, instead of by trial and error as it is done now.
It seems to me that with a greater understanding of networks, we will be able to finally advance in many fields in which progress is currently stalled. From firefly research to AIDS treatment, this is the Next Big Thing.
You can purchase Linked from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
More complex than you think. (Score:5, Interesting)
In the Foundation series... (Score:5, Interesting)
"societies", and you don't even have to know how the individuals act individually.
I agree with him, we knew how the solarsystem (society)worked long before we knew how atoms (individuals) worked.
You cannot use the knowledge of individuals to analyze society, just as you cannot use the knowledge of society to analyze individuals.
If you want to know how society works, study society, not individuals.
These are just my opinions though.
(Don't call me redundant if somebody else wrote something similar while I wrote this =) )
Related topics (Score:4, Interesting)
I won't research for you, but if you're interested, the preprints archive at LANL [lanl.gov] has a lot of relevant theory [lanl.gov]. Basically, the current research is trying to come with a unified framework for so-called "phase transitions" in stochastic discrete processes. One of the most studied problems is the transition between "easy" and "hard" problems in 3-SAT [wikipedia.org] (three-satisfiability). Brian Hayes has a very readable article [sigmaxi.org] about this phenomenon, with references. The authority in this field seems to be Gabriel Istrate [lanl.gov].
The emergence of the giant component in random networks is a mature field of research, of course pioneered by Erdös, and with players of the likes of Don Knuth [stanford.edu] and Doron Zeilberger.
From a mathematical standpoint, Graph Theory per se is not really complicated, what actually is is the asymptotic analysis of stochastic processes.
HTH,
Matas
Re:In the Foundation series... (Score:3, Interesting)
With all due respect to Asimov (who I don't think believed it himself), the theory is a load of crap and really is just fantasy. History proves over and over that single individuals can make a world-changing difference. Would the mongols have taken over asia with Gengis Kahn? Doubtful. Would Europe have been carved up the way it was without Hitler? Again, doubtful.
And hell, what if Lincoln had not been elected President? We might have TWO "United States of Americas" occupying our current continent. I can't even imagine what the world would be like with a divided US. And how long would it have taken to free the slaves in the Southern US?
I mean, you can go on and on. What if Lee Harvey Oswald had missed? What if what's-his-name didn't get assassinated, causing WW/I? What if Ghandi hadn't been born?
Small Worlds by Duncan Watts (Score:2, Interesting)
Amazon link [amazon.com]
From the Amazon reviews:
Duncan Watts uses this intriguing phenomenon--colloquially called "six degrees of separation"--as a prelude to a more general exploration: under what conditions can a small world arise in any kind of network?
The networks of this story are everywhere: the brain is a network of neurons; organisations are people networks; the global economy is a network of national economies, which are networks of markets, which are in turn networks of interacting producers and consumers.
Food webs, ecosystems, and the Internet can all be represented as networks, as can strategies for solving a problem, topics in a conversation, and even words in a language. Many of these networks, the author claims, will turn out to be small worlds.
Re:In the Foundation series... (Score:3, Interesting)
Great Analogy (Score:1, Interesting)
Re:In the Foundation series... (Score:2, Interesting)
> And hell, what if Lincoln had not been elected President?
> What if Ghandi hadn't been born?
The truth is, no one knows. Just as psychohistory was largely statistical, human societies are non-linear. Individual humans ("heroes") do come in, do act as inflection points -- but it is not as if other inflection points could not have existed.
Lincoln's opponent could have risen to the occasion as well. Many historians argue that India would have become free, Gandhi or not, because Britain was much too weak after WWII to deal with the "restive natives" (not all Indians were non-violent, a good many that were sentenced were called "seditionists" then, and almost certainly would be called freedom-fighters^W terrorists today).
Social behavior in the 1900s middle-east was pretty predictable: who in the middle of it would have predicted Kemal Atatürk? Yet, the really interesting thing is, given the almost-repeating patterns common to non-linear systems, how what will Turkey evolve into a hundred years from now? (e.g. Now a pro-Islamic party has been voted in there. Is this a major inflection or something that'll be damped out in no time? again, no one knows...)
> With all due respect to Asimov (who I don't think believed it himself
You are right, Asimov used it simply as one of the building blocks of a good yarn. Like the 3 laws of robotics. (In fact, in Forward the Foundation, written in the late 80s (or early 90s?), contains references to 'achaotic equations' he had to dream up because he could bear not acknowledging the growing body of evidence that the future is essentially non-linear).
Comment removed (Score:3, Interesting)
new "science" of networks (Score:3, Interesting)
Slashdot as a scale-free network (Score:3, Interesting)
Here's a couple of examples of networks that exhibit a scale-free topology.
WikiWiki.
This [reseaucitoyen.be] shows that Wiki sites are characterized by the Pareto distribution (a.k.a. power law distribution).
RPM dependency graphs [slashdot.org].
Out of curiousity, I wrote a quick script to compute the distribution of the number of links in the RPM dependency graph. It does seem to follow the Pareto distribution.
Slashdot
Although I have no easy way of verifying this, my gut feeling is that the network of Slashdot users is also scale-free, if we define the notion of a link between two users as follows. User bobdc is linked to user bugbear, if bobdc has replied to any of bugbear's post (or submissions) at least once.
This definition allows us to introduce the notion of a CmdrTaco number, similar to the Kevin Bacon number [virginia.edu]. Specifically, user Joe Schmoe has the CmdrTaco number of 1, if CmdrTaco has replied to any of Joe's comments. If Joe responded to wuliao's post, then wuliao has the CmdrTaco number of no greater than 2, and so on.
Pareto distributions are pretty common. For example, the number of downloads on SourceForge follows the Pareto distribution [cam.ac.uk].
This page [innovationwatch.com] provides a fairly comprehensive list of further reading on the subject.
Re:The New Science (Score:3, Interesting)
It seems to me that most of the dynamics and mechanics of multi-agent networking behaviour are closely related to the structure they are confined to - and by structure I mean the physical implementation constraints of the working model - more so than what it is the agents themselves do, associated with a certain probability density function.
I've done some research in Neural Networks and I was amazed by the importance of the dimensionality of the network. There is a subfield in NN's that tries to generate appropriate networks for appropriate computing tasks. Still the difference between real neurons and neural networks, is that the first one has an analog clock, while the second one has at least a discretized clock per node, if not per layer or for the whole cell. Also the importance of having a feedback or recurency can make all the difference in the right / wrong places.
I have the feeling - but could not proove this yet - that a dynamic combination of local optima searches and global optima searching leads to self-modifications to the structure in which the agents live, in such a way that the structure suits the needs of the original fitness function, which desribes the problem that we are trying to solve. Since the fitness function itself is a variant in time in most problems, it is logical to assume that the networks are never in a static state, so global optima searching will modify the network constantly, while local optima searching will try to exploit network capabilities best.
Seems like interesting material, I'll have to check out this book!