4. Visualization of network data

https://gyazo.com/e7e351571f3971c23e1ffdf52d4a1b8a

https://gyazo.com/264f30ada7b304b0c9c3a506f61682f3

Tokyo version coming soon?

InfoGraphics example

https://gyazo.com/e36d82fc5783f74fb0080e659f9e5627

https://gyazo.com/6569fe450539f66aaff3f6cd424bf74c.png

Railroad in Taiwan

https://gyazo.com/373f5eb2e488c546858cdaca48520515.png

Network data

http://upload.wikimedia.org/wikipedia/commons/5/57/6n-graf.png

Kinds of network data

Directed graph

Including hierarchical structure

Undirected graph

http://gyazo.com/ad1de9de3d4be1125253e1336480a5a2.png

Perfect graph

https://gyazo.com/25af21cadfdbd46c9994e21dac385782.png

Visualization example of a complex graph

"Hairball" problem

http://gyazo.com/da0643aa81e47595e05b192da61240dd.png

https://gyazo.com/3cf23e216cb0c22a1be301ac7f38b4ae

Scrapbox network structure

https://gyazo.com/d9ecae834299285efc9bba3fc1b889c4

LSI layout

http://gyazo.com/270bc4656134809b354a3d709a01510e.png

https://gyazo.com/910b5da73c88eaa9f4b7ba23c59a2ee0

Beautiful Visualization

https://www.amazon.co.jp/dp/1449379869 http://gyazo.com/efc62e15710c46f8c5640b6148390db0.png

Long history of research

Graph Drawing conference

Annual graph drawing conference

http://gyazo.com/3965de9f4446cf0c49114d74669e1e05.png

http://gyazo.com/a7fd8a62265562359bbeec3c7f6df258.png

https://gyazo.com/6e55efcf2af06eac7157f6c4f00ff707

https://gyazo.com/fd26c4843744634fd38e4977a1b31e21

https://gyazo.com/8fc31dbb518fcd48982e7e34a07cbd72

https://gyazo.com/dc3885d1b7aa48fec610d30cf054e976

Examples of large network strcture

Directed graph

Web links, state machine, Twitter followers

Undirected graph

Friends network

Bipartite graph

Book-bookshelf, person-work

Bipartite graph

Links between two sets

http://gyazo.com/9d95e3571e8873a0d97c444ebf950ff8.png

Table representation of a graph

Group info on Facebook

Mr.A ⇔ Group X ⇔ Mr.B

A and B are connected via X

Info on hondana.org

Bookshelf A ⇔ Book ⇔ Bookshelf B

https://gyazo.com/d90cb6991ba0839c7c8c959c7f48414d.png

Bookshelf matrix

http://gyazo.com/e408bec06444bdf845db1817077709f9.png

Book-bookshelf network

http://gyazo.com/f5973af08f60e72f4b958e7aa98622d2.png

Person-event relation

http://gyazo.com/3c3aa973ceaf30174937c149eedf2dde.png

Person relation calculation via attendance information

http://gyazo.com/ae2652279a7a2075229767f575088a60.png

Voting informration of U.S. senetors

Lines between similar voters

http://gyazo.com/48ab0ee6b79784d72ab6eeed25edb5e7.png

Beautiful Visualization

https://www.amazon.co.jp/dp/1449379869 http://gyazo.com/efc62e15710c46f8c5640b6148390db0.png

Characteristics of network graph

Ususally non-planar

Tree structure is always planar

Planar graph

Graph with no edge overlap

All non-planar graphs include a special non-planar structure

Non-planar structure

http://gyazo.com/33734994f80132eada3bf2d4e7089627.png

Example of planar graph

Aesthetic layout of network data

Small number of edge cross

Small number of node overlaps

Exponential time required to calculate the best layout

Removing edge cross by simple operation

Swap two edges if crossed

http://gyazo.com/fcda231adb943e03c66e107b94ca2285.png

Layout of network data

Force-directed layout algorithm

Statistical method

Force-directed algorithm

Based on "spring model"

Various variations

e.g. Kamata-Kawai method

Survey papers on force-directed algorithm

Algorithm by Peter Eades

Spring push and pull

http://gyazo.com/7bf72f55fdad20a6bbfd3a712a93310b.png

Kamata-Kawai algorithm

Shortest path length => spring length

Gradually calculate layout

Spring-based attraction + electric-based repulsion

http://gyazo.com/6c7ae678108594823bcdee2bd7570260.png

% attractive force is analogous to the spring force and the repulsive force is analogous to the electrical force.

Kamata-kawai algorithm

https://s3-ap-northeast-1.amazonaws.com/masui.org/a/9/a9166c9b8e8850d5237edecc23e437b1.gif

Dr. Kamada

Former president of Access Co.

Developed "Compact HTML" for iMode (Japanese mobile phone)

