In 1736 the Swiss mathematician Leonhard Euler ended a debate among the citizens of Königsberg, Prussia, by drawing a graph. The Pregel River divided the city, now Kaliningrad, Russia, into four sections. Seven bridges connected them. Could a person cross all seven without walking over the same one twice?
Euler began with a map that cleared away everything—the homes and streets and coffeehouses—irrelevant to the question at hand. Then he translated that map into something even more abstract, a depiction not of a physical place but of an interconnected system. The four sections became dots, and the seven bridges became lines. By transforming Königsberg into simple nodes and edges (as mathematicians have come to call such abstractions), Euler could subject the system to mathematical analysis. In doing so, he proved that a person could not cross all seven bridges without walking over the same one twice. More important, he mapped a network for the first time.
Over the next two centuries, scientists built on Euler's work to develop graph theory, a branch of mathematics that would eventually serve as the basis for network science. But it wasn't until 1959—when the Hungarian mathematicians Paul Erdös and Alfréd Rényi proposed a means by which complex networks evolve—that a defined theory of networks began to emerge. And it was only in the mid-1990s that scientists began to apply that theory to really complex problems. Before then, large data sets were difficult to obtain and even more difficult to process. But as data became more accessible and processing power cheaper, researchers began applying graph theory to everything from protein interactions to the workings of the power grid.
Albert-László Barabási, a Romanian-born physicist at the University of Notre Dame, was one of those researchers. In the past decade and a half, he has transformed the way his colleagues understand networks at least twice. His theories have influenced important developments in engineering, marketing, medicine and spycraft. And his research may soon allow engineers, marketers, doctors and spies to not just understand and predict network behavior, but also to control it.
In the beginning, though, Barabási, like Euler, was mostly interested in mapping complex systems. He was particularly interested in the -Erdös-Rényi model, which held that complex networks were random, and if they grew large enough each node would have roughly the same number of links as any other node over time. In 1998, Barabási and his students at Notre Dame saw an opportunity to study the implications of that theory on a really big data set: 325,000 pages from Notre Dame's Web domain. When they ran the numbers, nearly all the pages did in fact have about the same number of links. But a few dozen were different. They had upward of 1,000 incoming links. At the time, Google's PageRank was already exploiting this quality to produce more-relevant search results, but to network theorists the notion was radical and had implications far beyond the Web. Barabasi later wrote that "we caught a glimpse of a new and unsuspected order within networks, one that displayed an uncommon beauty and coherence."
Faced with a contradiction between the Erdös-Rényi model and his findings, Barabási mapped several other large and complex systems, including the connections between transistors on computer chips and the collaborations between actors in Hollywood. In each case, highly linked nodes, which he called hubs, were the defining characteristic of the network, not just an anomaly but an organizing principle for engineered and natural systems alike. With his student Réka Albert, Barabási updated the ErdösRényi model to reflect the existence of hubs in real-world networks. In doing so, he created a tool for scientists to map and explore all manner of complex systems in ways they had never thought to before.
Barabási's paper on hubs quickly evolved into one itself, becoming one of most cited in the field of network science. He turned it into a popular book, Linked, and later got his own lab at Northeastern University. Scientists in other fields began to draw on hub theory. Cancer researchers used it to better understand how a network of proteins suppresses tumors in the body. Biologists, aided by Barabási, used it to determine antibiotic targets within the metabolic networks of drug-resistant bacteria; the research could provide an entirely new avenue for drug discovery. There are even signs, Barabási says, that the intelligence community is using his work to map terrorist networks. "It's a matter of wording," he says. "There are lots of little hints that they are using it."But the translation of his insights into applications did not hold Barabási's interest for long. He is a theorist, not an applied scientist. And once he had the ability to map a system, he says, his next challenge was to predict its behavior.
Barabási got his chance to work on prediction in 2006. That year, a man called him with an unusual offer. He said he represented a European mobile-phone consortium, which he insisted remain unnamed, and he possessed an intriguing trove of data: the anonymized records of more than six million subscribers. If Barabási agreed to mine the data for information about why customers switched providers, he could also use it for his own academic research.
Barabási accepted the offer. By studying patterns in call logs and the payment details attached to each number, he and the members of his lab were indeed able to construct an algorithm that identified customers who were likely to switch providers. In exploring the data, though, he also found that it identified the cellphone towers that subscribers accessed when making calls, which allowed him to gauge the physical location of callers.
Physicists have been predicting the movement of particles and planets for centuries, but they had never successfully forecast the comings and goings of people. Barabási and physicist Chaoming Song, also at Northeastern, hypothesized that if they treated those callers as particles, they could predict a person's location at any given time. They wrote software to map the movements of 50,000 callers. Each cell tower became a node. When a user traveled from one node to another, the path was marked by an edge. They then derived each individual's entropy, which measures the degree of randomness or uncertainty in system. By combining movement data with entropy figures, Barabási and Song found that they could predict a person's location, within a square mile, with up to 93 percent accuracy. No one, not even those who traveled frequently outside their usual circuit, was less than 80 percent predictable.
Researchers are only just beginning to integrate Barabási and Song's findings into real-world applications. Epidemiologists use airline travel data to predict the spread of disease from city to city. Barabási and Song's findings could allow them to home in on a single block. Predicting how, when and where people move could help traffic engineers find ways of easing congestion and urban planners design cities in the developing world capableof handling large inflows of migrant workers. In 2009, Barabási and several students used prediction algorithms to explain why mobile-phone viruses aren't prevalent now but could be a serious threat as soon as enough phones are governed by a single operating system.
Predictive science does have a downside. After publishing his work, Barabási received a flood of e-mails accusing him of opening the door to Big Brother applications. Authorities could use his algorithms paired with the GPS data collected on mobile phones to track and predict the movement of citizens with remarkable precision. And if people could predict behavior within a system, might they not also find a way to control it?
Ricardo, you must be poor.. PFHAHHAHA sucka,,,, I make 35$ an hour doing nothing at my desk..just commenting of popsci articles...
Ur pathetic for even trying...you loose like all the other third world suckaz out there
Another evil genie out of the bottle. Life is already too complicated.
Midoman sounds so cool. Wish I could make $35/hour doing a job with no impact on anything at all (well... other than the negative one he has on the popsci community), just like Midoman does.
Midoman, you should use some of that money and take some grammar lessons; It will help you a lot.
Here's a bit of humor: Erdös (pronounced roughly "Erdisch" - he of the "Erdös-Rényi" model) was himself a hub, perhaps the ultimate hub. Search for "Erdos number" to see what I mean.
@AlBme Paranoid guy is paranoid. Big surprise. The genie was always out of the bottle. Now we can describe and predict the genie's behavior.
Midorman must work for the gov. Anyone else would have canned him for unproductive time management.
So now we can map the timing and areas that creepers will blow up on Minecraft?
People always like to believe that humans are so different than a particle, but it really isn’t the case. Our perceived “higher level of complexity” is simply relative. All systems are functions of a limited set of variables, once enough of those variables are known (and one posseses enough processing power), the likelihood of interactions becomes less mysterious. There isn’t nearly as much free will as you would like to believe. 99% of it is illusion much as 99% of who you think you are is illusion as well. In fact, our entire self of self is largely illusory. Anyone who has spent a bit of time in meditation can tell you (and you can test this yourself) that when you try to find the self, beyond the perpetuity of thought, you find nothing but pure awareness. There is no separate self anywhere to be found.