人物關系的可視化研究①

邱秀連, 康 倩1,, 王 崢

1(武漢郵電科學研究院 通信與信息系統,武漢 430070)

2(南京烽火軟件科技有限公司,南京 210019)

信息可視化通過將數據映射為容易感知的圖形、符號、顏色等,可以增強數據呈現效果,讓用戶以直觀交互的方式實現對數據的觀察和瀏覽,從而發現數據中隱藏的特征、關系和模式[1],為其對數據做進一步分析和處理提供參考思路.

Web相關的人物關系可視化成果,目前已有的百度知心、搜狗知立方等人物關系圖,都是近似于靜態的展示,交互性弱,拓展和布局均是有限且固定的,不能動態滿足用戶需求. 且未能對特定人物關系做出標識,故本文研究無向圖多最小環算法,以便于隱含團體關系的求解.

類庫D3.js是實現可視化的很好選擇. 趙聰[2]和權慶樂[3]對D3的特性做了闡述,權鑫[4]基于D3實現了可視化系統框架,Daniel等[5,6]將數據驅動應用于可視化取得了較好的效果,但以上均未涉及人物關系的可視化實現.

Dijkstra算法是圖論中求取最短路徑的經典算法.王樹西[7]改進Dijkstra以求多條最短路徑; 湯志貴[8]則討論了基于Dijkstra求解最小環的樸素算法. 但并不能解決無向圖多最小環問題.

本文結合D3.js可視化庫的數據驅動、高效靈活的特點,實現了以力導向布局為基礎的人物關系圖,并結合需求,改進了最短路徑算法,以求解無向圖的全部最小環,動態標識人物團體關系.

1 無向圖經指定頂點的最小環算法

對于由頂點集V和邊集E構成的圖Dijkstra是求解單源點到所有頂點最短路徑的經典算法. 雖然相關研究和改進很多[7-10],但對于無向圖求解經指定頂點的全部最小環,尚未討論充分. 對于無向圖,由于鄰接矩陣為對稱型,Dijkstra直接求環時,會將其理解為雙向圖,鄰接的兩點間自成一“環”,且在不考慮權重時,此“環”為最小環,然而,這并不是我們預想的環. 如圖1所示,B為指定頂點A的鄰接點,理解為雙向圖時,可構成“環”A-B-A,而實際上,該無向圖中最小環為A-C-D-A(或A-D-C-A)的三元環. 對于對稱型鄰接矩陣,由于Dijkstra無法區分無向圖和雙向圖,從而導致錯誤解.

圖1 無向圖鄰接點自成“環”

另外,圖中某頂點可能有多個鄰接點,故可能存在多條權重相同的最短路徑. 由于Dijkstra在比較路徑的“長短”時,忽略掉等權重的路徑,僅當存在“更短”路徑時,才考慮更新最短路徑. 致使結果只有一條最短路徑,用于求最小環,也只能得一環.

對于上述弊端,本文討論與改進如下：

無向圖G中頂點v的度記為dG(v),與其布爾鄰接矩陣matrixboolean存在關系從環的特點出發,可對圖進行預處理,由于 ? 頂點v∈{環集合}G,?dG(v)≥2,在求解最小環之前,遞歸過濾圖中滿足dG(v)≤1的點,剩余頂點n′(n′＜n)個,可降低求環過程中的復雜度.

設預處理后的圖為G',頂點v的鄰域為NG′(v),所求環經指定頂點v0,初始化鄰接矩陣matrix、路徑向量pre_path、距離向量dist. 切斷中心節點v0與其鄰接點u的連接v0-u,dijkstra求解v0到的u的最短路徑,算法在松弛過程中,將等于當前最短路徑的值同樣考慮在內,最短路徑的一個或多個前置鄰接點都存儲在pre_path中,再恢復v0-u,從而構成環. 直至遍歷完,選取最小環.

求解無向圖經指定頂點全部最小環算法偽代碼實現如下：

該最小(環算法)用于求解關系圖的人物團體關系,復雜度為Om?n′2,m為G'中指定頂點的鄰接點個數,n'為G'中頂點的總個數.

相較于文獻[7],本文算法考慮了多最短路徑到多最小環的應用; 文獻[8]雖討論了最小環的求解,但給出的(兩)種算法均未考慮多鄰接點問題,且復雜度均為On3,對于經特定頂點的情況,存在冗余計算,本文從環(的特點)出發對圖進行預處理,將復雜度降為Om?n′2.

2 D3.js

2.1 D3.js與力導向布局介紹

