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

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

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

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

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

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

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

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

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

破冰之斧——ForceAtlas2布局算法

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

斧之利刃——分割繪圖法

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

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

破冰之旅——使用分割繪圖法對學(xué)術(shù)網(wǎng)進(jìn)行可視化

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

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

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

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

圖3社區(qū)標(biāo)號與社區(qū)中節(jié)點(diǎn)關(guān)系

圖4社區(qū)劃分?jǐn)?shù)量分布統(tǒng)計(jì)

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

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

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

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

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

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

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

子圖的分別布局

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

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

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

子圖的拼合

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

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

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

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

，該社區(qū)的各個(gè)節(jié)點(diǎn)的坐標(biāo)為

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

合并圖的微調(diào)

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

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

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

圖8圖例

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

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

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

圖9

圖10

圖11

圖12

新紀(jì)元下的展望——分割繪圖法的衍生應(yīng)用

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

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