他能控制世界

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.

在过去的两个世纪里,科学家们在欧拉工作的基础上发展了图论——最终作为网络科学理论基础的数学科学的分支。但直到1959年,相关的理论发现才开始涌现。而且直到90年代中期科学家们才开始将该理论应用与真实的复杂问题。在那之前,大规模数据很难获,处理甚至更为困难。但当数据变得更易获取及处理器更低廉,研究者们开始将图论应用于从蛋白质相互作用到电力系统等各个领域。

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关于Hub的论文很快逐渐发展一个Hub,成为了网络科学中被广泛引用的论文之一。他将此写成一本受欢迎的书——《Linked》,并在西北大学建立起了他自己的实验室。其他研究领域的科学家们也开始利用Hub理论,肿瘤研究者利用它更好的理解一个蛋白网络如何在机体内消耗肿瘤。生物学家在Barabási的帮助下,利用该理论确定代谢网络。这项研究可以为药物开发提供一个新的视角。情报部门正利用他的研究绘制恐怖分子网络,“这是一种说法,有很多小迹象表明他们使用了它。”但将自己的观点转化为应用不会让Barabási有很久的兴趣。他是一个理论研究者,不是应用科学家,他立即将他的精力投入到描绘系统,他说,他的下一个挑战是预测网络的行为。

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.

2006年Barabási得到了预测研究的机会。一位先生打电话给他向他发出了不寻常的邀请,他说他代表欧洲移动通信集团,但始终不愿透露姓名。他抛出了一个诱人的数据宝库:超过600万用户的不具名信息。如果同意挖掘关于顾客为何更换供应商的数据信息,他也可以将这些信息用于他自己的学术研究。

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.

Barabási接受了邀请。通过研究通话每个电话号码的拨打和收费细节,他和他实验室的其他成员构造了一个算法来识别可能更换通信供应商的顾客。在发掘数据的过程中,他也发现,通过识别通话者接入的电话塔,可以使他估计通话者的物理位置。

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.

研究人员最初只是将Barabási和Song的发现和现实世界结合起来。传染病学家利用了航空旅行数据来预测城市间的疾病传播。Barabási和Song的研究可能使他们坐着独轮车跑回本垒。预测人们何时、何地、怎样出行以帮助交通工程师找到疏解堵塞的办法,发展中国家的地铁设计师有能力应对巨大的外来务工人流。2009年,Barabási和他的学生运用预测算法解释了为何手机病毒不广泛流行但一旦大量的手机使用同一操作系统就可能是一个严重的威胁。

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?

预测科学确实在走下坡路。在发表了他的研究后,Barabási收到了如潮水般的电子邮件的谴责他的观点颠覆人的信念。管理者可以用他们的算法结合通过手机收集的GPS数据以不寻常的精度来跟踪和预测居民的行动。那么如果人们可以通过预测系统的行为,他们有可能寻找到一种方法来控制它吗?

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.

工程师利用控制理论去预测对于不同的输入,系统将会作出怎样的响应。这样可以帮助他们使机器人抓住棒球,汽车轻松地拐弯,飞船避免从天空坠落。Barabási之前从未听说过这些,所以他的新朋友带着他来到一块黑板前写下了基本的公式。Barabási注意到这与他过去常绘制的网络如此相似,于是他决定将它们融合进自己的研究。

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?

如同预测一样,控制要求将对象看作是一个由不同重要程度节点组成的系统。以一辆汽车为例,“汽车由超过5000个节点组装而成”Barabási说道,“但当你作为一个司机仅有权操控其中三到五个节点。”——转动的车轮、油门、刹车、离合器和变速器。“通过这三到五个操纵杆,你可以使这个系统去任何汽车可以去的地方。”然后找出这些节点。在数以千计的操控细胞的蛋白中,能否找出转动的车轮、油门和刹车?

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

该小组在37种不同结构的网络上作了测试,包括监狱人群中的帮派、酵母中的代谢通路和很多互联网社区如Slashdot和Epinions。他们发现越紧密、越相互联系多的网络越倾向于含控制节点越少。比方说,被多次研究的线虫大脑网络有297个神经元,只有49个控制节点。酵母细胞的基因调控网络可以产生4441个蛋白,但Barabási发现他需要控制其中的80%也就是3500个才能控制系统。

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.

这听起来就像有太多有用的节点,就像一辆车有3500个滚动的轮子。但Barabási指出了两件事:无论,科学家仅便是大约5%的联系酵母细胞的基因网络。科学家将数据代入模型得越多,。“我们知道这些图是不完整的,但它们变得越来越多。”Barabási说,他的理论适用于完全的控制网络。想部分控制网络的科学家们,比方说激发一个特殊的细胞的蛋白表达,需要控制的节点要少得多。

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.

和大多数Barabasi的研究一样,这需要花费时间来使它具有实用性。寻找可以控制的节点是一个应用。实际上,对一个网络施加影响,该网络是Facebook或人类免疫系统,是完全不同的挑战。

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 

文中所述相关研究可以从Barabási主页上找到。

图书馆馆藏书籍

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

翻译:殷嘉辉,审校:魏雯婕

同济大学图书馆

2011-12-17

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