數據驅動文檔(Data Driven Documents)[11]是一個大數據下的開源可視化工具,簡稱D3,是基于數據的文檔操作JavaScript庫. D3 結合功能強大的可視化組件和數據驅動的方法對文檔對象模型(DOM)進行操作,可以將任意數據綁定到DOM. 將數據和HTML、SVG[12]、CSS結合起來,創造數據圖表. D3.js采用的是鏈式語法[13],為開發者提供了便捷的調用方式. D3最突出的特性是數據驅動,不隱藏用戶原始數據,避免了局限的數據展現,提供了強大的靈活性.

本文的人物關系的可視化采用力導向布局,該布局是模擬彈簧電荷模型,在每兩個節點間添加斥力,每條邊的兩節點間添加引力,每次迭代節點會在各個斥力和引力的作用下發生位移,多次迭代后,節點會靜止于受力平衡的位置,達到模型的能量最小化.

D3提供了諸多類型的布局(layout)函數,d3.layout.force就是D3中實現力導向布局的對象,該對象封裝了很多參數設定的方法. 其中,size方法用于設定畫布尺寸和重心位置,linkStrength、linkDistance分別設置邊強度和邊長度,摩擦系數friction主要影響速度衰減,電荷作用力charge表現為節點間的引力或斥力,chargeDistance為引力作用距離,向心力gravity以微弱牽引作用將節點吸引至布局幾何中心. 力導向布局的結果有良好的對稱性和局部聚合性,在平面上布局產生很少的邊交叉,清晰美觀.

2.2 d3.layout.force改進

d3.layout.force中nodes和links方法分別為節點和邊的數據接口,start函數為布局做準備,包括數據格式的映射和初始化圖元位置,tick函數則使節點在各個作用力下迭代運動直至收斂平衡.

但適用于第三版D3.js力導向圖的數據有一定要求,links中傳入的關系數據,“source”和“target”字段,作為連線兩端的標識,必須指向nodes中節點相應索引(從0開始的連續整數,或者nodes對象的屬性名),并不能依據用戶指定的字段而建立邊與點之間的映射關系. 由于索引的連續性,添加或刪除某節點,會影響其后所有節點的索引,進而影響相關連線兩端的標識.文獻[13]中所提到的代碼方式,D3.js本身并不能通過迭代自動建立聯系. 基于本文中數據交互較為頻繁多變,每次重新建立索引較為繁瑣且易出錯,D3原來的數據結構無法有效處理數據,故改進D3.js源碼,使d3.layout.force迭代關聯數據時,判斷relevance指向關系,實現邊-節點間的映射關系可自定義化,即可指定節點的某一特征或屬性建立關聯,靈活且直觀,同時也便于開發過程中的調試. start函數建立映射部分改進的核心代碼如下：

改進后的D3.my.js,保留D3.js原始的邊-節點之間的關系,即默認情況(不指定關聯字段)仍由節點索引建立關聯. 指定關聯屬性的情況下,可根據指定屬性建立關聯. 示例如下：

可見改進后的關聯關系更加直觀且靈活,但需注意的是關聯屬性值須具有唯一性.

力導向布局的迭代運動過程,每次位移重繪消耗較大,依D3的布局收斂條件,會存在冗余震蕩,即后期較多時間的運動對布局無明顯效果,本文在無明顯布局誤差的情況下,限制迭代次數.

對改進前后性能進行了對比驗證,以chrome52瀏覽器作為驗證工具,改進前后的布局準備beforestart、after-start耗時和布局總耗時before-end、afterend如圖2所示,其中end與start的差為布局迭代運動重繪耗時.

圖2 改進前后性能對比

由上圖不難發現,隨節點數量的增加,改進前,力導向布局迭代的時間消耗急劇增加,改進后的布局迭代耗時增長緩慢很多,性能有明顯改善. 改進前后,數據準備階段耗時幾乎一致,說明指向關系的改進在沒有增加額外消耗的情況下,增強了D3庫的可用性.

3 人物關系可視化設計

3.1 整體架構

根據CARD可視化模型可以將信息可視化的過程分為以下幾個階段：數據預處理,繪制、顯示和交互[14].傳統可視化模型又叫流水線模型,缺陷是未考慮用戶交互需求,可視化回路模型[15],解決了用戶交互的問題,使用戶對于數據的挖掘和了解有了更多可能性,但頻繁的前后臺的交互操作加大了系統的開銷. 王子毅等提出的Drilldown模型[15]較好的解決了這個問題,但該文基于Echarts的實現過于復雜. 而D3恰好具有良好的數據驅動特性,可以不需要過于復雜的處理而實現高性能交互.

