網(wǎng)絡(luò)數(shù)據(jù)可視化-研討班zxl

1、網(wǎng)絡(luò)數(shù)據(jù)可視化提綱網(wǎng)絡(luò)關(guān)系數(shù)據(jù)網(wǎng)絡(luò)關(guān)系數(shù)據(jù)的可視化節(jié)點鏈接布局相鄰矩陣混合布局圖的簡化交互工具與應(yīng)用網(wǎng)絡(luò)關(guān)系數(shù)據(jù)網(wǎng)絡(luò)關(guān)系數(shù)據(jù)相較于樹型數(shù)據(jù)中明顯的層次結(jié)構(gòu)，網(wǎng)絡(luò)數(shù)據(jù)并不具有自底向上或自頂向下的層次結(jié)構(gòu)，表達的關(guān)系更加自由和復(fù)雜。社交網(wǎng)絡(luò)電話網(wǎng)絡(luò)郵件網(wǎng)絡(luò)合作網(wǎng)絡(luò)網(wǎng)絡(luò)類型數(shù)據(jù)由來已久網(wǎng)絡(luò)理論的應(yīng)用疾病傳播分析路由器網(wǎng)絡(luò)的設(shè)計搜索引擎的設(shè)計演員的協(xié)作關(guān)系分析科研人員的研究協(xié)作分析社交網(wǎng)絡(luò).Typhoid MaryAIDS Mary網(wǎng)絡(luò)的重要性質(zhì)關(guān)系的復(fù)雜性和層次數(shù)據(jù)相比，關(guān)系可以存在于任意兩個節(jié)點中關(guān)系可能具有方向性、權(quán)重關(guān)系的中心性(centrality)度(degree), 相近/整體(clos

2、eness), 中間(betweenness), 特征向量(eigenvector)網(wǎng)絡(luò)數(shù)據(jù)的可視化需要解決的問題網(wǎng)絡(luò)關(guān)系結(jié)構(gòu)的圖形化展示和層次數(shù)據(jù)相比更加復(fù)雜 節(jié)點的排布 視圖的視覺復(fù)雜度與網(wǎng)絡(luò)視圖的交互圖的顯示節(jié)點鏈接式顯示分層顯示/Sugiyama力導(dǎo)向布局多維尺度分析(Multi-Dimensional Scaling, MDS)布局相鄰矩陣基于屬性的顯示Sugiyama類顯示非常適用于顯示具有原生順序的樹圖的“深度”映射到某一坐標軸上UNIX族譜Sugiyama處理步驟1創(chuàng)建圖的層次基于領(lǐng)域相關(guān)的知識與根節(jié)點的最長路徑利用算法確定最優(yōu)層次排列逐級最小化邊的交叉存在多種啟發(fā)式 (heu

3、ristic)算法Sugiyama處理步驟2決定各節(jié)點的最終x坐標安排各條邊Sugiyama處理步驟3Sugiyama美觀、可讀性好、自然的自上而下排列相對快速（依賴于在最小化邊交叉時所采用的啟發(fā)式算法）不適用于顯示不具有原生自頂向下順序的圖基于力引導(dǎo)的算法沒有原生的順序，怎么辦？使用物理模型：邊=彈簧；節(jié)點=互斥質(zhì)點力引導(dǎo)布局用彈簧模型來描述兩個點之間的關(guān)系 過近的點會被彈開而過遠的點被拉近算法的本質(zhì)是能量優(yōu)化 彈簧模型 能量模型計算節(jié)點的實際位置從隨機生成的節(jié)點排列開始循環(huán)：為每一對節(jié)點計算排斥力為每一條邊計算引力將每個節(jié)點的各個力累加到一起沿著合力的方向更新各個節(jié)點的位置當節(jié)點的排列“足

4、夠好”時結(jié)束更新優(yōu)點非常靈活，對各種類型的圖都能生成較好的顯示效果相對容易實現(xiàn)有現(xiàn)成軟件包和算法可用局限與擴展局限性往往生成局部最優(yōu)解初始位置對結(jié)果影響很大迭代算法的復(fù)雜度在計算斥力的循環(huán)中，每次迭代的計算復(fù)雜度為O(N2) 擴展Barnes-Hut四叉樹分解，F(xiàn)ADE、GRIP、FMS、FM3、GVA力引導(dǎo)結(jié)果示例悲慘世界的人物圖譜 MDS彌補力引導(dǎo)布局的局限性用降維方法將數(shù)據(jù)從高維空間降到低維空間，力求保持數(shù)據(jù)之間的相對位置不變，同時也保持布局效果的美觀性MDS是一種全局控制基于距離的尺度分析Ulrik Brandes and Christian Pich. 2009. An Experi

