大数据、关键节点以及控制复杂网络

从Facebook信息泄露

谈如何控制复杂网络

引言：

网络科学（Network Science），顾名思义，是一门研究复杂网络性质的学问，是一个重要的新兴学术领域，它广泛地从多个学科汲取营养（例如：数学，统计物理，计算机科学，生物学，统计学，经济学），也有着广阔且强大的应用性。

大家应该听说过前一阵子Facebook被曝出的丑闻：5000万用户社交信息的泄露。而该信息的第三方使用者就是一个叫做“剑桥分析”的公司，而他们获取信息之后所做的事，便是分析各个用户的性格特点、喜好以及用户之间的关系，从而达到信息的“精确投放”。而这些信息，据报道，直接或间接地影响到了互联网用户在美国总统大选期间的投票决策。事实上，早在特朗普当选美国总统前，就有各种传言谈及俄罗斯通过干预社交媒体的内容来影响互联网用户的投票决策。那么这些公司或机构到底是如何在背后操作的？成功的关键因素有哪些？第一是大数据，正如报道中指出，他们具备着“解读用户信息”的能力；但是还有一点不可忽略，那便是对社交网络的控制能力，他们知道如何识别网络中的关键结点，以及如何控制信息在网络中的传播。

再举个正面的例子。生物体中存在着复杂的基因调控网络，通俗地讲，就是用于描述细胞内基因和基因之间对相互作用关系的网络。生物体可以通过它改变自身代谢的方式从而适应环境的变化，它更是个体发育的基础，和遗传学也有着密切的联系。这就使得它和一些疾病（尤其是遗传病）的治疗紧密挂钩。如何找到网络中的“靶点”来准确投放药物来达到理想中的治疗效果，是其中一个网络科学需要解答的问题。

本文主要涉及“复杂网络的可控性”这个话题，内容基于Albert-László Barabási组在Nature上发表过的文章 Controllability of Complex Network。文章以科普为目的，所以在完整度、严谨度上会略有欠缺，但是也会尽量做到深入浅出，能让读者有所收获。

（https://www.nature.com/articles/nature10011），以及它的补充材料，从而了解更多细节。

基本概念：

在讲述有趣的内容之前，我们需要熟悉一下基本概念。

首先是图论中的一些名词：结点（node）和边（edge），它们是组成一个图的基本单元。在应用场景中，结点往往是对被研究单元的抽象，而边则是用来刻画结点之间的联系性。例如，在Facebook的社交网络中，每个用户都是一个结点。如果两个用户之间互相是对方的好友，那么这两个代表这两个用户的结点之间便会有一条边。在这个例子中，两个用户“互为好友”，这个关系是没有方向性的，所以“无向图”已经足够了。然而在很多其他的应用中，结点间的关系是有方向的，那么我们就需要使用“有向图”了。例如，同样是社交网站，我们考虑Twitter或是Instagram，在这两个平台上，如果你想关注一个人并看到他的动态，你可以follow他。这样的关系就是单向的，图上会有一条有方向的边从代表你的结点指向代表他的结点。 一般情况下，我们允许指向自己的边存在，这样就形成了一个环，如下图所示。

想要控制复杂网络，只有结点和边的概念是不够的。为了准确说清我们到底要在网络上控制什么，我们需要在图上引入“动力系统”的概念。那么什么是“动力系统”呢？其实就是常微分方程啦，形式如下所示

这里 代表着结点的状态，状态随着时间 而变化。如果网络中有 N 个结点，那么就有 这 个状态与这 个结点相对应。代表我们对系统的控制，通过它我们可以驱动系统达到我们想要的状态，如下图绿色箭头所示。是系数矩阵，矩阵中每个元素代表着网络中某条边的权重。

这里需要指出，想要网络达到某种特定的状态，一般情况下我们并不需要对所有的结点施加控制，我们称那些接受外部输入信号的结点为驱动结点（driver node）。而我们所感兴趣的，也正是如何去识别这些驱动结点。

我们当然可以通过对所有结点施加控制，来达到控制整个网络的目的。但是在现实应用中，这样太耗费人力物力了，所以这种解决方式是不尽人意的。所以，问题的关键就转化成了如何找到最少个数的驱动结点来控制复杂网络。说到这里，我们可以很自然地想到：如果我们能在网络中找到一些有特点的“子结构”，然后这些“子结构”极其简单，以至于控制它们只需要在某个特定结点上施加单一的输入信号即可，那么我们不就可以通过寻找这样的“子结构”，来找到最简约的控制方式了吗？这样，所需要的控制结点也唾手可得。

可控性：

在经典线性控制理论中，我们有相关的结论：如果矩阵是满秩的，即，那么我们就可以通过选取特定的输入信号，来趋势网络达到想要的状态。这里，矩阵的定义如下：

这里的是我们前面提到的系数矩阵。读者不必被这个结论所困扰，如想了解些细节，可以看下这个简短的视频

（https://www.coursera.org/lecture/mobile-robot/controllability-oJVlO）。

事实上，这个对可控性的判定方式在实际应用中过于严苛了，主要体现在以下两点：

1、很多应用场景下，我们是没有办法获取系数矩阵的。这样我们就无法判定是否满秩。例如，我们无法准确量化社交网络中，用户之间的“影响”。

2、即便可以获取系数矩阵，其测量也可能是不精确的。这就使得原本可能可控的网络结构，由于测量不精确，而被判定为不可控。或者是原本不可控的网络，我们仅需对其加一些小的扰动，它就可控了。

为了消除以上问题，作者引入了一个重要的概念：结构可控性。与原有概念不同，结构可控不依赖特定的系数矩阵，是原有概念的弱化。通俗地讲，只要“大多数”的系数矩阵组合能使得满秩（也即，使得不满秩的系数矩阵组合少得可以“忽略不计”），我们就说该网络是“结构可控”的。

以下是原论文给出的四个经典例子，可以方便读者理解。

消除了对特定系数矩阵的依赖性，一个网络的可控性就完完全全地由它的结构（即：结点的连接方式）所决定了。这时，我们就可以探索上文中所提到的简单的“子结构”了！

@#$^&%!$# …*&%￥&@4%#!，经过原作者一系列乱七八糟而又不失优雅的证明，我们发现：

1、原来，使得一个网络结构无法做到结构可控的“病因”只有两条：

· 不可到达性（inaccessibility）

· 扩张（dilation）

2、只需一个控制结点的最简单的“子结构”，是一个叫做仙人掌（cactus）的东西。