本文根據人物關系可視化的實際業務需求,采用Tomcat 7.x作為服務器,Oracle 11g作為數據庫,后臺采用Java編寫,前端應用Html、JavaScript、compass等技術,實現人物關系的圖譜展示,并實現一定的基于數據的交互功能. 系統的框架描述如圖3.

圖3 系統框架流程

信息可視化過程中,依據數據的轉換可劃分為：原始數據到數據表、數據表到可視化結構、可視化結構到視圖的三個轉換過程.

數據交互中,一部分交互是基于前端后臺的,應用Ajax異步傳輸數據,完成前后臺的數據交互,如通過人員ID搜索人物關系; 另一部分交互則是利用d3.js的數據驅動特性,使得可以不向后臺發送http請求而獲取到相應數據,如鼠標單擊人物節點進行詳情展示,回調函數直接調取節點數據,大大減小服務器端負擔,縮減了響應時間,提高了用戶體驗效果.

3.2 數據處理

(1)親密度

引入親密度,量化描述人物間的關系,考慮聯系類型(書信、電話、郵件、在線聊天工具等)和互動次數兩個維度,親密度定義(依據不同業務需求,可調整)如式(1).

其中Intimacy(u,v)表示u和v之間的親密度,wi為聯系類型i的權重,Ii(u,v)為u、v以i方式進行交互聯系的總次數. 為便于定量篩選,式(2)將親密度量化至0～100.

MAX和MIN分別為親密度的最大和最小值.

另外,本文中的人物關系實際上是混合圖,既有有向邊(如父子關系)又有無向邊(如好友關系),且存在重邊(兩人間可能存在多種關系,如既是母女關系又是師生關系). 本文在數據處理中合并重邊,依賴親密度大小排序,標識所有關系,以最大親密度作為合并親密度,將混合圖簡化為無向簡單圖.

(2)數據庫設計

張運良[16]將關系和節點存儲在一張表中,由于節點數據的重復,會造成大量的數據冗余,且不便于數據更新,本文將關系和節點信息分存于兩張表中,以用戶ID作為關聯信息.

本文中數據庫共設計兩張表nodes和relation,分別用于存儲人物信息和人物間的關系信息,部分字段及數據如表1和表2所示.

表1 人物節點nodes表的部分字段

表2 關系節點relation表

(3)多最小環模塊

運用第1節的經指定頂點的無向圖多最小環算法,標識當前界面中的團體關系,采用流程如圖4.

圖4 最小環數據處理模塊

當界面中顯示圖的內容發生變化時,需要計算或者重新計算,將當前節點數據nodes和關系數據links作為最小環模塊的輸入. 遞歸去除度不大于1的點及與其相連的邊,得到預處理后的數據nodes’和links’. 對節點進行編號,初始化鄰接矩陣,利用無向圖多最小環算法計算最小環路徑集合. 最后通過編號映射回節點和邊的數據,更新視圖對應邊的strokewidth屬性,以達到標識團體關系的目的.

3.3 視圖交互

為了開發思路清晰,便于后期維護,前端視圖邏輯共分四個模塊D3、relation、circle、index,每個模塊封裝為一個Object,以require.js管理模塊依賴,便于各個模塊間的相互調用.

relation.draw() 調用d3.layout.force(),使用力導向布局,傳入nodes、links數據以及size、linkDistance、charge等參數,使圖元與數據建立映射關系,D3通過執行映射規則,將抽象數據轉為直觀圖像. 以分組不同語義的svg元素,便于不同視圖元素的層級設置,定義各元素的事件回調,完成畫圖及界面事件監聽功能. relation.update()接受新的數據,更新視圖.

人物信息按照用戶關注程度,分為三個等級,關系圖通過交互形式實現信息的多級鉆取,呈現于不同位置：關系圖節點處標識核心信息,懸浮框顯示次要信息,個人檔案頁顯示人員全量信息.

不同于文獻[16]的動態交互,點擊節點查詢為關系擴展,而非另一個初始查詢,避免頻繁移焦而使用戶失去方向. 同時本文做了關系層級限制,通過限制當前顯示信息量,以減少感知超載問題,將關系限制在以中心人員為中心的三層關系內.

鼠標懸浮于人物節點時,交互響應行為為該節點放大并且沿線顯示與該節點直接相關的關系描述標簽;雙擊該節點實現關系拓展; 單擊彈出詳情懸浮框; 拖拽節點后可重新布局. 其中,對于瀏覽器來說,雙擊操作會觸發兩次單擊事件,本文采用設定定時器的方式來判定區分用戶端的單擊和雙擊操作.

4 實現

本文通過編碼,對以上理論進行實踐,效果展示如圖5至圖10.

