基于Gephi的可視分析方法研究與應(yīng)用

關(guān)迎暉，向 勇，陳 康

（中國電信股份有限公司廣州研究院 廣州510630）

1 引言

全世界正處于一個信息爆炸時代，有大量的數(shù)據(jù)需要進(jìn)行分析、處理和交流，在金融學(xué)、生物學(xué)、社會學(xué)、通信運輸和軟件工程等各大領(lǐng)域，都需要新的處理數(shù)據(jù)的手段?？梢暦治鰧W(xué)是指通過交互式可視化界面促進(jìn)分析推理的一門科學(xué)，是一個多學(xué)科交叉研究領(lǐng)域，涉及以下方面：

·分析推理技術(shù)，使用戶獲得深刻見解，這種見解直接支持評價、計劃和決策的行為；

·可視化表示和交互技術(shù)，充分利用人眼的寬帶寬通道的視覺能力立即觀察、瀏覽和理解大量信息；

·數(shù)據(jù)表示和變換，支持可視化和分析的方式轉(zhuǎn)化所有類型的異構(gòu)和動態(tài)數(shù)據(jù)；

·支持分析結(jié)果產(chǎn)生、演示和傳播的技術(shù)，能與各種觀眾交流，有適當(dāng)背景資料信息。

2 數(shù)據(jù)可視分析技術(shù)

信息通常都以文字為載體，但只通過文字描述，難以讓人們迅速直觀地了解信息，而圖像則能夠以形狀、顏色、大小和成比例縮放等方式編碼大量的數(shù)據(jù)，直觀方便，非常適用于人與人、人與機(jī)器之間的大量信息交流。圖數(shù)據(jù)可視化技術(shù)不僅可以加速人們的閱讀速度，還可以發(fā)現(xiàn)隱藏在信息中的大量至關(guān)重要的關(guān)聯(lián)性細(xì)節(jié)。

圖數(shù)據(jù)可視化方法論，結(jié)合數(shù)據(jù)可視化、數(shù)據(jù)分析和人機(jī)交互技術(shù)解決實際應(yīng)用問題，如圖1所示，有如下4個關(guān)鍵步驟：

（1）數(shù)據(jù)預(yù)處理；

（2）繪圖和布局；

（3）用戶可視化交互；

（4）基于模型的分析。

圖1 可視化分析過程

數(shù)據(jù)可視化工具按照商業(yè)模式，可以分為商業(yè)和開源兩大類。商用可視化工具將諸多可視化的模塊集合在軟件系統(tǒng)中，將各項需要使用的功能、信息基礎(chǔ)設(shè)施等整合成方便操作的工具套件，如Tabluau、Spotfire、QlikView等；開源可視化工具由具備可視化展現(xiàn)、分析以及交互等功能的工 具 包 構(gòu) 建 而 成，如InfoVisToolkit、Prefuse、Improvise、JUNG等。

盡管開源工具在維護(hù)、更新、技術(shù)支持等方面相比商業(yè)化工具存在一定差距，但對于專業(yè)性較強(qiáng)的人員來說更加有效，通過各模塊的隨意組合、與其他工具嵌套等方式組合成新的系統(tǒng)功能會更加靈活強(qiáng)大。更加重要的是，開源可視化工具更方便用戶了解、干預(yù)和掌握數(shù)據(jù)的分析過程。因此，筆者重點研究、分析各開源可視化工具的優(yōu)劣，并開展相關(guān)應(yīng)用研究。

通常通過3個標(biāo)準(zhǔn)來衡量一款開源軟件：可視化功能、可視化分析能力和對開發(fā)環(huán)境的支持。

下面從應(yīng)用軟件和開發(fā)庫兩個方面分析、比較相關(guān)開源可視化方法和工具。

2.1 開源可視化分析應(yīng)用軟件

主要的開源可視化分析應(yīng)用軟件有Cytoscape、Gephi和Graphviz等。

Cytoscape，源自系統(tǒng)生物學(xué)，致力于為用戶提供一個開源的網(wǎng)絡(luò)顯示和分析軟件，提供了網(wǎng)絡(luò)顯示、布局、查詢等方面的基本功能，軟件核心可通過插件架構(gòu)進(jìn)行擴(kuò)展。

Gephi，是一款開源免費跨平臺基于JVM的復(fù)雜網(wǎng)絡(luò)分析軟件，用于各種網(wǎng)絡(luò)和復(fù)雜系統(tǒng)、動態(tài)和分層圖的交互可視化與探測，可廣泛用作探索性數(shù)據(jù)分析、鏈接分析、社交網(wǎng)絡(luò)分析和生物網(wǎng)絡(luò)分析等。

