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

Size: px

Start display at page:

Download "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"

あいねわしあし
5 years ago
Views:

1 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 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 = Λ = λ λ 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 Zachary Karate club 10) mixi 3) AT&T ug 166,ug 263,ug c 2012 Information Processing Society of Japan

3 Table 1 1 Dimensions of high-dimensional layouts Karate club mixi ug ug ug 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 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 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

5 (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 AGI3D Karate club x y AGI3D Fig. 1 The prototype system AGI3D z GSL 0 12) Karate club 2 3 ug 166 ug ( 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

6 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 (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 (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 (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 (2002). 10) Vol.28, No.2, pp (2011). 11) Kruskal, J. and Seery, J.: Designing network diagrams, proceedings of the First General Conference on Social Graphics, Leesburg, VA, USA, pp (1978). 12) Powell, M. J.D.: A hybrid method for nonlinear equations, chapter6, pp , Gordon and Breach (1970). 13) :. (2006). 1) Eades, P.: A heuristic for graph drawing, Congressus numerantium, Vol.42, pp (1984). 2) Fruchterman, T. and Reingold, E.: Graph drawing by force-directed placement, Software: Practice and Experience, Vol.21, No.11, pp (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 (2004). 4) Hosobe, H.: An extended high-dimensional method for interactive graph 6 c 2012 Information Processing Society of Japan

7 (a) (b) (a) (b) (c) (d) (c) (d) 2 ug 166 Fig. 2 Interactive layout of graph ug ug 263 Fig. 3 Interactive layout of graph ug c 2012 Information Processing Society of Japan

8 (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 c 2012 Information Processing Society of Japan

JST CREST: Graph CREST 2

JST CREST 2012.12.3, 18 1 JST CREST: Graph CREST 2 3 4 Deep South A. Davis (1941) 14 Events 18 Women 5 Deep South [DGG41], [HOM50], [P&C72], [BGR74], [BBA75], [BCH78], [DOR79], [BCH91], [FRE92], [E&B93],