0x00 背景
復(fù)雜網(wǎng)絡(luò)一直是個(gè)很有意思的領(lǐng)域球恤，雖然它現(xiàn)在沒有深度學(xué)習(xí)那么火爆蛹疯，但這么多年來一直在穩(wěn)步的發(fā)展，更是與人們生活的方方面面都息息相關(guān)，計(jì)算機(jī)科學(xué)自然不用多說喂走，物理化學(xué)殃饿、生物醫(yī)藥甚至傳播學(xué)都有復(fù)雜網(wǎng)絡(luò)的應(yīng)用場景。而且芋肠，復(fù)雜網(wǎng)絡(luò)的論文大多都發(fā)表在物理相關(guān)的期刊上乎芳，這也側(cè)面說明了復(fù)雜網(wǎng)絡(luò)和物理學(xué)的緊密聯(lián)系。
回到正題帖池，此次復(fù)雜網(wǎng)絡(luò)大師賽是由數(shù)據(jù)城堡舉辦奈惑，主題是尋找復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，并按照節(jié)點(diǎn)重要性程度從高到低排序碘裕，給出一個(gè)節(jié)點(diǎn)重要性序列携取。比賽鏈接在此，提供了8個(gè)規(guī)模不一的復(fù)雜網(wǎng)絡(luò)帮孔，下載鏈接點(diǎn)這里雷滋。
0x01 一般思路
尋找復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)是一個(gè)由來以久的問題，前人做過的研究多如牛毛文兢。想快速了解的話可以看看呂琳嬡老師和她學(xué)生的綜述文章晤斩，非常全面的從各個(gè)方面闡述了重要節(jié)點(diǎn)排序的各類方法。
在我的理解中姆坚，對(duì)節(jié)點(diǎn)重要性進(jìn)行排序本質(zhì)上是一個(gè)最優(yōu)化的問題：只要給定了評(píng)價(jià)指標(biāo)澳泵，我們窮舉出所有可能的序列，依次進(jìn)行評(píng)估就能夠找到最優(yōu)解兼呵。當(dāng)然這種方法也只是理論上可行兔辅，即使網(wǎng)絡(luò)中只有100個(gè)節(jié)點(diǎn)，窮舉的空間也是爆炸的击喂，更不用說本次比賽提供的復(fù)雜網(wǎng)絡(luò)维苔，規(guī)模最小的也有40萬個(gè)節(jié)點(diǎn)。
在剛才提到的綜述文章中懂昂，介紹了許多比較常見的算法介时，有基于度的，基于k-shell分解的凌彬，基于介數(shù)的沸柔，還有大名鼎鼎的PageRank算法。這些方法雖然在真實(shí)場景中各有各的局限性铲敛，但其算法思想是非常簡潔非常美的褐澎，無論大家是否有志于做復(fù)雜網(wǎng)絡(luò)領(lǐng)域的研究，我覺得都有必要好好了解一下原探。
除了綜述文章中的提到的方法乱凿，我也找了很多近幾年的論文顽素，看了不少老外做的研究咽弦。但是經(jīng)過實(shí)驗(yàn)驗(yàn)證徒蟆，除了PageRank算法和LeaderRank算法(呂琳嬡老師提出的PageRank算法的改進(jìn))，其他方法都是槽點(diǎn)滿滿。最為普遍的一個(gè)問題就是效率問題，很多人折騰出一個(gè)看起來很高大上淘太，碾壓別人結(jié)果的算法埠忘，結(jié)果一看實(shí)驗(yàn)部分，所測試的網(wǎng)絡(luò)規(guī)模都是幾百到幾千個(gè)結(jié)點(diǎn)左右的……那基本上不用多說了括蝠，幾十萬節(jié)點(diǎn)的網(wǎng)絡(luò)肯定沒法跑。
除此之外，我們還需要重點(diǎn)關(guān)注一下節(jié)點(diǎn)重要性排序的評(píng)價(jià)指標(biāo)姥闪，這部分在剛才提到的綜述文章中也有涉及，一般來說有兩種評(píng)價(jià)方法：第一種是用網(wǎng)絡(luò)魯棒性和脆弱性評(píng)價(jià)排序算法砌烁，第二種是用傳播動(dòng)力學(xué)評(píng)價(jià)排序算法筐喳。第一種方法的思路比較直接，如果一個(gè)節(jié)點(diǎn)越重要函喉，那么移除它以后對(duì)網(wǎng)絡(luò)的破壞性就越大避归，那么我們通過不斷移除節(jié)點(diǎn)，觀察網(wǎng)絡(luò)中最大連通集團(tuán)規(guī)模的變化情況管呵，就可以“客觀”的評(píng)價(jià)出某個(gè)節(jié)點(diǎn)的重要性程度梳毙。本次大師賽采用的就是這種評(píng)價(jià)指標(biāo)，后面我們會(huì)詳細(xì)講講該算法的實(shí)現(xiàn)捐下。那么第二種評(píng)價(jià)指標(biāo)主要是在研究傳染病模型账锹、社交網(wǎng)絡(luò)中的信息傳播過程中使用較多，包括SIS模型和SIR模型坷襟，這里就不繼續(xù)深入了奸柬。
0x02 PageRank算法+貪心策略
上一小節(jié)說到，除了PageRank算法和LeaderRank算法啤握，其他算法都很難在評(píng)價(jià)指標(biāo)和時(shí)間效率上實(shí)現(xiàn)雙贏鸟缕。但是事實(shí)證明，在此次比賽的評(píng)價(jià)指標(biāo)下排抬，直接使用PageRank算法的效果并不好懂从。為什么呢？我們來看如下情形：
[圖片上傳失敗...(image-6f70aa-1514533576212)]
在上圖中蹲蒲，毫無疑問PageRank值最高的兩個(gè)節(jié)點(diǎn)為A和B番甩，但是如果我們按照評(píng)價(jià)指標(biāo)逐個(gè)刪除時(shí)就會(huì)發(fā)現(xiàn)，當(dāng)刪除掉第一個(gè)節(jié)點(diǎn)A之后届搁，第二個(gè)節(jié)點(diǎn)B的重要性似乎并沒有那么高了缘薛。反而是刪掉節(jié)點(diǎn)C或D能夠使復(fù)雜網(wǎng)絡(luò)的最大連通子圖規(guī)模下降的更快窍育。這僅僅是簡單的示例，在真實(shí)網(wǎng)絡(luò)中必然也存在類似情況：即刪除某個(gè)節(jié)點(diǎn)后宴胧，導(dǎo)致整個(gè)網(wǎng)絡(luò)中大量節(jié)點(diǎn)的PageRank值發(fā)生劇烈變化漱抓，使得原節(jié)點(diǎn)重要性序列不再可靠。
那么怎么辦恕齐？可以采用貪心策略乞娄，最暴力的做法是每刪除一個(gè)節(jié)點(diǎn)，重新計(jì)算一次PageRank值显歧。但是很遺憾仪或，雖然PageRank算法的效率非常高，但是重復(fù)計(jì)算幾十萬到幾百萬次也不是我普通PC能夠承受的士骤。因此范删，我們把刪除的節(jié)點(diǎn)數(shù)放寬到500，即每刪除500個(gè)節(jié)點(diǎn)拷肌，重新計(jì)算一下剩余網(wǎng)絡(luò)中節(jié)點(diǎn)的PageRank值到旦，然后再重復(fù)這個(gè)過程即可。
對(duì)于普通玩家來說廓块，能夠做到這一步厢绝，結(jié)果已經(jīng)很不錯(cuò)了，大概能排到30名左右带猴。但是如果要繼續(xù)向前推進(jìn)昔汉，那還需要從其他角度去思考問題。
0x03 從評(píng)價(jià)算法的實(shí)現(xiàn)談起
本次比賽提供了評(píng)價(jià)算法的思路和源碼是一個(gè)非常重要的hint拴清，如果沒有認(rèn)真看將是一個(gè)非常大的損失靶病，大賽評(píng)價(jià)算法的頁面點(diǎn)這里。
簡單概述一下算法的基本思想口予，本次比賽將網(wǎng)絡(luò)的魯棒性(Robustness)作為評(píng)價(jià)指標(biāo)娄周，給定的一個(gè)節(jié)點(diǎn)重要性序列(重要性從高到低排列)，逐個(gè)從中刪除節(jié)點(diǎn)沪停，每刪除一個(gè)節(jié)點(diǎn)煤辨，計(jì)算當(dāng)前網(wǎng)絡(luò)最大連通集團(tuán)規(guī)模。
如果按照字面上的理解木张，直接去實(shí)現(xiàn)這樣的一個(gè)算法當(dāng)然是可以的众辨，求最大連通分量大多使用深度優(yōu)先搜索算法，雖然時(shí)間復(fù)雜度不算高(一般為$O(N+M)$舷礼，其中$N$為節(jié)點(diǎn)數(shù)量鹃彻，$M$為邊數(shù)量)，但是在百萬級(jí)別的網(wǎng)絡(luò)規(guī)模下妻献，仍然是一筆不小的時(shí)間開銷蛛株，何況每刪除一個(gè)節(jié)點(diǎn)就需要計(jì)算一次团赁。因此，這里采用了一種“逆向思維”的方式：不從已有網(wǎng)絡(luò)中“刪節(jié)點(diǎn)”谨履，而是從零開始構(gòu)建一個(gè)網(wǎng)絡(luò)欢摄，每一步變?yōu)椤疤砉?jié)點(diǎn)”。這兩種方式是完全等價(jià)的屉符，最后算出來的結(jié)果也是一致的剧浸。
我根據(jù)官方的代碼和描述锹引，寫了一個(gè)不那么規(guī)范的偽代碼(重在領(lǐng)會(huì)思想)矗钟，如下所示：
[圖片上傳失敗...(image-9440d6-1514533576212)]
官方提供的版本是用groovy寫的，實(shí)現(xiàn)中有一些細(xì)節(jié)差異嫌变。運(yùn)行效率上差強(qiáng)人意吨艇，在普通PC大概耗時(shí)30秒左右可完成8個(gè)網(wǎng)絡(luò)的魯棒值的計(jì)算。
0x04 將貪心策略進(jìn)行到底
前面我們利用PageRank算法和貪心策略得到了一個(gè)初步的節(jié)點(diǎn)重要性序列腾啥。但是它并不完美东涡，原因是多方面的：包括我們每刪除500個(gè)節(jié)點(diǎn)才重新計(jì)算一次PageRank，也包括評(píng)價(jià)指標(biāo)本身并非完全科學(xué)(或者說評(píng)價(jià)指標(biāo)所期望的和PageRank的最終目的并不一致倘待，PageRank算法是建立在一個(gè)靜態(tài)網(wǎng)絡(luò)的基礎(chǔ)之上疮跑，而評(píng)價(jià)指標(biāo)在不斷的刪除節(jié)點(diǎn)，本質(zhì)是一個(gè)動(dòng)態(tài)變化的網(wǎng)絡(luò))凸舵∽婺铮總而言之，我們第一步得到的節(jié)點(diǎn)重要性序列雖然算不上完美啊奄，但離最優(yōu)解“并不遙遠(yuǎn)”渐苏，我們可以在它的基礎(chǔ)上做一些微調(diào)優(yōu)化，盡可能逼近最優(yōu)解菇夸。
其實(shí)看完剛才評(píng)價(jià)算法的介紹以后琼富，稍微敏銳一點(diǎn)的同學(xué)立馬就能想到：既然能用“構(gòu)圖”的方式來計(jì)算魯棒值，那是不是也可以用“構(gòu)圖”的方式來得到一個(gè)更優(yōu)的序列庄新？是的鞠眉，完全可以，這正是我所使用方法择诈，且同樣是一種基于貪心策略的方法械蹋。
這個(gè)方法出發(fā)點(diǎn)非常直觀：從重要性最低的節(jié)點(diǎn)開始構(gòu)圖，我們希望每一步所添加進(jìn)來的節(jié)點(diǎn)對(duì)當(dāng)前網(wǎng)絡(luò)最大集團(tuán)規(guī)模的影響最小吭从。也就是說朝蜘，在符合算法規(guī)則的基礎(chǔ)上，這個(gè)節(jié)點(diǎn)要么自己新建一個(gè)集團(tuán)涩金，要么加入到其他較小的集團(tuán)中谱醇，這樣對(duì)當(dāng)前最大集團(tuán)規(guī)模不構(gòu)成影響暇仲。如果一定要加入到當(dāng)前最大集團(tuán)中，那么也應(yīng)該盡量使集團(tuán)規(guī)模只增加1或其它較小的數(shù)值副渴。
那么如何尋找這樣的一個(gè)節(jié)點(diǎn)呢奈附？直接在所有節(jié)點(diǎn)中尋找當(dāng)然是可以的，但尋找范圍過于龐大煮剧，有時(shí)很多計(jì)算是完全無必要的斥滤。例如整個(gè)網(wǎng)絡(luò)中PageRank值最高的節(jié)點(diǎn)，顯然是不可能在早期構(gòu)圖階段成為候選節(jié)點(diǎn)并加入到網(wǎng)絡(luò)中的勉盅。因此佑颇，我設(shè)置了一個(gè)搜索窗口，如下圖所示：
[圖片上傳失敗...(image-fd5296-1514533576212)]
其中搜索窗口為一個(gè)動(dòng)態(tài)鏈表草娜，其長度為$k$挑胸，我們每一步都從搜索窗口中尋找一個(gè)對(duì)當(dāng)前連通集團(tuán)規(guī)模影響最小的節(jié)點(diǎn)，從鏈表中刪除并加入到當(dāng)前網(wǎng)絡(luò)中宰闰。然后搜索窗口沿著前進(jìn)方向移動(dòng)一格(實(shí)際上就是從節(jié)點(diǎn)序列中讀取一個(gè)新節(jié)點(diǎn)茬贵，插入到鏈表頭部)，重復(fù)該過程即可移袍。
當(dāng)然解藻，在這個(gè)過程中，$k$的取值至關(guān)重要葡盗，$k$較小時(shí)算法運(yùn)行快但效果差螟左，$k$越大效果越好但所需時(shí)間較長。不過$k$也并非越大越好戳粒，這個(gè)我們后續(xù)再詳細(xì)說路狮。
0x05 小結(jié)
以上就是我在大師賽中的思路與方法，與那些高大上的方法相比是不是顯得有些low蔚约？其實(shí)我本人也覺得這個(gè)方法有些“笨”奄妨，顯得不是那么的“學(xué)術(shù)”∑凰睿總的來看砸抛，我只做了兩件事：
- 用
PageRank算法和貪心策略得到了一個(gè)看起來還不錯(cuò)的節(jié)點(diǎn)重要性序列 - 受大賽官方評(píng)價(jià)算法啟發(fā)，采用逆向思維树枫，在構(gòu)建圖的過程中繼續(xù)使用貪心策略直焙，對(duì)第一步得到的節(jié)點(diǎn)重要性序列進(jìn)行優(yōu)化
但是，真正讓我覺得自己的工作略有價(jià)值的部分不在于思路部分砂轻，而是在工程實(shí)現(xiàn)上奔誓。正如前文所提到的，官方提供的評(píng)價(jià)算法是用groovy實(shí)現(xiàn)的(實(shí)際就是Java)搔涝，效率并不算高厨喂『痛耄可問題在于，我們后續(xù)的算法基本就是建立在評(píng)價(jià)算法的基礎(chǔ)之上蜕煌，需要頻繁的調(diào)用并計(jì)算派阱。
所以，如果直接在groovy版本的代碼上改造并實(shí)現(xiàn)我們的算法斜纪，除非使用非常小的$k$值贫母，否則最終的時(shí)間成本幾乎是不可接受的，但使用較小$k$值又勢必會(huì)影響我們最終的結(jié)果盒刚。
這樣似乎只剩下一種解決途徑：用更高效的語言從頭實(shí)現(xiàn)一遍評(píng)價(jià)算法腺劣。這也是我們下一篇文章要談的，請(qǐng)繼續(xù)關(guān)注本系列的第二篇文章《復(fù)雜網(wǎng)絡(luò)大師賽第四名技術(shù)分享（篇二：工程技巧的勝利）》
如果覺得本文對(duì)你有幫助伪冰，請(qǐng)打賞我一杯咖啡錢~
[圖片上傳失敗...(image-b11dd3-1514533576212)]
