目前已有的可視化技術可處理的節(jié)點規(guī)模上限在十萬量級。當網(wǎng)絡中節(jié)點數(shù)超過該上限時，布局算法的效率便急劇下降。上海交通大學Acemap團隊便提出了一種突破百萬量級壁壘的可視化繪圖新方法。本文以Acemap數(shù)據(jù)庫中收集的Nature雜志論文引用關系數(shù)據(jù)集為例，展現(xiàn)了超大規(guī)模學術網(wǎng)絡可視化的破冰之旅！

數(shù)據(jù)可視化通俗來說就是使用圖形來表達抽象數(shù)據(jù)的結(jié)構(gòu)、變化、聯(lián)系、或趨勢。數(shù)據(jù)可視化的發(fā)展已經(jīng)有幾百年的歷史，而上世紀五十年代計算機的發(fā)明使人類處理數(shù)據(jù)的能力有了質(zhì)的提升。

與此同時，隨著計算機技術的飛速發(fā)展，人類開始創(chuàng)造各式各樣體型龐大的數(shù)據(jù)集。數(shù)據(jù)集的內(nèi)容變得越來越抽象且復雜，簡單的可視化方法已經(jīng)無法滿足人們的需求。

數(shù)據(jù)可視化用來創(chuàng)造一條快速認識數(shù)據(jù)集的捷徑，圖形化的數(shù)據(jù)表示方法能夠?qū)⑷祟惖淖⒁饬ξ街匾繕?，搭建人類與數(shù)據(jù)進行溝通的橋梁。根據(jù)不同數(shù)據(jù)集的特點，對數(shù)據(jù)可視化方法進行研究，從而最終得到可視化結(jié)果的過程本身并不容易，因此大數(shù)據(jù)可視化本身就是一門藝術。

圖1統(tǒng)計學家John Wilder Tukey：信息可視化理論的重要奠基者(1915—2000)

目前已有的網(wǎng)絡可視化算法如Force Atlas，F(xiàn)orceAtlas2，F(xiàn)ruchterman Reingold，Yifan Hu等算法可處理的節(jié)點規(guī)模上限在十萬量級。當網(wǎng)絡中節(jié)點數(shù)超過該上限時，布局算法的效率便急劇下降。而學術網(wǎng)絡中的節(jié)點數(shù)量通常在百萬量級甚至更高，算法的性能瓶頸和實際需求間的巨大差異對于揭示實際學術大數(shù)據(jù)空間結(jié)構(gòu)形態(tài)造成了巨大障礙，面臨諸多嚴峻的技術挑戰(zhàn)。

上海交通大學Acemap團隊聚焦此項問題，另辟蹊徑，提出了一種突破百萬量級壁壘的可視化繪圖新方法，為超大規(guī)模可視化的可實現(xiàn)性提供了新的突破口，開啟了學術大數(shù)據(jù)空間可視化新紀元。接下來，本文將以acemap數(shù)據(jù)庫中收集的Nature雜志論文引用關系數(shù)據(jù)集為例，向您展現(xiàn)超大規(guī)模學術網(wǎng)絡可視化的破冰之旅！

超大規(guī)模學術網(wǎng)絡——Nature雜志論文引用關系數(shù)據(jù)集

Nature雜志論文引用關系數(shù)據(jù)集來源于Acemap數(shù)據(jù)庫，數(shù)據(jù)集包含了Nature雜志中的所有論文與這些論文引用的其他論文總共2053310篇。其中囊括了生物、物理、機械、化學、心理學等19個領域。從直觀上來說，數(shù)據(jù)可視化完成后在整體上將會有明顯的聚類效果，因為相同領域內(nèi)的引用關系一定會比不同領域間的引用關系更加密切。除此之外，數(shù)據(jù)集中包含3426847條邊，用來表示數(shù)據(jù)集中論文之間的引用關系。

破冰之斧——ForceAtlas2布局算法

ForceAtlas2布局算法是一種力引導算法。該算法整合了包括Barnes Hut近似，度決定性斥力，全局與局部迭代速度自適應調(diào)整等技術。相比于Force Atlas算法，F(xiàn)orceAtlas2運行速度更快，并且處理的圖的規(guī)模更大。算法運行時，節(jié)點與節(jié)點之間將會相互排斥，存在連邊的兩個節(jié)點將會相互吸引。當算法穩(wěn)定后，用戶將得到一個穩(wěn)定的布局。

斧之利刃——分割繪圖法

當數(shù)據(jù)體量增長到一定程度后，以往的可視化方法無論從計算的準確性，還是可視化結(jié)果的可展示性都將遇到瓶頸，直接將所有數(shù)據(jù)放入布局算法中進行計算似乎是不可行的。于是我們提出使用分割繪圖法對大規(guī)模學術網(wǎng)絡進行可視化的方法。