Graphviz由AT&T實驗室啟動，用于繪制DOT語言腳本描述的圖形，也提供了供其他軟件使用的庫。

3種開源可視化分析應(yīng)用軟件的對比如表1所示。

表1 開源可視化分析應(yīng)用軟件的對比

2.2 開源可視化分析開發(fā)庫

JUNG（Java universal network/graph framework）是Java開源項目，為開發(fā)關(guān)于圖或網(wǎng)絡(luò)結(jié)構(gòu)的應(yīng)用程序提供一個易用、通用的基礎(chǔ)架構(gòu)。JUNG功能調(diào)用可以方便地構(gòu)造圖或網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用經(jīng)典算法（如聚類、最短路徑、最大流量等），編寫和測試用戶自己的算法以及可視化地顯示數(shù)據(jù)的網(wǎng)絡(luò)圖。

Prefuse是一個用戶界面包，用來把有結(jié)構(gòu)與無結(jié)構(gòu)數(shù)據(jù)以具有交互性的可視化圖形展示出來，包括任何可以被描述成一組實體（或節(jié)點）或者可以被連接在一起的一些關(guān)系（或邊緣）。支持的數(shù)據(jù)包括具有層次性（如文件系統(tǒng)和組織圖）、網(wǎng)絡(luò)（網(wǎng)絡(luò)拓?fù)浜途W(wǎng)站鏈接）甚至是沒有連接的數(shù)據(jù)集（如時間線）。

NetworkX是Python在圖形和網(wǎng)絡(luò)可視化的一個庫，由BSD發(fā)布，適合大量真實世界的圖形操作，如超過10萬個節(jié)點和100萬節(jié)點的邊緣網(wǎng)絡(luò)展現(xiàn)。由于依賴于一個純Python“dictionary of dictionary”數(shù)據(jù)結(jié)構(gòu)，它是一個合理、高效、可擴(kuò)展、高度可移植的框架，適用于IP網(wǎng)絡(luò)和社交網(wǎng)絡(luò)的分析。

Protovis是一款可視化的圖表工具，基于JavaScript和SVG（scalable vector graphics，可伸縮向量圖形）技術(shù)，由斯坦福大學(xué)可視化組的Bostock M和Heer J開發(fā)。通過使用如條形及點等簡單標(biāo)記將自定義數(shù)據(jù)視圖組合起來，創(chuàng)建標(biāo)準(zhǔn)化的圖表，可以通過動態(tài)屬性定義標(biāo)記，這些屬性通過對數(shù)據(jù)編碼、繼承、形變及布局以簡化結(jié)構(gòu)。

4種開源可視化分析開發(fā)庫的對比如表2所示。

表2 開源可視化分析開發(fā)庫的對比

考慮了代碼復(fù)雜度、跨平臺性和可擴(kuò)展性等各種因素，本文選擇基于Gephi來應(yīng)用和驗證數(shù)據(jù)可視化的方法。

3 Gephi介紹

Gephi提供對數(shù)據(jù)的各種操作和顯示，包括對圖中節(jié)點、邊和標(biāo)簽的調(diào)整、顏色變換以及大的調(diào)節(jié)；實時的布局算法可以對數(shù)據(jù)進(jìn)行各種各樣的布局；同時提供對數(shù)據(jù)圖的過濾顯示，即在獲得數(shù)據(jù)后，可以部分地顯示需要的數(shù)據(jù)；并且提供對部分?jǐn)?shù)據(jù)的單獨保存功能；支持多種格式的文件輸入，支持應(yīng)用插件，更具可擴(kuò)展性，滿足用戶對不同數(shù)據(jù)的處理需求。

Gephi在許多領(lǐng)域都有應(yīng)用，例舉以下幾個方面。

·探索性數(shù)據(jù)分析：對數(shù)據(jù)進(jìn)行實時、直觀的分析。

·鏈接分析：分析對象之間的關(guān)聯(lián)結(jié)構(gòu)。

·社會網(wǎng)絡(luò)分析：易于在社會數(shù)據(jù)中創(chuàng)建社區(qū)地圖和建立小世界網(wǎng)絡(luò)。

·生物網(wǎng)絡(luò)分析：在生物數(shù)據(jù)中發(fā)現(xiàn)其固有的模式或結(jié)構(gòu)。

·廣告創(chuàng)作：提供對圖像、海報的高質(zhì)量打印顯示。

