全文预警：本篇复杂指数五颗星。
“复杂网络”是个啥？
你看过琅琊榜吗？这部作品有两个特点：帅哥特别多，帅哥之间的关系特别复杂。像这样的人际关系网络就是一个简单的复杂网络。类似的，交通运输网络、电力系统网络、微博上的相互关注、Facebook上的好友关系，这些也都是典型的复杂网络。
琅琊榜中的人际关系网络。图片来源：www.anyv.net
关于复杂网络的研究兴起于20世纪末期，很快就被广泛地应用于各个领域。复杂网络既是对数据的一种表现形式，也是一种研究的手段。在研究复杂网络的系统图示里，系统的各个组成部分叫做节点；部分之间的相互关系叫做连边。研究复杂网络的重要目的是为了控制网络，趋利避害。比如，在癌症治疗的时候，我们就希望通过外界控制将某些疾病状态的细胞转换为健康状态的细胞，达到治愈的目的。
复杂网络的基本要素。供图：成慧敏 张忠元。
复杂网络如何控制？
用最小的成本控制整个网络
我们先从一个简单的例子开始。胖虎要举办生日聚会，希望来的朋友越多越好。哆啦A梦说大雄去我就去，大雄说静香去我就去。请问胖虎如何让静香、大雄、哆啦A梦3人都去参加聚会呢？
胖虎当然可以挨个搞定静香、大雄和哆啦A梦。不过，只搞定静香显然也可以达到同样的效果。因为这三个人之间存在相互联系。合理利用这种联系，就可以“牵一发以动全身”。就像一辆汽车，无论内部构造多精巧，系统多复杂，我们只需要管好方向盘和刹车等几个关键点就能达到控制的目的。
在复杂网络中也存在类似的情况。我们当然可以对网络中数量众多的节点分别进行控制。但这种控制无疑需要投入大量的时间和精力。而且，当网络增大到一定规模时，这种控制甚至根本不可行。所以，如何找到复杂网络中的“静香”，通过控制一个，或少数几个关键节点，实现对整个网络的控制，以最少的投入达到最大的效果，这是研究复杂网络想要解决的问题之一。
胖虎通过“控制”静香就可以达到邀请全部三人到生日聚会的目的。供图：成慧敏 张忠元。
那么，如何以最少的投入来控制整个复杂网络呢？这就需要解决两个问题：什么样的网络是可控的？以及，如何找到数量最少，又能控制这个网络的节点？
知己知彼，百战不殆：什么样的网络是可控的？
想要控制一个复杂网络，先得确认这个网络是否可控。什么样的网络是可控的呢？网络可控的意思就是借助外力作用（对某些节点输入控制信号），我们能够独立地控制这个网络中的每个节点。这句话包含了两个含义：
1. 我们可以控制网络中每个节点。只要网络中有一个节点不受控制，那么这个网络就没有被控制住。比如下面这幅图示的网络中，如果我们只对节点1输入控制信号，节点3就不受控制，我们也就无法控制整个网络。所以要想控制住这个网络仅仅对节点1施加外力是不够的，还需要对节点3也施加一个外力。
2. 我们可以独立地控制每个节点。看下面的示意图。在这个网络里，每当我们对节点1施加控制，节点1的变化一定会同时引起节点2和节点3的变化。假设我们的目的是想改变节点2，同时保持节点3不变的话，在这样的网络中是永远也无法实现的。总结成规律，就是，如果网络里有两个节点受到且仅受到同一个节点的控制，那么这两个节点就不是被独立地控制的。
原理介绍完了，咱们来举一个例子。请问，在下面三种网络结构中，哪个控制源能成功控制全网？
节点间带箭头的连边代表控制关系。图a红色节点“3”为不可达节点；图b红色节点“2”包含膨胀结构；图c为既不包含不可达节点也不包含膨胀节点的“仙人掌”结构。供图：成慧敏 张忠元。
答案是，C。
在网络结构（a）中，控制源控制节点1，节点1控制节点2，但是节点2无法控制节点3，节点3处于控制不可达的状态，因此信号源无法控制全网。
在网络结构（b）中，节点3和节点4同时受到节点2 的控制，无法被独立控制，因此信号源无法控制全网。
与图（b）相比，网络结构（c）中，节点4和节点5可以互相控制，套用刚才总结的规律，此时，节点3和节点4不再受到且仅受到一个节点的控制——节点4不仅受到来自节点2的控制，还受到来自节点5的控制。 因此，在（c）结构中，控制源可以通过控制节点1达到独立地控制每一个节点，也就是控制全网的目的。
擒贼先擒王：你该控制谁？
知道了什么样的网络是可控的，那么，如何才能以最高效的方式对网络进行控制呢？根据Yang-Yu Liu等人在2011年提出的“最小输入定理”，只需要三步。
最小输入定理步骤。供图：成慧敏 张忠元。
第一步：把原始网络转换成二部图。就是把网络中所有的节点排好后左右各放一列。左边这列是网络图中有箭头出发的节点，用“+”代表；右边这列是网络图中被箭头指向的节点，用“-”代表，两列节点之间是否有连边由原始网络决定，比如原始网络中存在由A出发指向B的连边，那么在二部图“+”列的A与“-”列的B之间就应该有连边。
第二步：根据二部图求最大匹配。什么是匹配呢？在连好边的二部图里，如果一条连边既没有和其他连边共用出发点，也没有和其他连边共用终点，那么这条连边所连接的两个节点就匹配了。最大匹配，就是尽可能多的让左右两列的节点都能匹配在一起。如果我们以丈夫和妻子分别代表左列和右列，一个丈夫节点连到两个妻子节点这种情况不是匹配，反过来一个妻子节点连到两个丈夫节点的情况也不是匹配。因此一夫多妻和一妻多夫都不是匹配，只有一妻一夫才算匹配。而最大匹配就是在一夫一妻的前提下最大限度地减少左右两列中单身节点的数量。
最大匹配就是在一夫一妻的前提下撮合做多对夫妻。供图：成慧敏 张忠元。
第三步：实现最大匹配后，对右列中没有匹配上的的节点输入控制信号就能控制全网。
回想一下刚才由五个节点组成的可控网络图（c），下面我们以它为原始网络为大家详细介绍最小输入定理。
首先，我们将原始网络结构（下面的图i）转换成二部图，参与到网络中的角色有节点1至节点5，我们把他们列在“＋”和“－”两列中。“＋”列表示箭头的出发节点，“－”列表示箭头的指向节点，如图（i）所示。
接下来找出该图的最大匹配，先把所有的指向关系间连线，这时“一妻多夫”的情况出现（节点2和节点5同时指向节点4），“一夫多妻”情况也出现了（节点2同时指向节点3和节点2 ）。对于该图，存在两种匹配方式：第1种有3个匹配节点（节点1-->节点2、节点2-->节点4、节点4-->节点5）；第2种有4个匹配节点（节点1-->节点2、节点2-->节点3、节点4-->节点5、节点5-->节点4）。显然，第2种匹配方式为最大匹配。
确定好最大匹配后，我们为最大匹配的连边标上红色。红色连边即为匹配连接，红色连边对应的右列中的“-”节点为匹配节点，也就是图（ii）和（iii）中的绿色节点；而右列中没有被红色连边相连的“-” 节点就是非匹配节点。匹配节点都处于“可控”的状态。我们可以通过控制左列中与红色连边相连的“+”节点来控制它们。例如节点3受到节点2的管理，节点2受到节点1的管理，而在没有控制源的情况下，节点1则处于“无人管理”的状态。所以我们（控制源）只需要对节点1这个非匹配节点输入控制信号就能实现整个网络的目的了。
最小输入定理实例展示。供图：成慧敏 张忠元。
别忙出去搞控制！
都看懂了？准备去控制复杂的客户网络和七大姑八大姨的相亲网络了？别忙，你可能盲目乐观了。咱们现在还只是找到了身边的“静香们”。如何控制她们，如何通过她们去控制整个网络，这还需要更深的学问来指导生活。“最小输入定理”虽然在理论上解决了如何以最小的成本控制整个网络的分析，但是，具体输入什么样的控制信号能使得网络达到期望状态？以及，如何将复杂网络可控性的理论应用到现实生活中？这些问题的答案仍然需要通过大量的研究工作来一一作答。这些也是研究复杂网络的科学家们在未来努力的方向。（编辑：明天 婉珺）
题图来源：http://www.cl.cam.ac.uk/research/srg/netos/CNSD09/Home.html
参考文献：
- Liu Y Y, Slotine J J, Barabási A L. Controllability of complexnetworks[J]. Nature, 2011, 473(7346): 167-173.
- Liu Y Y, Barabási A L. Control principles of complex networks[J]. arXivpreprint arXiv:1508.05384, 2015.
- RATHORE T, PRATHEEK C H S. STUDY ON CONTROLLABILITY OF COMPLEXNETWORKS[J].
- 侯绿林,老松杨, 肖延东, 等.复杂网络可控性研究现状综述[J]. 物理学报, 2015 (18): 477-487.