網(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é)點(diǎn)鏈接布局相鄰矩陣混合布局圖的簡化交互工具與應(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)，表達(dá)的關(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è)計(jì)搜索引擎的設(shè)計(jì)演員的協(xié)作關(guān)系分析科研人員的研究協(xié)作分析社交網(wǎng)絡(luò).Typhoid MaryAIDS Mary網(wǎng)絡(luò)的重要性質(zhì)關(guān)系的復(fù)雜性和層次數(shù)據(jù)相比，關(guān)系可以存在于任意兩個(gè)節(jié)點(diǎn)中關(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é)點(diǎn)的排布 視圖的視覺復(fù)雜度與網(wǎng)絡(luò)視圖的交互圖的顯示節(jié)點(diǎn)鏈接式顯示分層顯示/Sugiyama力導(dǎo)向布局多維尺度分析(Multi-Dimensional Scaling, MDS)布局相鄰矩陣基于屬性的顯示Sugiyama類顯示非常適用于顯示具有原生順序的樹圖的“深度”映射到某一坐標(biāo)軸上UNIX族譜Sugiyama處理步驟1創(chuàng)建圖的層次基于領(lǐng)域相關(guān)的知識(shí)與根節(jié)點(diǎn)的最長路徑利用算法確定最優(yōu)層次排列逐級(jí)最小化邊的交叉存在多種啟發(fā)式 (heu

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

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

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

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

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

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