分割繪圖法的整體思路就是使用某種啟發(fā)式算法，在數(shù)據(jù)進行可視化之前，檢測數(shù)據(jù)的結(jié)構(gòu)，并根據(jù)數(shù)據(jù)在結(jié)構(gòu)上的聯(lián)系將數(shù)據(jù)集分割為多個社區(qū)。分割后的單個數(shù)據(jù)集已經(jīng)在布局算法可以處理的范圍之內(nèi)，這時我們需要將這些數(shù)據(jù)集進行分別布局，然后將布局完成的小圖，以某種合理的方式進行拼接，最后再使用布局算法進行微調(diào)，即可得到最終的可視化。

破冰之旅——使用分割繪圖法對學術網(wǎng)進行可視化

數(shù)據(jù)分割

我們使用啟發(fā)式算法根據(jù)數(shù)據(jù)集節(jié)點在結(jié)構(gòu)上的聯(lián)系對其進行分割，分割的具體流程如下。

圖2使用啟發(fā)式算法實現(xiàn)數(shù)據(jù)集數(shù)據(jù)的結(jié)構(gòu)分割流程圖

圖3為社區(qū)劃分結(jié)果統(tǒng)計：

圖3社區(qū)標號與社區(qū)中節(jié)點關系

圖4社區(qū)劃分數(shù)量分布統(tǒng)計

圖3顯示了社區(qū)劃分完成后4917個社區(qū)中節(jié)點數(shù)量的分布，圖4顯示不同社區(qū)節(jié)點數(shù)量級中社區(qū)數(shù)的分布。在社區(qū)數(shù)量分布來說，社區(qū)節(jié)點數(shù)量最多分布在1000以下，總共占總體的97%，社區(qū)中節(jié)點數(shù)量超過1000的占總體的3%，其中更是有兩個社區(qū)節(jié)點的數(shù)量超過了12萬，可見這些社區(qū)中核心節(jié)點的影響力之大。

根據(jù)社區(qū)劃分的數(shù)量與最終的模塊度可以看出：社區(qū)劃分的效果較好，可知該數(shù)據(jù)集本身就具有非常強的結(jié)構(gòu)性，且這種強結(jié)構(gòu)性對后面圖結(jié)構(gòu)等效模型的提出有很好的啟蒙作用。

等效結(jié)構(gòu)的獲取

為了解決社區(qū)的塊間布局的計算，我們重新對基于引斥力模型的ForceAltlas2算法進行研究。在ForceAltlas2算法中，決定節(jié)點位置的最本質(zhì)因素是一個節(jié)點所受的引力和斥力。同理，一個社區(qū)的最終位置也由該社區(qū)所受的引力和斥力決定，且社區(qū)內(nèi)各個節(jié)點之間的力不會影響社區(qū)之間的引力和斥力。我們通過將社區(qū)中的所有節(jié)點等效為一個節(jié)點，進而得到數(shù)據(jù)集結(jié)構(gòu)的等效模型。

圖5為等效結(jié)構(gòu)的Gephi渲染結(jié)果

圖5 Nature雜志引用關系數(shù)據(jù)等效結(jié)構(gòu)模型

該結(jié)構(gòu)由社區(qū)節(jié)點數(shù)大于等于1000的149個社區(qū)進行等效，因為大圖的總體社區(qū)結(jié)構(gòu)應由節(jié)點數(shù)較多的社區(qū)決定，節(jié)點數(shù)較少的社區(qū)可能會對圖的局部布局產(chǎn)生影響，但不會對整體結(jié)構(gòu)形狀造成影響，因此這些節(jié)點的作用可以暫時忽略。該圖中的綠色節(jié)點表示社區(qū)的等效節(jié)點；綠色節(jié)點間的連邊表示不同社區(qū)之間的等效連邊，他們有不同的權重；綠色節(jié)點外的白色節(jié)點的作用是為了平衡不同社區(qū)之間的斥力。

子圖的分別布局

我們使用ForceAtlas2算法對劃分的結(jié)果進行分別布局，圖6為ForceAtlas2算法收斂后選取的部分社區(qū)的可視化結(jié)果：

圖6 ForceAtlas2算法對部分社區(qū)進行可視化的結(jié)果

在圖6中社區(qū)以不同的結(jié)構(gòu)形態(tài)聚集在一起，有些社區(qū)存在多個核心，比如community_4，community_5，community_8，這些社區(qū)所包含的領域中的論文可謂是“百花齊放”；有些社區(qū)只存在一個核心，比如說community_1，這些社區(qū)中核心論文可謂是“一枝獨秀”。

子圖的拼合

當我們得到Nature雜志引用關系數(shù)據(jù)的等效結(jié)構(gòu)與每個社區(qū)在ForceAtlas2算法下的布局后，我們現(xiàn)在就可以進行社區(qū)的拼合工作。