此外，Gephi強(qiáng)大的功能還包括：內(nèi)置的3D渲染引擎、多種可輸入的文件格式（包括GDF（GUESS）、GraphML（NodeXL）、GML、NET（Pajek）、GEXF等）和可定制 的 布 局創(chuàng)建（包括布局工具、數(shù)據(jù)指標(biāo)、數(shù)據(jù)來源、展示設(shè)置等）。

圖2 Gephi的工具包構(gòu)成

利用Gephi工具包，可構(gòu)建功能更強(qiáng)大的可視分析工具，也可以和其他的平臺進(jìn)行集成。

選擇Gephi軟件進(jìn)行可視化分析，除了由于Gephi擁有強(qiáng)大的處理功能外，還擁有許多獨特的功能和簡單易用的特性。

·實時可視化：特設(shè)的OpenGL引擎，能夠以最快的速度將大圖可視化。

·多種布局算法：提供近幾十種布局算法，并可通過插件無限擴(kuò)展，如力引導(dǎo)算法、多層次算法等，這些算法無論在效率上或在質(zhì)量上都是最先進(jìn)的。

·多種統(tǒng)計功能：軟件提供了統(tǒng)計數(shù)據(jù)和指標(biāo)框架的最常用指標(biāo)和無尺度網(wǎng)絡(luò)，包括聚類系數(shù)、平均最短路徑等十多種統(tǒng)計分析功能。

·動態(tài)信息過濾：支持實時地對網(wǎng)絡(luò)圖進(jìn)行選擇或過濾，以方便用戶了解圖中的更多信息。

·支持插件：支持插件，提供可擴(kuò)展性，內(nèi)置的插件中心可以自動從網(wǎng)絡(luò)更新可用插件；也可由用戶自主開發(fā)插件，并可輕松打包和分享。

4 基于Gehpi的可視分析應(yīng)用實例

下面基于Gephi，通過實驗方式來應(yīng)用和驗證數(shù)據(jù)可視化技術(shù)。

自2017年9月—2018年1月，團(tuán)隊采用多階段分層抽樣，分別于不同時間階段進(jìn)行，根據(jù)其專業(yè)將徐州醫(yī)科大學(xué)的醫(yī)學(xué)生分成五層（臨床、麻醉、影像、護(hù)理、口腔），每層隨機(jī)選取2014級、2015級、2016級、2017級各50人。另設(shè)立兩組參照組，即江蘇師范大學(xué)及中國礦業(yè)大學(xué)非醫(yī)學(xué)類專業(yè)本科生各50人；國際教育學(xué)院不同年級的100名醫(yī)學(xué)生。共計1 200人。

4.1 BGP中AS路徑

全球的互聯(lián)網(wǎng)被分成很多個自治域，BGP（邊界網(wǎng)關(guān)協(xié)議）是一種自治系統(tǒng)（AS）的路由協(xié)議，主要用于互聯(lián)網(wǎng)AS之間的互聯(lián)，其最主要功能在于控制AS間路由的傳播和選擇最好的路由，實現(xiàn)IP網(wǎng)不同自治系統(tǒng)間的路由選擇。

從互聯(lián)網(wǎng)技術(shù)而言，不同AS沒有嚴(yán)格的等級區(qū)分。在實際中，根據(jù)網(wǎng)絡(luò)覆蓋和路由可達(dá)程度，互聯(lián)網(wǎng)不同AS域一般可分為3級（Tier 1、Tier 2和Tier 3）。其中，Tier 1網(wǎng)絡(luò)是指不向任何其他網(wǎng)絡(luò)購買互聯(lián)網(wǎng)穿透（IP transit）服務(wù)或付費連接的網(wǎng)絡(luò)，Tier 2/3網(wǎng)絡(luò)一方面向一家或多家上級Tier網(wǎng)絡(luò)甚至同級Tier網(wǎng)絡(luò)購買互聯(lián)網(wǎng)穿透服務(wù)，另一方面也會與多家同級網(wǎng)絡(luò)設(shè)置部分網(wǎng)絡(luò)建立對等互聯(lián)。

通過對基于BGP的AS路由信息進(jìn)行分析，可有效構(gòu)建AS間互聯(lián)的拓?fù)鋱D，從而實現(xiàn)AS級別上的路由策略決策。由于互聯(lián)網(wǎng)上AS數(shù)量及路由信息數(shù)據(jù)量已經(jīng)非常龐大，必須具備適合的可視化工具，才能對分析結(jié)果進(jìn)行全面的展示。

