Looking for the Next Big Thing

Author: Dale Keiger


In 1998, a young physicist of remarkable energy and promise named Albert-László Barabási brought together his research group at Notre Dame. They had been working on problems of materials science, studying granular media like sand, and the ultra-tiny semiconductors known as quantum dots. They were already producing significant papers, so one can imagine their surprise when Barabási told them he intended to abandon materials science for a field that existed mostly in his imagination: network science.

Barabási had been at Notre Dame for only three years. He did not yet have tenure. But his curiosity and personality were leading him away from the safe course. About four years before, he had tried to work on networks and been rejected. Still, that’s what he wanted to explore. So he gave his team the news. One chose to complete his doctorate and leave. The others made the leap of faith with Barabási, and now that leap has brought forth a new scientific paradigm that is changing one field after another.

The networks studied by network science abound. Climb onto a commercial airliner, open the in-flight magazine to the route map in the back, and you will find a route map, a map of a network: flights (links) connecting airports (nodes) and routing through major airports in such places as Atlanta and Dallas-Fort Worth (hubs). The electrical power grid is a network, as is the national highway system. The World Wide Web is a network of information. We each are part of a social network, linked to relatives, spouses, friends and acquaintances. The metabolism of cells in the human body is a network of molecules linked by chemical reactions.

The formal study of networks has forerunners as far back as the 18th century. As a genuine scientific discipline it is only about 10 years old, and the founders of its contemporary theory and practice number at most three or four. Barabási, now the Emil T. Hofman professor of physics and director of the Center for Complex Network Research, is one of them, and its most-cited author. As Walt Whitman said of himself, Barabási contains multitudes. He has the energy and discipline of an athlete, a scientist’s methodical approach to managing time and effort, the ambition and self-confidence of an entrepreneur, a physicist’s brashness about crossing disciplinary lines, and an artist’s stubborn independence regarding his work habits and his determination to follow his inspiration.

That networks turn up everywhere is not their principal attraction for scientists. What has grabbed the attention of physicists, sociologists, economists, computer scientists, biologists, physicians and defense experts is how many of them, mysteriously, share the same fundamental architecture that Barabási discovered about eight years ago. The World Wide Web, cellular metabolism, Hollywood actors connected through appearances in films—all share the same topology, with similar mathematical characteristics. Why? Barabási thinks he knows.

Last December, taped to the door of his faculty office were two things. One was a joke, a doctored picture of the Energizer Bunny with Barabási’s face superimposed. (A third-year doctoral student at the center, Cesar Hidalgo, says, “He doesn’t drink coffee, but he acts like he does.”) The other was a cartoon. A dog sits high in a tree, gazing down at an earth-bound cat. The dog says, “Sheer will, I tell you—sheer will.”

A day in the life

Monday through Friday, Barabási adheres to a strict routine designed to minimize distractions and keep his work moving forward. He wakes up at around 7 a.m. and opens the laptop computer that his wife, a schoolteacher named Janet Kelley, has left beside him on the bed. He refuses to come to the physics department’s offices for any reason before afternoon, so he has missed a few faculty meetings, which does not seem to bother him. He spends the morning thinking, reading, making notes and writing papers for science journals. At noon, he eats lunch in one of the University cafeterias and reads journal articles, mostly from Science and Nature. From 2 to 6 p.m., when he is not teaching, he works in the center’s offices in Nieuwland Science Hall, mostly meeting with members of his research group.

He has weekend routines, too. Every Saturday he walks to South Bend’s Farmer’s Market and has lunch at its café, where the waitresses know to bring him a Diet Coke with a side plate of lemon wedges. Every Sunday, he and Janet dine at Fiddler’s Hearth, an Irish pub in town.

Barabási was born in 1967 to ethnic Hungarian parents in the Transylvania region of Romania. His father, László, was a museum director; his mother, Katalin Keresztes, taught literature and became a director of children’s theater. The young Albert-László aspired to be a sculptor. At the museums his father supervised, he studied drawing and sculpting. When he gained admission to an elite high school that specialized in science and mathematics, he encountered physics. Soon he excelled at it, winning a local physics Olympiad. He recalls, “At the end of the 10th grade, physics was going so well. Art was not going so well.” He began poring over biographies of physicists, and by the end of the 11th grade, he knew what he wanted to do with his life.