Now a "startup booster"

http://gyazo.com/0a1130c0369c174553a5f8b5f886fafb.png

Yamada's system

Ignore distant elements

http://gyazo.com/b7aff995ab7a0b4d9720c609a3fa683a.png

Hierarchical division

http://gyazo.com/d86d7e0e16e7258b0ff9d5b626a7991b.png

http://gyazo.com/fa8f657c3d131d7514ba14e3b3cff85e.png

Constraint solvers

Including force-directed methods

Solve many constraints on spring length

Examples of layout constraints

http://gyazo.com/101b33ff7784c1fb76c678d719a1d9b2.png

Hosobe's algorithm

Solve various constraint solvers

Solve equations and inequalities

Video: Chorus (Hosobe)

https://s3-ap-northeast-1.amazonaws.com/masui.org/c/0/c0480753216e1124c4981a4656b40c79.mp4

ビデオ: Chorus (細部)

https://gyazo.com/1195203d4865c2d4b6c1506870aaa115.png

Video: AGI (Hosobe)

https://s3-ap-northeast-1.amazonaws.com/masui.org/a/3/a371db5c5508159ecbf148c8f66c6ffd.mp4

Stochastic layout methods

GA (Genetic algorithm)

SA (Simulated Annealing)

Genetic algorithm

Simulate the evolution on computers

Code the solution into gene-like string

Calculate better solutions by generations

Genetic algorithm

code:GA.txt

Randomly generate N data

while(true){

Calculate evaluation function for each data

Stochastically perform the following operations

Select two data and perform crossover

Select one data and perform mutation

Select one data and keep it

Use the new data for next generation

}

Genetic manipulations

Crossover

Mutation

One-point crossover

http://gyazo.com/fc41eca4275cac628ded90bc347ad1f5.png

Two-point crossover

http://gyazo.com/88c894a29d5c22e1b59b711ffe42ad5b.png

Random crossover

http://gyazo.com/77ea3c2cbc95253934ff55e49b5fab5a.png

Calculating layout values

http://gyazo.com/fb926b172e65f7010905eda402e2ae6f.png

Genetic operations

http://gyazo.com/fd6a0485f7ac715321aa86935bf25542.png

Application for LSI layout

http://gyazo.com/270bc4656134809b354a3d709a01510e.png

Problems of large network visualization

Data concentration

Difficult to control layout

Small change of the structure yields completely different layouts

Solutions

Interactive layout

Reduce the number of nodes/edges

Interactive layout

Give up fully-automatic layout

People partially lay out objects

Interactively change the layout

e.g. "Natto view"

Interactive layout

Users lay out objects while automatic layout

Interactive genetic algorithm

http://gyazo.com/8957332d0b32ca91bf2575fb663b1839.png

Reduce the number of objects

Ignore unimportant edges

Convert to tree structure by removing edges

Convert to tree structure

Other network visualizations

FisheyeView

Natto view

Kartoo

Musicplasma

Textarc

FisheyeView

Display only close/important nodes

Importance is calculated by DOI

Degree of Interest = A Priori Interest - Distance

Video: FisheyeViewGraph

https://s3-ap-northeast-1.amazonaws.com/masui.org/e/f/efcbebb183d6609aec5b5564f8579fae.mp4

https://gyazo.com/f228408d3c5daf4d76ef96b1633a40bb.png

VIVE

Searchh documents based on relations

http://gyazo.com/6b11c24d515294ea19b21d96f660a5d8.png

Natto view

Drag nodes like natto

http://gyazo.com/d731d9c83f2d087051062d1d9893c665.png

Display web sites and keywords like a chart

http://gyazo.com/e237efc0c3e88d03f00348a305866d33.png

Relations between musicians

http://gyazo.com/0c00cd4ab0195413838a5833fabdf1f0.png

Relation between words in 'Hamlet'

http://gyazo.com/b5e6d1d75a05e904a4cde4ffe5604a3a.png

http://gyazo.com/5b446276ede34af0610cb92f73e79e6e.png

Visualizing 'link spam'

http://gyazo.com/948f6cadcc08da8f4b051468fa42484b.png

Summary

Visualization of network data

Force-directed model and genetic algorithm is widely used

Various new visualization systems available on the Web

Task 1

Visualization of hierarchical data or network data

Use visualization software or draw by hand

Tools

Cytoscape

GraphVis

https://gyazo.com/b4175eac966ab5b7c3c8425378ef3fb4

https://gyazo.com/6d30760f8600bd3d23c9ba4ccf8cc61a

https://gyazo.com/a8ed0f42ca4bbc12efe72b74d3634d38

http://gyazo.com/b85ecf16d0d23bf6d9907e40a95ea5cc.png

https://gyazo.com/cf7161f3e0c1660e674137947ea0b4df

End