首先，由于我們得到的結(jié)構(gòu)是一個相對真實結(jié)構(gòu)等比例縮放的結(jié)構(gòu)，他不一定能夠較好地容納各個社區(qū)。因此，我們需要對得到的等效結(jié)構(gòu)進行等比例縮放，以適用每個社區(qū)的大小，并且避免每個社區(qū)之間有過多的重疊或者社區(qū)之間的距離過大的問題。對結(jié)構(gòu)進行縮放非常簡單，只需要將結(jié)構(gòu)中的每個中心節(jié)點的坐標乘上一個縮放因子即可，即：

由于拼合完成的圖結(jié)構(gòu)最終還需要進行微調(diào)，所以進行拼合時不需要將結(jié)構(gòu)計算的非常精確，因此我們只需要手動調(diào)節(jié)參數(shù)λ到圖結(jié)構(gòu)合適即可。

當完成圖結(jié)構(gòu)大小的調(diào)節(jié)后，我們需要進行圖的拼接。圖的拼接同樣很簡單，假設等效結(jié)構(gòu)中某社區(qū)的中心節(jié)點為

，該社區(qū)的各個節(jié)點的坐標為

，則該社區(qū)中每個節(jié)點在大圖中的位置為：

合并圖的微調(diào)

在前面的操作當中，我們通過對社區(qū)進行分別布局，進而得到了Nature雜志論文引用關系數(shù)據(jù)布局的局部最優(yōu)解，但通過上述的拼合方式得到的布局并不是全局的最優(yōu)解，因此我們需要使用微調(diào)的方式來消除上述拼合過程中產(chǎn)生的誤差。

為了保留數(shù)據(jù)的完整性，我們需要將先前忽略的數(shù)據(jù)補全。當完成數(shù)據(jù)補全后，我們可以開始圖的微調(diào)工作了。微調(diào)完成后，我們已經(jīng)得到所有節(jié)點的位置信息。到此時，節(jié)點布局的基本工作已經(jīng)完成，這時我們需要將節(jié)點信息通過Gephi渲染，圖7為Gephi最終渲染的結(jié)果：

圖7 Nature雜志論文引用關系數(shù)據(jù)可視化結(jié)果（2053310個節(jié)點，3426847條邊）

圖8圖例

由圖7可見，Nature雜志論文引用關系數(shù)據(jù)存在較強的結(jié)構(gòu)性。圖中最外層一圈細細的圓環(huán)是數(shù)據(jù)集中度為0的點，他們沒有引力的作用，因此呈現(xiàn)在圖的最外層；圖中產(chǎn)生了超級大的紅色節(jié)點，該點屬于生物學領域，論文名稱為“Cleavage of Structural Proteins during the Assembly of the Head of Bacteriophage T4”，據(jù)不完全統(tǒng)計，這篇文章已經(jīng)達到了118282的引用量，引用數(shù)已經(jīng)到達數(shù)據(jù)總量的1/20，達到了生物學領域數(shù)據(jù)量的1/10，可見這篇文章的影響力之大。圖7能夠顯示出較好的聚類效果，紅色區(qū)域表示生物學領域，生物學領域的文章的數(shù)量占據(jù)了Nature雜志一半還要多，在圖中能夠有較好的體現(xiàn)；然后物理學與機械領域分別占據(jù)了11.17%和9.11%；這些領域之間存在相互交疊的，交疊表示兩個領域之間存在學科交叉。

理想彼岸終到達——可視化結(jié)果的呈現(xiàn)

完成數(shù)據(jù)的可視化后，我們還進行了節(jié)點的重疊去除，圖的分層加載，由于篇幅限制，在此不再贅述。一下為可視化結(jié)果不同放大級別的展示。

圖9

圖10

圖11

圖12

新紀元下的展望——分割繪圖法的衍生應用

分割繪圖法開創(chuàng)性地突破了網(wǎng)絡大數(shù)據(jù)可視化百萬量級的屏障，為超大規(guī)模作圖帶來了新鮮血液。該方法可將大部分學術網(wǎng)絡一次性畫出，從而有望揭示整個學術領域的全貌，以及世界范圍內(nèi)的精準學術定位，并對世界范圍內(nèi)的學術地圖繪制提供重要思路。分割繪圖法除了在超大規(guī)模學術網(wǎng)絡可視化中發(fā)揮巨大作用外，該方法同樣可以擴展到其他具有結(jié)構(gòu)性的超大規(guī)模網(wǎng)絡，例如大規(guī)模社交網(wǎng)絡。

超大規(guī)模數(shù)據(jù)可視化領域仍有許多屏障需要我們?nèi)ネ黄?，這正是吾輩需要努力之處。總之，革命尚未成功，同志仍需努力！