As an undergraduate at the University of Bucharest, he began research on chaos theory and published three papers, unusual for someone yet to earn his first degree. But life was becoming difficult in Romania. The totalitarian government of Nicholas Ceausescu distrusted the country’s ethnic Hungarian minority and ordered the destruction of rural villages so as to consolidate the Hungarian population in cities. As a museum director, his father would decide which Hungarian churches and other cultural buildings in his county had to be preserved. The government did not want that decision in the hands of a Hungarian, so it fired him. The only work open to him after that was in the municipal bus system. When his situation attracted too much attention inside and outside Romania, the authorities ordered him out of the country, in 1989. He refused to go without his son, so Albert-László left with him.

Says Barabási, “We were given two passports with the understanding: Don’t come back.” His mother, by this time divorced from his father, stayed behind with his sister, Livia. The fall of the Communist government in 1989 freed Barabasi to return to Transylvania each year to visit his mother. He sees his sister whenever he travels to Budapest, where she now lives.

Father and son went to Hungary in 1989, and László earned a master’s in physics at Eotvos Lorand University. His advisor there recommended him to H. Eugene Stanley, a physicist at Boston University. When Stanley came to Budapest for a conference in 1990, he met Barabási and was impressed by his ambition. “Science is not a leisurely affair,” says Stanley. “It’s a competitive sport.” He invited Barabási to apply to Boston University’s doctoral physics program. Barabási’s English wasn’t so hot—he actually failed the TOEFL English proficiency exam—but in only three years he earned his doctorate at Boston U. and in his new language wrote his first book, Fractal Concepts in Surface Growth.

As a newly minted Ph.D. in 1994, Barabási became a research physicist at an IBM research center in New York. After four months, he had become curious about what all the computer scientists around him pondered. So over the Christmas break he took home from the company library a book whose exact title eludes his memory, something like Fifty Problems in Computer Science. One problem caught his attention: If you are presented with a grid, what is the most economical way to find a linking tree that extends a link to every node? It was a problem in networks.

In his 2002 book Linked: How Everything Is Connected to Everything Else and What It Means, Barabási wrote, “As I immersed myself in algorithms, graphs and Boolean logic, I started to sense how little was known about networks in general. All my readings told me that the millions of electric, telephone and Internet cables cramped under the pavement in Manhattan formed a fundamentally random network. The more I thought about it, the more I was convinced that there must be some organizing principles governing the complex webs around us.”

A new science was about to be born.

Network theory

One can arbitrarily designate the first act of network science as taking place in Saint Petersburg, Russia, in 1736. The great mathematician Leonhard Euler, perhaps merely for amusement, wrote a paper about seven bridges in the nearby Prussian town of Königsberg. The paper answered a puzzle: Could one devise a path so as to cross all seven bridges without crossing any one bridge more than once? Euler wrote a proof that provided the answer, which was no. One step of his process was to draw a graph of the bridge system, with nodes for plots of land and links for bridges. His drawing marked the birth of graph theory. It was also perhaps the earliest example in mathematics of what Barabási made his specialty. Links connecting nodes—Euler had sketched a network.

The next seminal moment in network theory occurred more than 200 years later. In 1959, the Hungarian mathematician Paul Erdös, who once called mathematicians “machines for turning coffee into theorems,” collaborated with Alfred Rényi, a fellow Hungarian, on a paper that proposed a random model of networks. Every node in their model had an equal chance of linking to another node, and the formation of links was a random process. The Erdös-Rényi model remained the paradigm for mathematical thinking about networks for 40 years.

Barabási’s little computer problem, from the book he’d checked out of the IBM library, resulted in his first network science paper, which he submitted to four journals, including Science and Nature. All four rejected it. He remembers, “Nobody said it was wrong. But somehow the tone I got from the referee reports was, ‘Who cares?’” Barabási decided networks would not be a fruitful line of professional inquiry and put them aside.

He wanted to land in an academic setting but assumed any good faculty position would require four to six years of work as a post-doctoral fellow. Gene Stanley encouraged him to apply for faculty jobs anyway. One night Barabási came home to his apartment in the Bronx and found a reply from a school in Indiana. “I had never heard about this place. I went to IBM and asked my colleagues, ‘Have you ever heard about the University of Notre Dame?’"

They had. He traveled to South Bend for an interview and impressed Jerry Jones, who was then chairman of the physics department. Jones, now a professor emeritus, says, “He was the only applicant we had ever seen who had written a major book before he had graduated with his Ph.D.” Notre Dame hired him. He was only 26 and looked so young he preferred to deal with administrators by telephone, because when they encountered him in person they thought he was a student. He began his initial work in materials science, and the group he assembled produced good papers straight off. One of his doctoral students, Réka Albert, co-authored a paper titled “What Keeps Sandcastles Standing?” that made the cover of Nature.

