1 2 3 A projection-based method for interactive 3D visualization of complex graphs Masanori Takami, 1 Hiroshi Hosobe 2 and Ken Wakita 3 Proposed is a new interaction technique to manipulate graph layouts presented on two- and higher-dimensional spaces. The work extends a highdimensional interactive graph visualization technique proposed by Hosobe, which deals with graph layouts presented on two-dimensional spaces. The proposed method first computes static graph layouts in high-dimensional space using multidimensional scaling, and then projects it on a low-dimensional space. Updating this projection according to user interaction, it enables the user to handle a graph layout in the low-dimensional space interactively. The report gives a theoretical foundation to interact with graph layouts and presents experimental results obtained with an early prototype system using three dimensions. 1 Department of Information Science, Tokyo Institute of Technology 2 National Institute of Informatics 3 /JST CREST Tokyo Institute of Technology/Japan Science and Technology Agency 1. 1)7)2) 3) 1 c 2012 Information Processing Society of Japan
2. Eades 1) Kamada-Kawai 7) Fruchterman 2) 6) ACE 8) HDE 9) Kruskal MDS 13) 11) Kruskal AGI Active Graph Interface 3) Kruskal 5) Kruskal 4) 3. Kruskal 3.1 Torgeson Kruskal Togerson 13) 11) Togerson n D = (d ij) Kruskal d ij i j D = (d ij ) A = (a ij ) a ij = 1 2 ( 1 n n d 2 ik + 1 n k=1 n d 2 kj 1 n 2 k=1 n k=1 l=1 n d 2 kl d 2 ij) A V V T AV = Λ = λ 1 0... 0 λ n Λ λ i A λ 1 λ 2... λ n λ i v i V = (v 1,..., v n) d λ 1 λ 2... λ d > 0 n d X = (x 1,..., x n ) T λ1 0 x 1 X =. = V Λ... 1/2 = (v 1,..., v n) 0 λd x n Λ 1/2 Λ n d X k x k = (x k1,..., x kd ) k d d = 2 (x k1, x k2 ) d D Togerson 1 0 10 6 Zachary Karate club 10) mixi 3) AT&T ug 166,ug 263,ug 380 0 2 c 2012 Information Processing Society of Japan
Table 1 1 Dimensions of high-dimensional layouts Karate club 34 78 22 mixi 158 680 97 ug 166 71 74 61 ug 263 141 162 125 ug 380 1104 3231 698 e 1, e 2 e 1, e 2 k x k k (w k1, w k2 ) (w k1, w k2) x k e 1, e 2 e 0 e 0 e 0 = f 0 / f 0, f 0 = x k w k1 e 1 w k2 e 2 3.2 k x k = (x k1,..., x kd ) e 1, e 2 A λ i e 1 = f 1 / f 1, e 2 = f 2 / f 2 f 1 = (λ δ 1, 0, λ δ 3, 0,...), f 2 = (0, λ δ 2, 0, λ δ 4,...) x k e 1, e 2 k (x k e 1, x k e 2 ) 1 f 1, f 2 δ δ λ 1 > λ 3 λ 2 > λ 4 δ 3.1 d 2 Kruskal δ δ = 1/2 1 f 0 = x k 2 wk1 2 w2 k2 e 0 e 1, e 2 (w k1, w k2 ) < x k (w k1, w k2) < x k e 0, e 1, e 2 e 1 e 2 a 10, a 11, a 12, a 20, a 21, a 22 e 0, e 1, e 2 e 1 = a 10e 0 + a 11e 1 + a 12e 2 e 2 = a 20 e 0 + b 21 e 1 + b 22 e 2 r b 1, b 2 r = b 1 e 1 + b 2 e 2 8 x k e 1 = w k1, x k e 2 = w k2 e 1 = 1, e 2 = 1, e 1 e 2 = 0, r = 1 r e 1 = r e 1, r e 2 = r e 2 3 c 2012 Information Processing Society of Japan
4. 3.2 Torgerson d H d L d L e 1,..., e dl e 1,..., e dl Torgerson A (d L 1) e i = f i / f i f i = (0,..., 0, λ }{{} i, 0,..., 0, λ }{{} i+dl, 0,..., 0,...) T }{{} i 1 d L 1 d L 1 e i = 1 i, j e i e j = 0 {e i} d L i=1 e i e i n d L P = (e 1,..., e dl ) k q H = (x k1,..., x kdl ) k q L q H P q L = q H P = (q H e 1,..., q H e dl ) P e 1,..., e dl q H e 1,..., e dl e 0 e 0 = f 0 / f 0, f 0 = q H d L j=1 x kj e j e 1,..., e dl e 0 d L + 1 (d L + 1) (d L 1) k q L = (w k1,..., w kdl ) q L = (w k1,..., w kd L ) P = (e 1,..., e dl ) P = (e 1,..., e d L ) q L q H P q L = q H P e 1,..., e d L (d L + 1) α ij e 0,..., e dl e i = d L j=0 α ije j (1 i d L) (d L + 1) (d L 1) r 1,..., r dl 1 (d L 1) β ij e 1,..., e dl r i = d L j=1 β ije j (1 i d L 1) (d L + 1) d L e 1,..., e d L, r 1,..., r dl 1 4 q H e j = w kj (1 j d L ) (1) e i e j = δ ij (1 i, j d L) (2) r i r j = δ ij (1 i, j d L 1) (3) r i e j = r i e j (1 i d L 1, 1 j d L ) (4) (1) q H 4 c 2012 Information Processing Society of Japan
(2) (3) δ ij {e i} d L i=1, {r j } d L 1 j=1 (4) {e i} d L i=1 d L (d L +1) {r j } d L 1 j=1 d L (d L 1) 2d 2 L (1) d L (2) (3) ( dl C 2 + d L ) ( dl 1C 2 + d L 1) d 2 V (4) d L(d L 1) (1) (4) d L + d 2 L + d L (d L 1) = 2d 2 L q L < q H q L < q H d L = 2 d L d L = 3 5. AGI3D Active Graph Interface 3D C Java Java C Java Native Interface JNI C Java C GNU GSL-1.15 GNU Science Library 2 Java API Java 3D-1.5.1 3 1 AGI3D Karate club x y 2 http://www.gnu.org/s/gsl/ 3 http://java3d.java.net/ 1 AGI3D Fig. 1 The prototype system AGI3D z GSL 0 12) 1 1 6. 1 Karate club 2 3 ug 166 ug 263 2 ( 2(a) (b)) ( 2(b) (c)) 2(c) (d) 3 3(a) (b) 3(b) (c) 3(c) (d) 5 c 2012 Information Processing Society of Japan
4 5 mixi ug 380 4(a) 5(a) mixi ug 380 5(b) 5(c),(d) 7. AGI3D drawing, proceedings of the Asia Pacific Symposium on Information Visualisation, Sydney, Australia, Australian Computer Society, Inc., pp.15 20 (2005). 5) Hosobe, H.: Analysis of a high-dimensional approach to interactive graph drawing, proceedings of the Asia Pacific Symposium on Visualisation, Sydney, Australia, IEEE, pp.93 96 (2007). 6) Hosobe, H.: Numerical optimization-based graph drawing revisited, to appear in proceedings of the 5th IEEE Pacific Visualization Symposium, Songdo, Korea, IEEE (2012). 7) Kamada, T. and Kawai, S.: An algorithm for drawing general undirected graphs, Information Processing Letters, Vol.31, No.1, pp.7 15 (1989). 8) Koren, Y., Carmel, L. and Harel, D.: ACE: A fast multiscale eigenvectors computation for drawing huge graphs, proceedings of the IEEE Symposium on Infomation Visualization, Boston, MA, USA, IEEE, pp.137 144 (2002). 9) Koren, Y. and Harel, D.: Graph drawing by high-dimensional embedding, proceedings of the 10th International Symposium on Graph Drawing, Lecture Notes in Computer Science, No.2528, Irvine, CA, USA, Springer, pp.207 219 (2002). 10) Vol.28, No.2, pp.206 216 (2011). 11) Kruskal, J. and Seery, J.: Designing network diagrams, proceedings of the First General Conference on Social Graphics, Leesburg, VA, USA, pp.22 50 (1978). 12) Powell, M. J.D.: A hybrid method for nonlinear equations, chapter6, pp.87 114, Gordon and Breach (1970). 13) :. (2006). 1) Eades, P.: A heuristic for graph drawing, Congressus numerantium, Vol.42, pp. 149 160 (1984). 2) Fruchterman, T. and Reingold, E.: Graph drawing by force-directed placement, Software: Practice and Experience, Vol.21, No.11, pp.1129 1164 (1991). 3) Hosobe, H.: A high-dimensional approach to interactive graph visualization, proceedings of the 19th Annual ACM Symposium on Applied Computing, Nicosia, Cyprus, ACM, pp.1253 1257 (2004). 4) Hosobe, H.: An extended high-dimensional method for interactive graph 6 c 2012 Information Processing Society of Japan
(a) (b) (a) (b) (c) (d) (c) (d) 2 ug 166 Fig. 2 Interactive layout of graph ug 166 3 ug 263 Fig. 3 Interactive layout of graph ug 263 7 c 2012 Information Processing Society of Japan
(a) (b) (a) (b) (c) (d) (c) (d) 4 mixi Fig. 4 Interactive layout of graph mixi 5 ug 380 Fig. 5 Interactive layout of graph ug 380 8 c 2012 Information Processing Society of Japan