本文使用了2012年4月3日的BGP核心AS數(shù)據(jù)集合，含40 898個節(jié)點，79 161條邊，涵蓋了全球大部分的互聯(lián)網(wǎng)服務(wù)提供商。可視化布局算法采用徑向布局（radial axis layout）算法，節(jié)點度數(shù)按照大小逆時針升序排序，整個圖的平均度數(shù)為3.871，模塊化值為0.517。

（1）BGP結(jié)構(gòu)與AS節(jié)點分析

BGP中所有AS及其路徑的結(jié)構(gòu)如圖3所示，不同的顏色代表不同的分組。最常被連接的AS節(jié)點：AS174節(jié)點度數(shù)為3 349，是美國Cogent Communications公司的節(jié)點；AS3356節(jié)點度數(shù)為3 197，是美國Level 3 Communications公司的節(jié)點。

圖3 BGP中所有AS的徑向分布

（2）群組分析

從BGP數(shù)據(jù)集中共發(fā)現(xiàn)59個群組，群組1占所有AS節(jié)點的8.07%，群組2占所有AS節(jié)點的7.86%，為最大的兩個群組。從圖4中可看到，兩個群組之間的相互交差較小，整個BGP圖的模塊化值為0.517（越大分組越顯著），這些都說明本文的群組發(fā)現(xiàn)效果較好。

（3）Tier 1網(wǎng)絡(luò)的識別

本文探索潛在Tier 1網(wǎng)絡(luò)的方法，是在BGP所有AS節(jié)點中找出節(jié)點度數(shù)最高的一些節(jié)點及其連接路徑，并進(jìn)行圖結(jié)構(gòu)的可視化。需要對BGP圖中AS節(jié)點度數(shù)進(jìn)行過濾，如只顯示節(jié)點度數(shù)超過100和1 000的AS節(jié)點，如圖5和圖6所示。

AS3356和AS3549都屬于美國Level 3 Communications公司，它們之間的交互最為頻繁；此外，美國的AT&T運營商的AS7018，美國Cogent Communications公司的AS174與前面兩個自治域節(jié)點聯(lián)系最為頻繁。這些可視化結(jié)果都是互聯(lián)網(wǎng)數(shù)據(jù)流量狀況的最直觀表現(xiàn)方式。

4.2 Facebook好友關(guān)系

本文從Facebook中用戶賬號的社交信息得出其社交關(guān)系圖，爬取的源數(shù)據(jù)包括姓名、性別、界面語言、位置、賬號年齡、好友列表、消息數(shù)量、評論數(shù)量、標(biāo)注喜歡內(nèi)容等信息。這里試驗的數(shù)據(jù)為一個用戶的關(guān)系數(shù)據(jù)，包括223個節(jié)點、2 845條邊，可視化過程如下：

圖4 群組1和群組2的交互示例及群組1的單獨示例

圖5 節(jié)點度數(shù)大于100的BGP可視化圖

（1）運行Force Altas布局算法；

（2）計算出該關(guān)系圖的模塊化值為0.341（模塊化值越大，群組結(jié)構(gòu)越清晰），平均路徑長度值為2.306（平均路徑長度值越小，該關(guān)系圖節(jié)點間的聯(lián)系越緊密）；

（3）進(jìn)行用戶的各類群組探測（community detection）；

（4）對圖形的標(biāo)簽、節(jié)點、邊和群眾的顏色和字體進(jìn)行調(diào)整；

圖6 節(jié)點度數(shù)大于1 000的BGP可視化圖示例

（5）過濾異常節(jié)點和不需要的群組。

Force Atlas算法得到的Facebook用戶關(guān)系如圖7所示，節(jié)點的大小代表節(jié)點度數(shù)大小，是該節(jié)點用戶在社交關(guān)系圖中的重要程度的刻畫，大型節(jié)點為核心節(jié)點；節(jié)點之間的邊連接著用戶及其好友，其長度代表了在此關(guān)系圖中的聯(lián)系頻繁程度。在圖中也已經(jīng)分析出不同灰度的部分，節(jié)點的不同灰度代表了檢測出來的不同的群組。

對關(guān)系全圖進(jìn)行群組分析結(jié)果如圖8所示，如圖8（a）為同學(xué)群組，圖8（b）為校友群組，圖8（c）為生活好友群組，圖8（c）為工作群組，而圖8（f）為散點則表明可能是陌生人。Gephi群組分析與真實數(shù)據(jù)的關(guān)系十分相符，證明了本文可視化分析方法的優(yōu)越性。

4.3 Python/PyPI庫依賴關(guān)系

