 # 汪云海 面向美学原则和应用需求的大规模图布局与交互研究

#### 前端狗

2019/01/19 发布于 技术 分类

1. http://www. yunhaiwang.org/
2. Visualization Data
3. Why are we using Visualization? Tamara Munzner 2011: “Computer-based visualization systems provide visual representations of datasets intended to help people carry out some tasks more effectively”
4. Task-driven visualization design
6. Which one is better? Bad Good Task: class separation
8. Which one is better?
9. Which one is better is for visualizing trends, line chart or scatterplot?
10. Task-driven graph visualization
11. Graphs are everywhere! Social Networks  Gene Regulatory Graph The Internet  [Decourty 2008] Human Disease Network 11 [Barabasi 2007]
12. Graph Visualization Methods Adjacency Matrix 12 Arc Diagram Node-link Diagram
13. Graph Visualization Task and Aesthetic Criteria • Identify clusters • Find the set of nodes adjacent to a node. • Find the circles • Maximizing edge orthogonality • Minimizing edge crossing • Maximizing symmetry Clusters • …… [H. C. Purchase et al. 2002] 13 Directed Edges + all above Stress Model Layout Constrained Layout produced from our framework Circles Stars
14. Graph Visualization Software • Gephi – a Java open source software with user interface • GraphViz – an open source software
15. Force-Directed Layout • Imagining the nodes as physical particles that are initialized with random positions, but are gradually displaced under the effect of various forces, until they arrive at a final position.
16. What’s the Problem? It looks nice but is it doing anything useful? Typical complaint: Giant-Hairball Poor local minima
17. Another method: Stress model • Given a graph G(V,E) • Stress model: min S(X) = min ∑ wij( xi - xj - dij)2 i<j 17
18. An Example (b) dCA 2 1 3 =3 (a) (c) The energy dij is the minimization shortest path process [Kamada [Kamada et al. et1989] al. 1989] 18 xi - xj ≈ dCA = 3 (d)
19. How to handle these tasks? • Identify clusters • Find the set of nodes adjacent to a node. • Find the circles • Maximizing edge orthogonality • Minimizing edge crossing • Maximizing symmetry • …… [H. C. Purchase et al. 2002] 19
20. Core Idea Introducing edge vector in the “stress model” (reformulating stress majorization) to provide inherent (unified) support to general layout constraints. » Classical stress model: distance only: » We: distance + angle (i.e. vector) min S(X) = min ∑ wij( xi - xj - dij)2 i<j dCA = 3 dCA = 3 Stress model: scalar 20 Ours: vector
21. IEEE Transactions on Visualization and Computer Graphics (Proc. IEEE InfoVis 2017) 2 1
22. Stress Majorization [Gansner et al. 04] S(X) = ∑ wij dij 2 + ∑ wij xi - xj 2 - 2 ∑ wijdij xi - xj i<j i<j i<j S(X) ≤ ∑ wij dij 2 + ∑ wij xi - xj 2 -2∑ wijdij i<j 22 i<j i<j (xi - xj)T(zi - zj) zi - zj
23. Reformulation in Vector Form S(X) = ∑ wij dij 2 + ∑ wij xi - xj 2 - 2 ∑ wijdij xi - xj i<j i<j i<j (zi - zj) dij = dij (xi - xj)T(zi - zj) zi - zj S(X) ≤ ∑ wij dij 2 + ∑ wij xi - xj 2 -2∑ wijdij zi - zj i<j i<j i<j Edge vectors 23
24. Reformulation in Vector Form (xi - xj)T(zi - zj) (xiji - xj)Tdij S(X) ≤ ∑ wij dij 2 + ∑ wij xi - xj 2 -2∑ wij d zi - zj i<j i<j i<j = ∑ wij xi i<j Stress model: - xj - dij 2 (zi - zj) dij = dij zi - zj ∑ wij ( xi - xj - dij)2 i<j dCA = 3 Stress model: scalar dCA = 3 Ours: vector 24
25. Incorporating User Constraints • 25 Define d'ij — target edge vectors for constraints • d’ij distance constraints between node pairs • d’ij direction constraints between node pairs
26. User Constraints 1. Direct Constraint 2. Metrics-based Constraint 3. Shape-based Constraint 26
27. 1. Direct Constraint • Edge Length / Direction Constraint • Temporal Coherent Dynamic Graph Visualization Direction Constraint Layout at time t 27 (Unconstrained) Layout at time t+1 (Constrained) Layout at time t+1
28. 2. Metrics-based Constraint Minimizing Edge Cluster Non-overlap Crossings Constraint (Minimal Penetration Depth) Result Non-overlap Constraint 28 Minimizing Edge Crossings
29. 3. Shape-based Constraint Iterative Closest Point (ICP) fit ICP fit Reference shape ICP fitting Result Star Constraint 29 Reference shape Iterative Closest Result Point(ICP) fitting Circle Constraint
30. 3. Shape-based Constraint Symmetry axis fit Mirroring ICP fitting Symmetry Constraint 30
31. 3. Shape-based Constraint Symmetry axis Result Symmetry Constraint 31
32. Constraint-based Graph Exploration (a) Cluster non-overlap constraints + Circle constraints (b) star constraints Facebook4039 Graph 4039 nodes, 88234 edges 32 + Path constraints (c)
34. Structure-Aware Fisheye Views for Efficient Large Graph Exploration IEEE InfoVis 2018, IEEE TVCG 2019 Magnifying a node-link diagram (a) with 11 clusters around a user-specified location (indicated by the cursor) using different fisheye lenses: (b) graphical fisheye; (c) hyperbolic fisheye; and (d) our structure-aware fisheye, which aims to maintain the shapes of almost all clusters and to minimize their distortions, such as in (b,c)
35. Graph Becomes Very Large A given layout
36. How to explore regions of interest? Context lost Pan & Zoom Additional Space Overview + Detail Dwyer et al.  Preserving context in the given space Focus + Context Lamping et al. 
37. The State-of-the-art Fisheye Views Input Layout Graphical Fisheye Sarkar and Brown.  Hyperbolic Fisheye Lamping et al.  iSphere Du et al. 
38. Problems • Strong Distortion Input layout Existing fisheye result Input layout Existing(c) fisheye result • Readability Lost
39. Our Core Idea
40. Our Objective [Cohé et al. 2016] • Minimizing the distortion of the structure of a diagram • Improving the readability of nodes of interest • Maintaining a coherent layout during the interaction
41. Our Core Idea Ge o tr e m i is F c y he e Edge length Sa Input layout m es tr u ct ur e Edge direction
42. Comparison With the State-of-the-art (a) Input Layout (b) Graphical Fisheye (c) Hyperbolic Fisheye (d) Ours
43. Our Core Idea Ge o tr e m i is F c y he e Edge length Sa Input layout m es tr u ct ur e Edge direction
44. Input layout Graphical Fisheye Our framework + structure constraints
45. Our framework + structure constraints + shape structure constraints
46. + node non-overlapping constraints + maximizing edge crossing angle
48. - - - - Convex Focal Area - -
49. - - - - Convex Focal Area - -
51. Thanks! http://www. yunhaiwang.org/