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

#### 前端狗

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”
8. Which one is better?
9. Which one is better is for visualizing trends, line chart or scatterplot?
11. Graphs are everywhere! Social Networks  Gene Regulatory Graph The Internet  [Decourty 2008] Human Disease Network 11 [Barabasi 2007]
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
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:'>model: distance only: » We: distance + angle (i.e. vector) min S(X) = min ∑ wij( xi - xj - dij)2 imodel:'>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
23. Reformulation in Vector Form S(X) = ∑ wij dij 2 + ∑ wij xi - xj 2 - 2 ∑ wijdij xi - xj i
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 imodel:'>model: - xj - dij 2 (zi - zj) dij = dij zi - zj ∑ wij ( xi - xj - dij)2 imodel:'>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/