使用可視化技術(shù)分析了Python的所有開發(fā)函數(shù)庫，從PyPI（Python package index）倉庫的所有工具包上抽取依賴關(guān)系列表，建立一個完整的依賴關(guān)系圖（dependency graph），以揭示每個工具包是如何彼此依賴的，也可判斷出“install_requires”參數(shù)的依賴關(guān)系是動態(tài)還是靜態(tài)的：

（1）使 用XML-RPC API，從PyPI中 收 取 所 有 的 函數(shù)庫；

（2）下載函數(shù)庫的所有版本并從 “install_requires”參數(shù)中抽取出“setup.py”文件；

（3）把依賴關(guān)系結(jié)果抽取并存儲在 “pypi-deps.csv”文件中；

（4）使用Gephi或工具分析源數(shù)據(jù)（20 661個節(jié)點，14 047條邊），構(gòu)造可視化圖，并支持用戶動態(tài)拖動以獲取某一依賴關(guān)系，如圖9所示。

由圖9可以看到，圖中間部分十分密集，為了獲得更多信息，采用模塊化對中間兩塊進(jìn)行詳細(xì)分析，如圖10所示。

通過圖10可以看出，雖然黑色、灰色兩個模塊都是最主要的模塊，不過各有不同點：模塊1的包互相引用的次數(shù)低，但包多；模塊2互相引用的次數(shù)高，但包較少。由圖10（d）可以很清晰地看出這一點，這也說明模塊2所包含的包應(yīng)該是成套使用的。

圖7 Force Atlas算法得到的Facebook用戶關(guān)系全圖

圖8 Facebook用戶關(guān)系群組分析子圖

圖9 Python/Pypi庫依賴關(guān)系（從左到右，比例不斷放大）

圖10 包的模塊化分析

為了分析出全部Python/PyPI庫里重要的包以及包之間的關(guān)系，對生成的可視化圖進(jìn)行更多的分析。如圖11所示是被50個以上的包所引用的包，這些也是庫里最重要的包。

在圖11中可以看到setuptools包是最重要的包，而事實上該包是用于安裝其他包的工具，這很符合現(xiàn)實情況。而各種版本的Django、lxml和PIL等包也是Python庫里起基礎(chǔ)作用的包。

5 結(jié)束語

研究數(shù)據(jù)的可視分析技術(shù)能解決圖形繪制、圖形展現(xiàn)、人機(jī)交互和數(shù)據(jù)分析等眾多問題，本文對業(yè)內(nèi)最新發(fā)展成果、分析方法與過程、典型的應(yīng)用等方面都做了系統(tǒng)的介紹與論述。與此同時，可視分析技術(shù)也面臨眾多挑戰(zhàn)，例如，如何無縫融合信息可視化和數(shù)據(jù)分析技術(shù)，如何更好地處理海量、實時的、分布的互聯(lián)網(wǎng)數(shù)據(jù)信息等。為了更好地幫助用戶處理日益增長的文本信息，未來可視分析技術(shù)可改善現(xiàn)有布局算法，以提高實時的、大量的數(shù)據(jù)可視化效率，并且綜合運用各種人際交互方法，提高展現(xiàn)效果，轉(zhuǎn)化成可規(guī)?；虡I(yè)應(yīng)用的能力。

圖11 被引用大于50的包

1 Auber D,Chiricota Y,Jourdan F,et al.Multiscale visualization of small world networks.Proceedings of IEEE Symposium on Information Visualization,Seattle,WA,USA,2003:75～81

2 Bennett C,Ryall J,Spalteholz L,et al.The aesthetics of graph visualization.Proceedings of Computational Aesthetics in Graphics,Visualization,and Imaging,Banff,Alberta,Canada,2007

3 Walshaw C．A multilevel algorithm for force-directed graph drawing．Journal of Graph Algorithms and Applications,2003,7(3):253～285

4 Muelder C,Ma K L.Rapid graph layout using space filling curves.IEEE Transactions on Visualization and Computer Graphics,2008,14(6):1301～1308

5 Collins C,Carpendale S.VisLink:revealing relationships amongst visualizations.IEEE Transactions on Visualization and Computer Graphics,2007,13(6):1192～1199

6 Card S C,Mackinlay J,Shneiderman B.Readings in Information Visualization:Using Vision to Think.San Francisco:Morgan Kaufmann Publishers,1999

7 Hu Yifan.Efficient,high-quality force-directed graph drawing．The Mathematica Journal，2005，10(1):37～71

8 Gephi.http://www.gephi.org,2012