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?

1736年,挪威数学家莱昂哈德.欧拉(Leonhard Euler)用一幅图终结了普鲁士(Prussia)柯尼斯堡(Königsberg)坊间的争论。Pregel河将该城市(现为俄罗斯的加里宁格勒Kaliningrad)分割为四部分,由七座桥连接着它们,一个人能否在所有桥都只走一遍的情况下一次将所有桥走完?

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.

Albert-László Barabási这位罗马尼亚出生的圣母大学(University of Notre Dame)的物理学家在过去十五年里,已经至少两次改变了他的同伴对于网络的理解。他的理论影响了工程、市场、医学和情报安全领域的重要进展。而且他的研究很快将使工程师、市场、医生和安全人员不仅理解和预测网络行为,而且可以控制它。

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.”

在一开始,如同欧拉一样,Barabási对绘制复杂的系统感兴趣。尤其是对Erdös-Rényi模型,该模型认为复杂网络是随机的,如果每个节点增长得足够大,将会和任何其他节点一样拥有相同数量的连边。1998年,Barabási 和他在圣母大学的学生寻找到一个可以研究网络理论内在规律的相当大的数据集的机会:来自圣母大学网络的32万5千个页面。当他们计算数据发现几乎所有的页面确实含有相同多的链接数。但是有少数页面不同,它们有至多1000个内部链接。与此同时,Google的PageRank算法已经利用这个性质来搜索更相关的结果,但对于网络理论学者来说,这个概念是全新的,远未足以对互联网产生影响。Barabasi后来写道“我们一眼看出了新的、不容质疑的网络秩序,它显示出了不同寻常的美妙和连通性。”

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.

根据Erdös-Rényi模型和他的发现,Barabasi绘制了另外一些巨大且复杂的系统,包括计算机芯片上的晶体管间的连接和好莱坞演员合作圈。在每个例子中,那些被他称为Hub的高度连通的节点决定了网络的特征,这是人工设计系统或类自然系统的一种既不规则又有组织性的原理。Barabasi和他的学生Réka Albert发展了ErdösRényi模型用以反映现实世界网络中的Hub的存在。自此,他为科学家们创造了一个他们之前从未想到的工具。

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.

物理学家预测例子和星球的运动已经有一个世纪了,但他们从未成功地预测人类的去留。Barabási和同在西北大学的物理学家Chaoming Song猜想如果他们可以将通话者看作粒子,那他们就有可能在任何给定的时间预测一个人的位置。他们编写了程序来绘制5万的通话者的移动行为,每个手机信号塔被看作节点。当一个用户从一个节点移动至另一个,这条路径就被记为一条连边。随后他们衍生定义了每个个体的熵,这刻画了系统的随机性和不确定性程度。通过结合移动数据和熵,Barabási 和Song发现他们能以93%的准确率在一平米的精度范围内预测人的位置。没有一个人,甚至那些经常性出行的人的预测准确率会少于80%。

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?


In 2009, when he was visiting the University of Minnesota to present his work, control was much on Barabási’s mind. Shortly before the lecture, he got into a conversation with an engineer. “After five minutes it became absolutely clear that he had no idea what I did,” Barabási says. “So I asked, ‘What do you do?’ And he said, ‘I’m a control theorist.’”

2009年,当Barabasi访问明尼苏达大学来展示他的研究,控制已经出现在他的脑海中了。在他开始讲座前很短的时间,他和一位工程师进行了一次交谈。“五分钟后我完全清楚了他不明白我在干什么。”Barabási 说,“所以我问他,你正在进行的工作是什么?”他回答说“我是一个控制学家。”

Engineers use control theory to predict how systems will respond to various inputs, which in turn helps them make robots that can catch baseballs, cars that take sharp corners with ease, and planes that don’t fall from the sky. Barabási had never heard of it, so his new friend led him to a whiteboard and drew out the basic equations. Barabási noticed how similar they were to the ones he used to map networks, and he decided to incorporate them into his own work.


Like prediction, control required evaluating an object as a system with nodes of varying importance. A car for instance: “It is made of 5,000 components,” Barabási says, “yet you as a driver have access to only three to five nodes”—the steering wheel, the gas pedal, the brake, and maybe the clutch and shifter. “With those three to five knobs, you can make this system go anywhere a car can go.” What he wanted to know was if he could look at any network, not just engineered ones, and find those control nodes. Among the thousands of proteins operating within a cell, could he find the steering wheel, the gas pedal and the brake?


