Slashdot Mirror
Linked: The New Science of Networks
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.
Here is the book's official site.
This is the photos page, with photos like.. umm... this.
CS Monitor (thumbs-up)
Nature (ho-hum)
Computer User (thumbs-way-up)
One of the required classes for my Engineering degree was a course in the mathematics behind networks. It was without a doubt one of the most difficult coursework I have ever experienced. Even with all of the work we performed to create mathematical models of network nodes, etc., they were still unrealistic due to the overall complexity of "real" networks. For example, basic router queuing assumes the packets have an incoming probability Poisson distribution and outgoing has an exponential distribution. This is just an approximation used to allow us to get our arms around the problem. If you examine this model closely, you will find out that it implies that the packets that enter aren't necessarily the same size when they leave! Other issues like probabilistic routing rather than trying to model "smart" routers that adjust based on traffic patterns, etc. aren't usually modeled either.
... Wolfram's, "New Kind of Science" and Fritjof Capra's, "The Web of Life" to get a tremendous sense of convergence of many fields and principles. The incredible interconnectedness of things makes you wonder how anyone can claim to have " ... found the gene for ..." or dare to think that their actions only have local repurcussions. You listening, George?
"Consensus" in science is _always_ a political construct.
The science of networks is not so new, but it is gaining importance rapidly. I'm interested in the application of network theory to the flow of information in structured populations. Network theory would be part of this, but so would other social theories (kinship, information, psychology, etc.)
for interesting papers on networks go to:
http://www.santafe.edu
the center for the science of complexity
Logic, macros, and more
"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 =) )
"GNU's not Unix....it's Linux" / Kami "kokamomi" Petersen
"We know how people act individually, and yet we can't extrapolate the behavior of entire societies from this."
There just happens to be an entire discipline dedicated to exploring the behavior of entire societies. It's called sociology.
Within society, there's an entire sub field that's been studying social networks for years. Things like how information is spread, how people get jobs, how diseases like AIDS spread, all have been explored using social network analysis.
If you want a mathematical description of "tipping points", take a look at Mark Granovetter's work on threshold models of collective behavior. Gladwell's book is based his work (though he only references Granovetter's work on how people get jobs).
How does information spread through society?
Rumors.
Please stop drawing analogues between socioeconomical politics and physics.
Wasn't it enough that darwinism was used to promote fascism and ultraliberal capitalism and Einstein's relativity was used to promote moral relativism. All out of context, of course, but still bought by the people and - even worse - the politicians.
The owls are not what they seem
I liked Stephenson's idea of information as a virus. The "tipping point" was when the virus had reached a critical mass and became part of the basic store of information. Some info-virii, like Ford is better than Chevy doesn't infect enough people to tip society one way or the other. Other virii like the Earth revoles around the Sun, has infected basically the entire planet, and as such is passed from generation to generation.
I really don't think there isn't much complexity that can't be explained by the mere fact that we are all actually living on top of a Giant's head
"This isn't a study in computer science, its a study in human behavior"
Bose and Einstein are added to the black list of the OSS/linux zealot guild...
The author seems to make a claim, then dwell on it for entirely too long -- boring you to tears. If the book was rewritten, I imagine it'd be half as long, if not shorter. Honestly, how long does it take to explain the kevin bacon theory? He seems to think its profound that the "degrees of seperation" are getting smaller as we become more interconnected. I appreciate the effort, but it's common friggin' sense. All in all? An interesting read if all your other books are finished and theres nothing on TV. Even in that scenerio, I'd still probably end up reading (okay okay, looking at the pictures) in Wolfram's book instead ;)
I won't research for you, but if you're interested, the preprints archive at LANL has a lot of relevant theory. 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 (three-satisfiability). Brian Hayes has a very readable article about this phenomenon, with references. The authority in this field seems to be Gabriel Istrate.
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 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
BTW, what's this book about?
I don't need no instructions to know how to rock!!!!
If "Linked" sounds interesting, check out "Six Degrees; the Science of a Connected Age" by Duncan J Watts. Watts covers the nuts-&-bolts of fractal networks much better than Barabasi, plus he's a lot less conceited & a better read to boot.
S/N:R
Amazon link
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.
This is somewhat of a misleading remark. And I think this comment misses the spirit of the book and topic presented.
For instance, in the game of chess, we understand _completely_ what each piece does, but that doesn't mean we can play a perfect game, or even a good game. Although it certainly is a prerequisite in this case.
And for instance, in a branch of physics known as critical phenomena, where one tries to explain the behavior of things like water evaporating, or magnets losing magnetization, etc. You can construct extremely simple models where there's like one lower level of abstraction to know, but then you can't answer extremely simple questions about higher levels of abstraction.
Let me draw an example, that is widely known as the Ising model of magnetism in physics. We can make a very very simple model of magnetism by saying that all magnetic spins can be UP or DOWN, and the energy is 1 if an adjacent pair of magnetic spins are the same, and -1 if the spins are different. Then we put all these little spins on a lattice, and we call this collection of little spins a _magnet_. Ok, this is a very very simple model, but now we ask, does this thing behave like a magnet? A tough question in 2 and 3 dimensions! Why? It's not because of errors in our assumptions, it's basically because we have very primitive mathematical tools to tackle this type of problem. We are forced to resort to mathematical tools such as infinite transfer matrices, and jordan-wigner transformations.
Yes, in one sense, I agree with your post, that round-off errors cause chaos to occur over very long simulations or models can be inaccurate and have bad predictions. But the spirit of the book is in examining very simple models that seem to have correct predictions, but are complicated enough that we can't manipulate these models with finesse to extract additional information about the system.
- bill x .15 for good service .20 for great service
- bill x
- $.01 for crappy service
http://www.missionfaces.com/
Comment removed based on user account deletion
Calling it a "science" is sort of a misnomer. Sure there are people studying networks scientificly, but Linked is a lot of metaphors and comparisons rather than a quantitative or modelling approach. It runs in the same vein as Wolfram's ANKOS, in that they are both missing critical intermediaries needed to qualify them (to me) as a science. My studies have been in geography, which presents a whole different level of network behavior and construction. The book is good, but a little light on science.
People who think they know everything really piss off those of us that actually do.
We do? I don't think so. In order to extrapolate societal behaviour, one needs to completely subscribe to human behaviouralism. Networks of humans are less deterministic than their particles precisely because human behaviour isn't predictable. Our current error in describing human behaviour quickly compounds when describing several or many interacting humans.
Our lack of progress in sociology is a testament to our lack of understanding of the individual.
Here's a couple of examples of networks that exhibit a scale-free topology.
WikiWiki.
This shows that Wiki sites are characterized by the Pareto distribution (a.k.a. power law distribution).
RPM dependency graphs.
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. 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.
This page provides a fairly comprehensive list of further reading on the subject.
If you're interested in learning more about the large body of literature in this area, be sure to visit the INSNA web site. I think you'll find it much more informative than reading popular books on the subject.
-Carter
Most of the "tipping point" theory (which goes back at least to Erdos' 1960 random-networks paper) looks at how gradual accumulation can lead to sudden shifts in system properties. Good stuff, and relevant to situations from Darwinian evolution to traffic-jam analysis, but not really new.
However, the work of Sante Fe researcher Stuart Kaufmann (The Origins of Order, etc.) gives a whole new direction, showing how complex, interlocked systems can arise in some circumstances by winnowing a more complex chaotic system that arises naturally. It sounds circular until you look at it carefully, but Kaufmann backs up his analysis with extensive computer simulation as well as a deep analysis of genetic control processes (Kaufmann's original specialty).
These ideas can be used far beyond the biological settings for which they were first developed. Examples range from the crystallization of activity patterns in a new organization or cultural area to the process of learning itself, where the "aha" experience marks the emergence of a set of coherent concepts from the overflowing cloud of ideas that sets the stage for it.
Adding Kaufmann's ideas to your set of explanatory tools will permit you to resolve many complex-systems questions that are otherwise intractable. And computer types are particularly well-situated to understand and use his arguments.
-Carter
Many scale free distributions in user patterns have already been discovered (i.e. web pages against user visits -- a few popular sites like Amazon and Ebay, but lots of mediocre web sites like mine). You generally get a scale free distribution of transactions anytime people interact with one another in a way that they feel is advantageous (preferential). Even more interesting is when web usage becomes content becomes web usages becomes... etc. Such as Amazon's "Customers who bought this book also bought", or when Google's page rank become self reinforcing over time.
I put the 'fun' in fundamentalism