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], [FR193], [FR293], FW193, [FW293], [BE97], [S&F99], [ROB00], [OSB00], [NEW01],... 6

Karate Club 16 12 6 1970 W. W. Zachary, An information flow model for conflict and fission in small groups, J. Anthropological Research 33, 452-473 (1977). 18 14 20 15 22 29 9 32 33 8 7 3 13 0 2 1 30 19 31 28 27 5 4 21 17 10 11 26 23 25 24 7

Twitter Follower/Followee 8

Follows & Replies-to on Twitter: forward2012 in tweets (sep. 9-10, 2012) 9

Gephi NodeXL MS Excel gephi.org www.nodexlgraphgallery.org/ 10

Gephi NodeXL MS Excel gephi.org www.nodexlgraphgallery.org/ Visual analytics Exploratory data analysis 11

12

G = (V, E) V: E: 9 15 18 14 32 20 22 29 26 8 33 23 12 6 7 3 13 0 30 2 1 19 31 28 27 25 24 5 4 21 17 10 11 13

12 6 0: 1, 2, 3, 4, 5, 6, 7, 8,... 1: 0, 2, 3, 7,... 2: 0,1, 3, 7, 8, 9,... 3: 0, 1, 2, 7,... 9 8 15 18 14 32 20 33 22 29 7 3 13 0 30 2 1 19 31 28 27 5 4 21 17 10 11 4: 0, 6,... 26 23 25 24 5: 0, 6,... 6: 0, 4, 5,... 14

0: 1, 2, 3, 4, 5, 6, 7, 8,... 1: 0, 2, 3, 7,... 2: 0,1, 3, 7, 8, 9,... 3: 0, 1, 2, 7,... 4: 0, 6,... 5: 0, 6,...? 15 18 14 20 22 29 9 32 33 8 12 7 3 13 0 2 1 30 19 31 28 27 6 16 5 4 10 11 21 17 6: 0, 4, 5,... 26 23 25 24 15

16

17

18

: [Eades 1984], [FR 1991] : [KK 1989], [DH 1996] Distance scaling: [TKS 1980] (MDS): [BP 2007] 19

Eades (1984) G = (V, E) V e = (v 1, v 2 ) in V V. if e in E: else: repeat M: v in V: P. Eades: A heuristic for graph drawing. Congressus Numerantium (42), 1984. 20

Eades (1984) G = (V, E) V e = (v 1, v 2 ) in V V. if e in E: c 1 log(d/l) else: -c 2 /d 2 repeat M: v in V: 21

Fruchterman & Reingold (1991) G = (V, E) V e = (v 1, v 2 ) in V V. if e in E: d 2 /k else: -k 2 /d repeat M: v in V: T. M. Fruchterman & E. M. Reingold: Graph drawing by force-directed placement. Software Pract. Expre. (21), 1991. 22

Kamada & Kawai (1989) vs X Energy = ( p i p j l ij ) 2 (v 1,v 2 )2E Compute (p1, p 2,...) that minimize Energy Newton-Raphson T. Kamada & S. Kawai: An algorithm for drawing general undirected graphs. Inform Process Lett. (31), 1989. 23

Torgerson-Kruskal-Seery (1980) (MDS) MDS(D) (p1, p 2,...): p i P pi = q i: p i 2 q i J. B. Kruscal & J. B. Seery: Designing network diagrams. in proc. conf. Social graphics, 1980. 24

Hosobe (2012): (Eades, Kamada-Kawai, Fruchterman-Reingold) L- BFGS (a) L-BFGS/KK (b) L-BFGS/HC (c) L-BFGS/Eades (d) L-BFGS/FR H. Hosobe: Numerical optimization-based graph drawing revisited, PacificVis, 2012, IEEE. 25

26

KK, MDS: O( V 2 ) : O( V 3 ) << 27

28

29

6 < 6 6 30

Barnes-Hut : N graph layouts either in 2D or 3D. Implicit surfaces are u visually simplified representation of vertex clusters, and edge bundles are formed for the simplification of edges. ally, dedicated transition techniques are provided for co adaptive and adjustable views of graphs that range from stract to very detailed representations. Keywords: Graph visualization, level-of-detail, cluster implicit surfaces, edge bundles. Index Terms: I.3.6 [Methodology and Techniques]: I Techniques; H.5.2 [Information Interfaces and Presentat Interfaces; J. Barnes & P. Hut: A hierarchical O(N log N) force-calculation algorithm, Nature (324), 1986. O(N 2 ) O(N log N) Loack s LinLog: A. Noack: An energy model for visual graph clustering, in proc. GD03, 2004. Clustered Graph & LoD M. Balzer & O. Deussen: Level-of-Detail visualization of clustered graph layout, in proc. APVIS 2007. ( ) (Social Cosmo Browser) 31

Singed (D3.js/Google Chrome) Signed: Singed 32

Signedネットワークの素朴な可視化 33

構造をもったネットワークの可視化 34

Social Cosmo Browser K. Wakita & T. Tsurumi: Finding community structure in mega-scale social networking service, in proc. IADIS WWW/Internet, 2007. MDS 3D LoD : 28(2), 2011. 35

Social Cosmo Browser 36

Social Cosmo Browser (4min. for 88 LoD 622 3,350 ) MDS 3 (TKS ) 37

AGI3D: UI H. Hosobe: An extended high-dimensional method for interactive graph drawing, in proc. APVIS 2005. : 2012-HCI-164(6), 2012. 38

Graph CREST @ IBM 39

UI: LoD & 40 Social Cosmo Browser High Performance Gephi

Social Cosmo Browser AGI3D /GPGPU DB 41

Desktop Social Cosmo Browser 42

: UI HPC UI 43