But Barabási’s mind kept coming back to networks. “It was not hard to see that networks were everywhere,” he says, “and there had been zero research done on them. Absolutely nothing. I don’t find much satisfaction in taking a problem lots of people have been working on and doing it better. I do find satisfaction in working on a problem nobody considers a problem yet.” Associate professor Boldizsár Jankó, who has known him for 17 years and joined him at Notre Dame in 2000, says, “He has this unique talent for finding a niche, explaining to the rest of us that this is important, then creating a field. He finds gems and picks them up and polishes them, and then shows them to the rest of us dummies.”

Mapping the links

A physicist’s fundamental approach to understanding the world is to quantify it, then extract theories from the data. In 1998, as Barabási’s curiosity returned to networks, he realized he had an opportunity Erdös and Rényi had not had when they were developing their network model: the Internet, a massive network that might be measured and mapped. In his research group was a post-doc, Hawoong Jeong, who had a formidable knowledge of computers. At Barabási’s request, Jeong wrote a piece of software that would act as a robot and map the World Wide Web by electronically crawling from link to link. (Search engines such as Google use similar robots to catalog Web pages.) The Web was already huge, so the scientists sent Jeong’s crawler out to find only those pages that were part of Notre Dame’s Internet domain. The robot followed every link to every page in nd.edu, and compiled data on the scope and interconnectedness of what it found.

Barabási expected to find what had been predicted by the 1959 Erdös-Rényi model. Most pages would have the same number of links, formed at random (that is, in no fashion that an observer could predict) in what’s known as a Poisson distribution, which closely resembles the familiar bell curve. Then Jeong, who was analyzing the data, came to Barabási with something odd. The links in nd.edu appeared to be distributed in a much different pattern—a power law. A graph of a power law resembles a hockey stick, with a single steep curve sweeping downward into a long, long tail. There’s nothing bell curvish about it.

A power law is a pattern of distribution in which large is rare and small is common. It’s useful as a way of describing, for example, how wealth is distributed in a society (large wealth rare, small wealth common) or how books sell (bestsellers rare, poor sellers common). When you hear “20 percent of people hold 80 percent of wealth,” that describes a power law. The minority holding the most wealth will be at the top of the curve, and the long tail will be all the rest of the population who have a few bucks stashed in the mattress.

The power-law distribution meant that some nodes in the Notre Dame network had a great many links, others had widely varying numbers. Barabási didn’t know what to make of this, except for understanding that, chaotic as it might look, the World Wide Web apparently had some sort of deep order. He and his team wrote a quick paper for Nature summarizing their findings, and he flew off to a conference in Portugal.

Before he left, he asked Réka Albert to look at a few more networks while he was gone. So she examined data on how transistors in a computer chip were connected, and also the Internet Movie Database, a massive record of thousands of actors linked to each other by roles in the same films. (It’s the basis of the game “Six Degrees of Kevin Bacon.”) She later sent an email that Barabási read while he was in Portugal. “She said she had measured what I had asked her to, and the distribution [in both networks] was a power law.” That is, the physical network of transistors in a chip and the professional network of actors in Hollywood shared the same fundamental structure as did the World Wide Web.

“That was the defining moment,” Barabási says. Power laws, he says, “always emerge when there’s a transition from disorder to order. There had to be some explanation. I remember sitting in the lectures in Portugal and not paying attention at all.” He quickly scribbled a new theoretical model and faxed it to Albert. Soon he had her reply: “It works.”

Now Barabási knew he was on to something. Finding power laws in networks made them essential to understanding complex systems in general. What’s more, the presence of power-law distributions in networks required hubs with a disproportionate abundance of links that could not have formed randomly. That blew up the Erdös-Rényi model that had reigned for 40 years. Barabási called this new type of network “scale free,” because there was no typical number of links and thus no scale. He sensed he was looking at a new paradigm, and he had to write a paper fast. He was about to spend a month traveling in Romania, and he could not wait that long to compose an article, in case somebody else was trying to make sense of similar findings. Two Cornell researchers, Duncan Watts and Steve Strogatz, had just published in Nature a landmark paper on social networks, and Barabási didn’t know what else they might be up to.