5、mental Study on Distance-Based Graph Drawing全局布局和局部細節(jié)的平衡MDS的特點布局質(zhì)量好可擴展性好更適用于節(jié)點和關(guān)系比較多的數(shù)據(jù)集圖的其它節(jié)點鏈接顯示方式正交圖非常適用于顯示UML圖算法復(fù)雜環(huán)形排列強調(diào)環(huán)形的拓撲結(jié)構(gòu)在社交網(wǎng)絡(luò)圖中廣泛采用嵌套排列遞歸式地應(yīng)用圖排列算法適用于具有層次結(jié)構(gòu)的圖弧長鏈接圖弧長連接圖 悲慘世界的人物圖譜弧長鏈接圖 2011年年末歐債危機時各國之間錯綜復(fù)雜的借貸關(guān)系的可視化節(jié)點鏈接圖小結(jié)優(yōu)點比較直觀的反映網(wǎng)絡(luò)關(guān)系能夠表現(xiàn)圖的總體結(jié)構(gòu)、簇、路徑靈活，有許多變種局限性幾乎所有直觀算法的復(fù)雜度O(N2)對于密集（尤其是關(guān)系密集）的

6、圖不是很適用相鄰矩陣 的矩陣，代表N個節(jié)點，矩陣內(nèi)的位置(i, j)表達了第i個節(jié)點和第j個節(jié)點之間的關(guān)系相鄰矩陣 的矩陣，代表N個節(jié)點，矩陣內(nèi)的位置(i, j)表達了第i個節(jié)點和第j個節(jié)點之間的關(guān)系權(quán)重方向性相鄰矩陣 的矩陣，代表N個節(jié)點，矩陣內(nèi)的位置(i, j)表達了第i個節(jié)點和第j個節(jié)點之間的關(guān)系權(quán)重方向性相關(guān)算法排序：矩陣中各元素的順序路徑搜索：節(jié)點關(guān)系的跟蹤相鄰矩陣法的排序示例 矩陣模式和點鏈接模式相鄰矩陣路徑追蹤相鄰矩陣法小結(jié)完全規(guī)避邊的交叉，非常適用于密集的圖視覺伸縮性強能展示圖的模式可視化結(jié)果比較抽象難以跟蹤出路徑混合布局混合布局把網(wǎng)絡(luò)中小群體內(nèi)的關(guān)系用相鄰矩陣表示群體之間的關(guān)

7、系用點-線圖來表示其它布局GMapGMap是一種用平面代表實體，平面的連通代表實體的關(guān)系的一種“地圖”image courtesy of Emden Gansner, et al圖的簡化拓撲簡化減少數(shù)據(jù)量減少點聚類減少邊最小生成樹聚類可視化法M. Rosvall and C.T. Bergstrom. Maps of Random Walks on Complex Networks Reveal Community Structure拓撲簡化主要的問題 數(shù)據(jù)的丟失需要結(jié)合其他方法來提供全面的數(shù)據(jù) 如：縮放邊綁定邊綁定邊綁定主要的問題 可能會產(chǎn)生誤導(dǎo)信息交互交互視角相關(guān)的交互平移、縮放、旋轉(zhuǎn)圖元

8、素的交互選擇、高亮、刪除、移動圖結(jié)構(gòu)的交互（局部）重排序、重布局上下文+焦點展開與隱藏圖的細節(jié)：Roll-up & Drill-down魚眼來源于攝影，是一種極端的廣角鏡頭技術(shù)突出正前方物體的基礎(chǔ)上，力求照顧到視角所及的最大范圍 焦點與上下文兼顧魚眼可能會有問題： 圖形部件在顯示器上的非線性變換對點和邊的操控不同焦點視圖之間的切換社交網(wǎng)絡(luò)的交互不僅僅對點和邊的探索，還涉及到點和邊所包含的社會因素和社會行為工具與應(yīng)用UCINET / NetDraw能處理多種網(wǎng)絡(luò)數(shù)據(jù)靈活性高學(xué)術(shù)界用戶多個人用戶免費Sentinel Visualizer社交網(wǎng)絡(luò)分析軟件政府部門和企業(yè)的用戶較多 情報分析，案件分析等多種可視化工具不免費Pajek用于分析和展示大的網(wǎng)絡(luò)數(shù)據(jù)免費文檔比較齊全分析工具強大程序包Prefuse JAVAFlare ActionScript (Flash)yWork多平