Barabási asked Yang-Yu Liu, a physicist in his lab, and Jean-Jacques Slotine, a control theorist at the Massachusetts Institute of Technology, to help him locate “control nodes” within networks. Control nodes take instructions or signals from outside the network (for example, a foot on the gas pedal) and transmit them to nodes within the network (the fuel-injection system). To find them, Liu borrowed an algorithm, developed by Erdös and Rényi five decades prior, that acts as a signal moving through the network. It starts at one node and follows a random edge to another node, at which point it “erases” every other edge but the one it came in on and the one it will go out on. The algorithm runs through the entire network over and over until it finds the minimum set of starting points needed to reach every node in the system. Control these starting points, and you control the entire network

Barabási请他实验室的物理学家Yang-Yu Liu和麻省理工学院的控制学家Jean-Jacques Slotine来帮助他定位网络中的“控制节点”。控制节点从网络外发出指令或信号(比如踩在有门上的脚)然后将信号传输至网络内的节点(喷油系统)。为了研究这些节点,Liu借用了50年前Erdös和Rényi发明的算法,来表征一个信号在网络内移动。信号从一个节点开始,随机地连边至另一个节点,然后擦除其他边只留下一条链入的边和一条链出的边。这个算法在整个网络运行了一遍又一遍直到它找到一系列以最小数量的遍历整个系统节点的起始节点。控制这些节点,你就控制了整个网络。

The group tested the algorithm on 37 different networks, including a constellation of alliances within a prison population, the metabolic pathways in yeast, and several Internet communities, including Slashdot and Epinions. They found that denser, more interconnected networks tended to have fewer control nodes per capita. For instance, the brain of the highly studied worm C. elegans, a network of 297 neurons, has only 49 control nodes. The network of genes operating in a yeast cell produces 4,441 proteins, but Barabási found that he would need to control 80 percent of them, or 3,500, to control the system


This sounds like too many points to be useful, like a car with 3,500 steering wheels, but Barabási points out two things: Whereas the neuronal map of C. elegansis complete, scientists have determined only about 5 percent of the connections in the yeast cell’s gene network. The more data scientists feed into the model, the better they can map connections in the network and the fewer control nodes they might need to operate the system. “We know these maps are incomplete,” Barabási says. “But they’re getting richer every day.” He also says his theory applies to total control of a network. Scientists who want partial control—say, to elicit a particular protein expression within a cell—would need to master far fewer nodes.


As with most of Barabási’s work, it will take time to make it useful. Finding the points of control is one thing. Actually exerting influence over a given network, be it Facebook or the human immune system, is an entirely different challenge.


The first breakthroughs will most likely take place in medicine. By identifying control nodes in cell growth systems, scientists could return mature cells to their embryonic state, creating a new source of stem cells. “Some diseases are all about lack of control,” Barabási says. “If you were able to gain control over them at the cellular or neuronal level, you might be able to cure the disease.”


Control can be used for ill as well as good, of course. Marketers could learn how to better manipulate consumers, and governments could develop new techniques to cow citizens. It’s up to us, Barabási says, to define how control should be applied and how it shouldn’t be. “What we have to realize is that control is a natural progression of understanding processes,” he says. “But control is a question of will, and will can be controlled by laws. We have to come together as a society to figure out how far we can push it."

与控制可以被用于疾病一样,理所当然地,营销者可以学习如何操控消费者,政府可以发展新的技术以引导市民。“定义如何应用控制和怎样控制这取决于我们”,Barabasi说道。我们不得不意识到控制是一个理解过程的自然积累。但控制有一个意愿的问题,而意愿由法律控制。我们必须走到一起看看我们能将它推动得多远?(点击此阅读原版报道:This Man Could Rule the World)


  1. Controllability of complex networks. Nature,473,167–173. doi:10.1038/nature10011 



  1. 数字情种  索书号:K835.156.11/A124A
  2. 我的大脑敞开了天才数学家保罗·爱多士传奇(电子书)
  3. 链接网络新科学 索书号:C913/B251




Copyright © 同济大学 版权所有
上海市四平路1239号 021-65983380 同济大学 物理科学与工程学院