從Facebook信息泄露 談複雜網路的控制

從Facebook信息泄露 談複雜網路的控制

來自專欄數據+動力系統21 人贊了文章

【主頁】：Yuying Liu (劉宇贏)

【專欄】：數據+動力系統

引言

網路科學（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 個結點，那麼就有 這 N 個狀態與這 N 個結點相對應。 代表我們對系統的控制，通過它我們可以驅動系統達到我們想要的狀態，如下圖綠色箭頭所示。 是係數矩陣，矩陣中每個元素代表著網路中某條邊的權重。

這裡需要指出，想要網路達到某種特定的狀態，一般情況下我們並不需要對所有的結點施加控制，我們稱那些接受外部輸入信號的結點為驅動結點（driver node）。而我們所感興趣的，也正是如何去識別這些驅動結點。

我們當然可以通過對所有結點施加控制，來達到控制整個網路的目的。但是在現實應用中，這樣太耗費人力物力了，所以這種解決方式是不盡人意的。所以，問題的關鍵就轉化成了如何找到最少個數的驅動結點來控制複雜網路。說到這裡，我們可以很自然地想到：如果我們能在網路中找到一些有特點的「子結構」，然後這些「子結構」極其簡單，以至於控制它們只需要在某個特定結點上施加單一的輸入信號即可，那麼我們不就可以通過尋找這樣的「子結構」，來找到最簡約的控制方式了嗎？這樣，所需要的控制結點也唾手可得。

可控性

在經典線性控制理論中，我們有相關的結論：如果矩陣 是滿秩的，即 ，那麼我們就可以通過選取特定的輸入信號 ，來驅使網路達到想要的狀態 。這裡，矩陣的定義如下：

這裡的 是我們前面提到的係數矩陣。讀者不必被這個結論所困擾，如想了解些細節，可以看下這個簡短的視頻（https://www.coursera.org/lecture/mobile-robot/controllability-oJVlO）。

事實上，這個對可控性的判定方式在實際應用中過於嚴苛了，主要體現在以下兩點：

1. 很多應用場景下，我們是沒有辦法獲取係數矩陣 的。這樣我們就無法判定 是否滿秩。例如，我們無法準確量化社交網路中，用戶之間的「影響」。
2. 即便可以獲取係數矩陣，其測量也可能是不精確的。這就使得原本可能可控的網路結構，由於測量不精確，而被判定為不可控。或者是原本不可控的網路，我們僅需對其加一些小的擾動，它就可控了。

為了消除以上問題，作者引入了一個重要的概念：結構可控性。與原有概念不同，結構可控不依賴特定的係數矩陣 ，是原有概念的弱化。通俗地講，只要「大多數」的係數矩陣組合能使得 滿秩（也即，使得 不滿秩的係數矩陣組合少得可以「忽略不計」），我們就說該網路是「結構可控」的。

以下是原論文給出的四個經典例子，可以方便讀者理解。a和c是可控的（所以也是結構可控的），因為無論係數矩陣如何取值，都不會影響 滿秩（這裡我們假設邊的權重均為非零）。b既不是可控的，也不是結構可控的，因為矩陣 的第三列為零，不可能滿秩。d在很多情形下是不可控的（當滿足條件 時），但是它一定是結構可控的，因為滿足 的係數矩陣組合僅僅是一個「零測集」。

消除了對特定係數矩陣的依賴性，一個網路的可控性就完完全全地由它的結構（即：結點的連接方式）所決定了。這時，我們就可以探索上文中所提到的簡單的「子結構」了！

@#$^&%!$# …*&%￥&@4%#!，經過原作者一系列亂七八糟而又不失優雅的證明，我們發現：

1. 原來，使得一個網路結構無法做到結構可控的「病因」只有兩條：

• 不可到達性（inaccessibility）
• 擴張（dilation）

1. 只需一個控制結點的最簡單的「子結構」，是一個叫做仙人掌（cactus）的東西。

現在解釋一下以上都是些什麼鬼。為了方便理解，我們同樣用圖來說明（這樣當然會犧牲一些嚴謹性，但是「打通直覺」是足夠了；anyway，還是建議有興趣的讀者閱讀原文）。

圖 a 說明了不可到達性：通俗地講，如果網路中有某個結點，沒有任何的邊指向它，那麼我們就說這個點是「不可到達的」（例如這裡的）。既然這個結點不可到達，那麼就不可能有任何的信息流向它，那麼我們又怎麼可能通過控制網路中其中一個結點來影響到它呢！所以自然就無法「結構可控」了！是不是很簡單？

圖 b 說明了什麼是擴張：簡單地說，如果有一些結點（比如說一個結點：第二張圖中的），它們「向外」指向了更多的結點（這裡對應和，已用紅色標出），那麼我們就說網路里存在著「擴張」。「擴張」的存在直接導致了「自由度」的增大，這就好像一個部門的經理管理著很多的部員，為完成一些工作，經理給不同部員分配不同的任務，但是他不會控制部員如何具體地實施開展自己的任務，每個部員有自己發揮的空間。所以，擴張的存在會使得整體結構不可控。

