大数据、关键结点以及控制复杂网络（二）

从Facebook信息泄露谈

如何控制复杂网络

上期回顾：网络科学理论 | 大数据、关键节点以及控制复杂网络（一）

如何找到关键结点？

从上文中可知，想要知道最少需要多少个驱动结点从而控制整个网络，只要去记数这个网络中有几棵仙人掌就好了！是不是有点似曾相识，像小时候玩过的游戏？那么我们又如何找到这些关键的驱动结点呢？

同样从上文中可知，最简单的“子结构”中没有不可到达的结点，也没有扩张，这样极其特殊的性质为我们寻找“最少驱动结点”（即“最少输入”）提供了便利：我们可以考虑其对偶问题：寻找“最大匹配”。（注：为什么它们被称作对偶问题呢？通俗地说，就是因为它们是等价的，且解决了其中一个也就解决了另一个！）

那么什么是“匹配（matching）”呢？其实很简单，“匹配”就是指一堆边（edge）所组成的集合，只不过这个集合中的边并不“分享”相同的起始结点或是终止结点。

例如，集合中有一条边从2号结点指向5号结点，还有一条边从4号结点指向5号结点，这是不行的，因为它俩“分享”了终止结点（5号结点）。在这个边的集合中，所有的边都有自己的终止结点，我们称这些终止结点为“被匹配上的结点”；相反，如果有一个结点，没有任何一条这个集合中的边指向它，我们称这个结点“没有被匹配上”。知道了匹配的概念之后，我们还需要知道“最大匹配（maximum matching）”。其实也很简单：如果你找到了一个匹配（也即，一个满足上述条件的边的集合），使得有个结点被匹配上了，并且再也没有其他人可以找到别的匹配，使得被匹配上的结点数量多于，那么你找到的匹配就是“最大匹配”。请注意：最大匹配可以不唯一，且匹配的 个结点可以不同。如果网络中的所有结点全部被匹配上了，那么恭喜你，你找到了“完全匹配（perfect matching）”！以下a图红色标注的边就是一个“最大匹配”的例子，但是它并不是“完全匹配”，右侧b图只是有向图的另一种表达形式。

有趣的是，原文证明了：如果你找到了最大匹配（也就是说，你知道了哪些结点会被匹配上），那些没有被匹配上的结点，就构成了我们要找的“最少的驱动结点”集合。

其实如果你仔细体会上一个小节的分析，这样的结果并不应该让你惊讶：通俗地讲，被匹配上的结点可以被它的上一层的结点控制住，而没有被匹配上的，则需要外界其他的输入来控制。如果我们找到的最大匹配刚好是完美匹配，那么，我们就可以通过网络中任何单个结点来控制整个网络了！是不是很神奇？自行脑补：如果我们的交友方式满足一定的“模式”，那么某些人只需要通过在社交网站上影响非常少数的人，来控制整个网络了！是不是又很可怕？

---- 别担心！这个模型是非常理想化的，社交网络本身要比这个复杂很多倍。但是，这样的问题确实是潜在的。

最后，还需要补充最关键的一环，但也是最trivial的一环：一个叫做“Hopcropt-Karp Algorithm”的算法，是可以用来寻找最大匹配的，这里就不深入探讨了，有兴趣的读者可以参照维基百科。

一些有趣的结论

基于结构可控性的概念以及上述理论基础，并且我们把所需要的驱动结点的个数作为评判一个网络“可控程度”的标准，那么就会有很多有趣的结论：

1. 根据下图标示出的不同网络上的数据指标（驱动结点占总结点的百分比），生物网络一般是很难控制的，但是很多社交网络是比较好控制的（也即，可以通过控制少数人来影响整个系统）。

2. 复杂的网络的可控性和结点的入度（in degree）和出度（out degree）的分布息息相关；但是，和我们直觉相反的是，所选取的驱动结点往往不是枢纽节点（hub），即入度出度最大的结点。在社交网络的例子上，这就等价于说，如果想要控制社交网络，选取的用户不一定是最具有影响力的用户。

结语

以上内容仅仅是原文的第一部分，事实上，第二部分也同样精彩。它主要讲述了如何用分析（而非计算）的方法去估计一些具有特殊性质的网络的可控程度，例如：无尺度网络（scale-free network）。但是，由于它涉及到了一些深刻的统计物理知识，这里就不赘述了。最后，希望本文可以引起读者对网络科学的兴趣，并有所收获！

作者简介

Luckstarufo，南开大学数学学院本科，佐治亚理工学院计算机科学与工程硕士，华盛顿大学应用数学在读博士生，波音奖学金获得者。

主要研究方向为数据驱动下的动力系统发现和网络上的动力系统理解，曾在Amazon担任机器学习研究员，现师从华盛顿大学应用数学系、物理系、电子电气工程系教授NathanJ. Kutz以及应用数学系教授、Facebook研究员EliShlizerman攻读该领域。

领域前瞻

动力系统是应用数学领域的其中一个主流方向，它可以描述一个复杂系统如何随时间变化，所以此类模型被广泛应用于各个学科。在自然科学领域，它被用于描述星系演化、流体运动、物种数量变化等等；在社会科学领域，它对研究经济学现象、社交网络等也有着深远的指导意义。

而数据科学，是一门讲述如何从数据中提取有价值的信息的学问。随着科技的发展，人类社会拥有的数据规模增长的很快，再加上计算机的计算能力也有了大幅的提升，这就使得人们可以很方便地使用数据来辅助自己发现、建立模型。我在phd期间将主要研究如何将两者更好地结合，从而推动这一场智能革命。

作者：Luckstarufo

编辑：蜜汁酱、ECHO