圖5 人物關系圖整體界面

圖6 根據ID查詢關系

圖5為人物關系可視化整體界面,分為查詢區、視圖區、人物卡片區(提供檔案頁入口),鼠標懸浮某節點可沿連線方向顯示關系描述; 圖6為查詢某ID后的結果,視圖節點處顯示人物圖片和姓名,中心人物有視覺突出效果; 圖7為對圖2結果集進行親密度過濾后的結果; 圖8是雙擊人物節點后拓展關系; 圖9中則是計算當前視圖中包含中心節點在內的所有最小環,通過連線加粗的方式標識了人物間的團體關系; 圖10為單擊節點后,以懸浮框的形式顯示人物詳情,并提供人員檔案的入口.

圖7 親密度過濾

圖8 關系拓展

圖9 最小環團體

圖10 詳情懸浮框

以6組不同數據驗證人物關系可視化系統,結果如表3.

表3中,實驗1與實驗2對比,實驗3與實驗4對比可證,最小環處理模塊因為對度小于2的點的預處理,求解過程耗時較少,對于相對稀疏的圖,效果明顯.

實驗3、4與實驗6對比,可見更新后需重新布局的節點個數相當時,更新節點數較少比更新點數多時,更新布局耗時較少,因為圖中元素只有少部分的被更新節點附近的點需要移動,而對大部分節點而言,更新節點帶來的受力變化可以忽略不計或者很小,經過較少次迭代即可達到收斂條件. 實驗5與實驗6對比,剩余點數點數越多,重新布局越耗時.

表3 6組實驗結果

5 結論與展望

本文深入了解了D3.js的特性和工作機制,基于改進的D3.js可視化庫,利用力導向合理布局,實現了動態交互的人物關系可視化原型,直觀、有效地展現人物間的關聯關系及團體關系,以交互的形式實現數據多級鉆取,進一步探索對象相關信息,滿足了動態交互的基本要求. 在以后的研究中,視圖與交互細節,如視圖多樣性和圖譜的再編輯性等還需做深入探討和實現.

1 楊彥波,劉濱,祁明月. 信息可視化研究綜述. 河北科技大學學報,2014,35(1)：91-102. [doi：10.7535/hbkd.2014yx01016]

2 趙聰. 可視化庫D3.js的應用研究. 信息技術與信息化,2015,(2)：107-109.

3 權慶樂,連衛民. 對可視化庫D3.js的應用研究. 電子技術與軟件工程,2014,(18)：203.

4 權鑫. 基于D3.js的數據可視化系統框架設計與實現[碩士學位論文]. 北京：北京交通大學,2016.

5 Craw D,Block J,Lin K,et al. Firemap：A dynamic datadriven predictive wildfire modeling and visualization environment. Procedia Computer Science,2017,108：2230-2239. [doi：10.1016/j.procs.2017.05.174]

6 Zou J,Chang Q,Arinez J,et al. Data-driven modeling and real-time distributed control for energy efficient manufacturing systems. Energy,2017,127：247-257. [doi：10.1016/j.energy.2017.03.123]

7 王樹西,李安渝. Dijkstra算法中的多鄰接點與多條最短路徑問題. 計算機科學,2014,41(6)：217-224. [doi：10.11896/j.issn.1002-137X.2014.06.043]

8 湯志貴. Dijkstra與Floyd在求最小環時其算法優劣比較.電腦知識與技術(學術交流),2007,(9)：709-711.

9 鮑培明. 距離尋優中Dijkstra算法的優化. 計算機研究與發展,2001,38(3)：307-311.

10 趙禮峰,梁娟. 最短路問題的Floyd改進算法. 計算機技術與發展,2014,24(8)：31-34.

11 Bostock M,Ogievetsky V,Heer J. D3：Data-driven documents. IEEE Transactions on Visualization and Computer Graphics. 2011. 2309.

12 Dailey D,Frost J,Strazzullo D. Building web applications with SVG. Sebastopol,California：Microsoft Press,2012.

13 黃冠華,楊鶴標. 基于D3.js的微博輿情分析可視化研究.軟件導刊,2016,15(6)：142-144.

14 陳鵬鵬. 移動互聯網下數據可視化技術及應用. 智能計算機與應用,2015,5(6)：38-41.

15 王子毅,張春海. 基于ECharts的數據可視化分析組件設計實現. 微型機與應用,2016,35(14)：46-48,51.

16 張運良,張兆鋒,張曉丹,等. 使用D3.js的知識組織系統Web動態交互可視化功能實現. 現代圖書情報技術,2013,29(7-8)：127-131.