圖 c 是一棵仙人掌。它有自己的「根（root）」，「莖（stem）」和「芽（bud）」。原文證明了，通過單一輸入信號，我們可以控制這樣的結構，所以，該結構中也並不存在「不可到達的結點」和「擴張」。同時，這也是最簡單的「子結構」，任何其他更複雜的結構是無法通過單一輸入信號控制的。該結構的構建細節請參照原文。

如何找到關鍵結點？

從上文中可知，想要知道最少需要多少個驅動結點從而控制整個網路，只要去記數這個網路中有幾棵仙人掌就好了！是不是有點似曾相識，像小時候玩過的遊戲？那麼我們又如何找到這些關鍵的驅動結點呢？

同樣從上文中可知，最簡單的「子結構」中沒有不可到達的結點，也沒有擴張，這樣極其特殊的性質為我們尋找「最少驅動結點」（即「最少輸入」）提供了便利：我們可以考慮其對偶問題：尋找「最大匹配」。（註：為什麼它們被稱作對偶問題呢？通俗地說，就是因為它們是等價的，且解決了其中一個也就解決了另一個！）

那麼什麼是「匹配（matching）」呢？其實很簡單，「匹配」就是指一堆邊（edge）所組成的集合，只不過這個集合中的邊並不「分享」相同的起始結點或是終止結點。例如，集合中有一條邊從2號結點指向5號結點，還有一條邊從4號結點指向5號結點，這是不行的，因為它倆「分享」了終止結點（5號結點）。在這個邊的集合中，所有的邊都有自己的終止結點，我們稱這些終止結點為「被匹配上的結點」；相反，如果有一個結點，沒有任何一條這個集合中的邊指向它，我們稱這個結點「沒有被匹配上」。

知道了匹配的概念之後，我們還需要知道「最大匹配（maximum matching）」。其實也很簡單：如果你找到了一個匹配（也即，一個滿足上述條件的邊的集合），使得有N個結點被匹配上了，並且再也沒有其他人可以找到別的匹配，使得被匹配上的結點數量多於N, 那麼你找到的匹配就是「最大匹配」。請注意：最大匹配可以不唯一，且匹配的N個結點可以不同。如果網路中的所有結點全部被匹配上了，那麼恭喜你，你找到了「完全匹配（perfect matching）」！以下圖 a 紅色標註的邊就是一個「最大匹配」的例子，但是它並不是「完全匹配」，右側圖 b 只是有向圖的另一種表達形式。

有趣的是，原文證明了：如果你找到了最大匹配（也就是說，你知道了哪些結點會被匹配上），那些沒有被匹配上的結點，就構成了我們要找的「最少的驅動結點」集合。其實如果你仔細體會上一個小節的分析，這樣的結果並不應該讓你驚訝：通俗地講，被匹配上的結點可以被它的上一層的結點控制住，而沒有被匹配上的，則需要外界其他的輸入來控制。如果我們找到的最大匹配剛好是完美匹配，那麼，我們就可以通過網路中任何單個結點來控制整個網路了！是不是很神奇？自行腦補：如果我們的交友方式滿足一定的「模式」，那麼某些人只需要通過在社交網站上影響非常少數的人，來控制整個網路了！是不是又很可怕？

---- 別擔心！這個模型是非常理想化的，社交網路本身要比這個複雜很多倍。但是，這樣的問題確實是潛在的。

最後，還需要補充最關鍵的一環，但也是最trivial的一環：有一個叫做「Hopcropt-Karp Algorithm」的演算法，是可以用來尋找最大匹配的，這裡就不深入探討了，有興趣的讀者可以參照維基百科。

一些有趣的結論

基於結構可控性的概念以及上述理論基礎，並且我們把所需要的驅動結點的個數作為評判一個網路「可控程度」的標準，那麼就會有很多有趣的結論：

1. 根據下圖標示出的不同網路上的數據指標（驅動結點佔總結點的百分比），生物網路一般是很難控制的，但是很多社交網路是比較好控制的（也即，可以通過控制少數人來影響整個系統）。
2. 複雜的網路的可控性和結點的入度（in degree）和出度（out degree）的分布息息相關；但是，和我們直覺相反的是，所選取的驅動結點往往不是樞紐節點（hub），即入度出度最大的結點。在社交網路的例子上，這就等價於說，如果想要控制社交網路，選取的用戶不一定是最具有影響力的用戶。

結語

以上內容僅僅是原文的第一部分，事實上，第二部分也同樣精彩。它主要講述了如何用分析（而非計算）的方法去估計一些具有特殊性質的網路的可控程度，例如：無尺度網路（scale-free network）。但是，由於它涉及到了一些深刻的統計物理知識，這裡就不贅述了。最後，希望本文可以引起讀者對網路科學的興趣，並有所收穫！

推薦閱讀：