1 Graphs and Networks 2 CS 7450 - Information Visualization October 23, 2013 John Stasko Topic Notes Review • Last time we looked at graph layout aesthetics and algorithms, as well as some example applications • Today we look at more recent InfoVis projects Fall 2013 CS 7450 22 Interaction • One of the key ways we move beyond graph layout to graph visualization (InfoVis) is interaction with the graph Fall 2013 3 CS 7450 MoireGraph • Uses radial layout not terribly unlike hyperbolic tree, but no hyperbolic geometry • Impose levels on graph by doing min span tree from some node • Put root at center, nodes at subsequent levels further out radially, with descreasing space for each • Interaction is key Jankun-Kelly & Ma InfoVis ‘03 Fall 2013 4 CS 74503 Sample Views Fall 2013 5 CS 7450 Layout Principles Decreasing exponential space for outer layers Spreading the “children” nodes Fall 2013 6 CS 74504 Navigation and interaction… Fall 2013 7 CS 7450 Navigation and interaction… Fall 2013 8 CS 74505 Navigation and interaction… Video Fall 2013 9 CS 7450 Focus of Graph • Particular node may be focus, often placed in center for circular layout • How does one build an interactive system that allows changes in focus?  Use animation  But intuition about changes not always right Fall 2013 10 CS 74506 Focus Change Animation Straight linear interpolation of focus changes not as appealing as changes along polar coordinates Yee, Fisher, Dhamija, Hearst InfoVis ‘01 Video Fall 2013 11 CS 7450 TreePlus • Don’t draw entire graph • Have a focus vertex, then incrementally expand and show connections (min span tree) from there • Interaction:  Single-click: show connections via highlight  Double-click: new focus vertex  Smooth animated change in focus • “Plant a seed and watch it grow” Fall 2013 CS 7450 12 Lee et al TVCG ‘067 TreePlus Fall 2013 CS 7450 13 Green – current selection Blue – vertices from current selection Red – vertices to current selection Video Jigsaw’s Graph View Don’t draw everything, but allow the viewer to interactively explore (expand & compress) the graph Stasko, Görg & Liu Information Visualization ‘08 Fall 2013 14 CS 74508 Recent Trends in GraphViz • Attributes of nodes influence geometric positioning  Not just some arbitrary layout • Utilize graph statistical analysis too • Largely driven by interest in social network analysis Fall 2013 15 CS 7450 PivotGraph • Cluster on common node attributes  Put all A’s together, all B’s together, … • “Roll up” nodes  Draw edge from A to B depending on how many edges from some A to some B • Position nodes into a grid based on attributes Wattenberg CHI ‘06 Fall 2013 16 CS 74509 Fall 2013 17 CS 7450 Fall 2013 18 CS 745010 Semantic Substrates • Group nodes into regions According to an attribute Categorical, ordinal, or binned numerical • In each region: Position nodes according to some other attribute(s) • Give users control of link visibility http://www.cs.umd.edu/hcil/nvss/ Shneiderman & Aris TVCG (InfoVis) ‘06 Fall 2013 19 CS 7450 Fall 2013 20 CS 745011 Video Fall 2013 21 CS 7450 Vizster • Visualize social networking sites like friendster, myspace, facebook • Implementation  Crawled 1.5 million members (Winter 2003)  Written in Java using the prefuse tookit (http://prefuse.sourceforge.net) • Oppose Shneiderman’s mantra. Instead: “Start with what you know, then grow.” Heer & boyd InfoVis ‘05 Fall 2013 22 CS 745012 Visualization Fall 2013 23 CS 7450 Combining Features Colors: Gender Halo: Search for “student” Highlight: Friends of selection Blobs: Communities Video Fall 2013 24 CS 745013 SocialAction • Combines graph structural analysis (ranking) with interactive visual exploration • Multiple coordinated views  Lists by ranking for analysis data  Basic force-directed layout for graph vis http://www.cs.umd.edu/hcil/socialaction/ Perer & Shneiderman TVCG (InfoVis) ‘06 Fall 2013 25 CS 7450 Fall 2013 26 CS 745014 Social Network Attributes • Bary center – total shortest path of a node to all other nodes • Betweenness centrality – how often a node appears on the shortest path between all other nodes • Closeness centrality – how close a node is compared to all other nodes • Cut-points – the subgraph becomes disconnected if the node is removed • Degree – number of connections for node • HITs – “hubs and authorities” measure • Power centrality – how linked a node is to rest of network Fall 2013 27 CS 7450 Attribute Ranking • Run these measures on all nodes and rank them • Sort the rankings and show in lists and scatterplots • Allow user to filter based on rankings • Can aggregate rankings for cohesive subgroups of nodes Fall 2013 28 CS 745015 Graph Visualization • Standard node-link • Node positions remain constant across different metric views to promote comprehension • Links can have types • Coherent subgroups can be aggregated (like in Vizster)  Uses Newman’s community identification algo Fall 2013 29 CS 7450 Users begin with an overview of the entire social network. On the left side, overview statistics that describe the overall structure are presented. On the right, the network is visualized using a force directed algorithm. Fall 2013 30 CS 745016 The gatekeepers are found using a statistical algorithm. Users filter out the unimportant nodes using a dynamic slider which simplifies the visualization while maintaining the node positions and structure of the network. Fall 2013 31 CS 7450 Labels are always given priority so users can understand what the data represents. When user selects a node, neighbors are highlighted and details appear on the left. In order to protect sensitive information, node labels have been anonymized except for those individuals publicly identified in the Zacarias Moussaoui trial. Video Fall 2013 32 CS 745017 Senate Voting Patterns Fall 2013 CS 7450 33 Video http://www.cs.umd.edu/hcil/socialaction/ Implementation • Jung  Network data structures and algorithms • Prefuse  Graph drawing • Piccolo  Scatterplot and Matrix views Fall 2013 34 CS 745018 Comments • One of my favorite recent InfoVis papers • Not too innovative on the vis technique side, but wonderful application and synthesis of useful capabilities • Actually, a very nice visual analytics