Janet Kelley, at the time Barabási’s girlfriend, reminded him that he had promised not to work while they lingered in Portugal for a short vacation. “But this is so exciting!” Barabási recalls saying. “I’ve got to do that! I’ve got to do that! I have to get this out! Probably somebody else is already thinking about it.” They compromised. He could write a paper, but he had to wait until they were on the flight home. After a stewardess spilled a soft drink on his computer, he composed the paper in his head and drafted it by hand on paper provided by the guilty flight attendant. Science published the piece in October 1999. The appearance of Barabási and Albert’s work and the Watts-Strogatz paper marked the emergence of the new science of complex networks. This was when Barabási told his research group he was abandoning materials science for network science.

At first their new work attracted little attention and no funding. Then a trio of brothers, Michalis, Petros and Christos Faloutsos, did a study of the physical infrastructure of the Internet, the cables and routers and nodes, and found the same scale-free network architecture. Next, Barabási teamed up with a Hungarian friend at Northwestern University, the biologist Zoltán Oltvai, to examine metabolic networks—genes linked by chemical reactions—in 43 different living organisms. In every case they found the same power-law distribution of nodes and links. The Internet, actors in Hollywood, the proteins that regulate cellular metabolism, all could be studied as networks with a common structure and common mathematical laws. Physicists, biologists, sociologists, economists and other -ists began to realize they had a new and powerful way to look at how the world is put together. They started reading Barabási’s papers.

Social networks

In the last few years, Barabási and others have steadily added to the knowledge of scale-free networks. He has demonstrated how they grow from their first few nodes and why, as they grow, they develop hubs. (Older nodes, and nodes that begin to get some extra links for various reasons, soon attract more and more links in a rich-get-richer fashion. Barabási calls this “preferential attachment,” and it is a key component of his network theory.) He has shown how those hubs constitute the Achilles’ heel of systems such as the Internet: Attack the hubs and you can bring down the network. This is bad news for the Internet but good news if you’re a researcher looking to disrupt a genetic network that’s causing cancer.

Lately, Barabási has tried to better understand how social networks function by studying the behavior of individual nodes. When he analyzed how people used electronic mail, he found that most of them generate email in short bursts of activity at various points in the day. Graph the distribution of email activity over time, and you find it’s a power law. Is this a property created by the Internet, or is all personal communication like this? To figure that out, he studied the voluminous and meticulously catalogued correspondence of Darwin, noting how long it took him to respond to letters. He found that most responses were quick but some took a long time, and the distribution of responses? Another power law. When he studied Einstein’s correspondence, he found the same thing. Power laws do not underlie every network; the national electrical grid, for example, has neither a power-law distribution nor hubs. But scale-free networks show up so often it’s almost spooky.

Barabási believes the most interesting work in networks over the next few years will be in biology. With the confidence typical of physicists—sociologist Duncan Watts, who can lay claim to being another of network science’s founders, has called them “almost perfectly suited to invading other people’s disciplines”—he has spent more than a year studying diseases, and has co-authored a forthcoming paper that might be the next big thing in network science, not to mention medicine. The paper is under review by Science and thus embargoed, but Barabási can talk about it in general terms. It concerns what the authors are calling the Human Disease Network, and he says, “At the end of the day, the reason you have a disease is because something in your cells breaks down. Typically we think in terms of a gene or molecule breaking down. But it’s often not a single gene or molecule, but part of a network malfunctioning. To fix the problem, you need a blueprint of how the system works. You have to understand the network of disease, how a defect here has a consequence over there.”

Scientific interest in network theory has grown exponentially. Barabási’s doctoral advisor at Boston University, Gene Stanley, says of his former protégé, “He’s made more of an impact than any living scientist that I know of in the last five years.” Like any good physicist, Stanley has data: “One way to quantify [Barabási’s influence] is to look at how many citations he gets each year for his key papers: roughly 500, and that’s per year. My best papers get between 50 and 100 per year.” And Stanley is one of the most cited physicists in the world.

Barabási has done all of this before turning 40 years old. One of his collaborators in studying the human disease network has been Marc Vidal, a geneticist at the Dana Farber Cancer Institute and Harvard Medical School. In 2005, Barabási spent a sabbatical year working with Vidal at Dana Farber, learning all he could about diseases and protein networks, so Vidal got a good look at him. Asked to describe how Barabási’s mind works, Vidal just laughs, then utters a succinct description: “Fast.”

Dale Keiger is a senior writer at Johns Hopkins Magazine in Baltimore.

Photo of Albert-László Barabási by Matt Cashore.