Dr. Deborah Whitfield

Mr. William Botzer

Mr. Eric McAlpine

Dr. David Dailey

Slippery Rock University

Mr. William Botzer

Mr. Eric McAlpine

Dr. David Dailey

Slippery Rock University

- Web sites represented as graphs
- Nodes are pages; Edges are links
- Visualizations of random traversals of a graph
- Visualization of actual users traversing a graph
- Use color to indicate the temperature of a node
- Width of edge increases as the amount of traversals increases
- Speed control
- Path where a particular user has been

- Grapher software used to generate graphs for rapid prototyping of web sites
- Random traversals of site generated visualized
- Grapher and Constructor use the same XML structure
- Constructor used to modify pages
- Software permits importing and exporting of graphs and updates
- User data traversals visualized
- Graph numbering technique (i.e., flavoring)
- Purpose of the research is to reduce user search time on a website

- Grapher was originally developed in 1987 ported to SVG in 2009
- GUI that permits graph building
- Written with HTML, Javascript, SVG, and PHP
- Features include:
- graph scaling
- graph compliment
- extrude (i.e., Multiply by K2)

- Purpose:
- Research the types of graphs that are easy to navigate
- Optimization of web site design for ease of navigation
- Used for testing mathematical hypotheses regarding graph navigability

Figure 1. A webpage |
Figure 2. A graph built in Grapher based on the website in Figure 1 |

Demonstration of graph creation

- Random traversals used as a proof of concept
- Visualization process
- Properties of graphs seen in random traversals
- Nodes with more edges are "hotter"
- Bridges and articulation points are visited more often

Figure 2. A graph built in Grapher based on the website in Figure 1 |

Demonstration of random traversal

- Developed by the SRU Virtual Gravity Group in 2013
- Creates a prototype of a website based on a graph structure
- Not intended to be a web
**page design**tool, rather a web**site layout**tool - Constructor used to determine ease of site navigation
- Graph nodes are displayed as web pages
- Graph edges are displayed as buttons ("doors") that link to other pages
- Each page's background color is the same as the color of the door that leads to it
- Constructor's options include:
- Selection of words on each page
- Selection of a numbering scheme for the pages
- Create a search game with one of two goals

Figure 3. A graph created through the Grapher utility |
Figure 4. A website created through Constructor using the exported XML from Grapher |

Demonstration of constructor

- Gravitational Traversals
- Turkey Search
- Gather the three turkeys placed within the graph
- Return each turkey to the starting node
- Site Traversal
- Visit every node within the site
- Return back to the starting node to finish

Figure 5. A graph created through the Grapher utility |
Figure 6. A website created through Constructor using the exported XML from Grapher |

- An assignment to each node of unique integers in the range 1 to N such that between any pair of nodes a shortest path may be found by a simple greedy algorithm that chooses the next node from among those neighbors which have gravity values closest to that of the destination node
- What it is (labelling nodes/pages)
- Why it works
- Why it is important (speedup)

Figure 7. A 16 node graph that is gravitationally flavored |
Figure 8. A 12 node graph that is not gravitationally flavored |

- Gravitationally flavored graphs have been shown to be faster to navigate
- Many graphs cannot be gravitationally flavored
- Many graphs have landmarks and vantage points
- Landmarks
- seen from anywhere
- flavoring of the graph can always flow (making the same greedy choices as gravity) to the landmark node using the shortest path
- a tall mountain on a flat plain: wherever you are on the plain the mountain can still be seen

- Vantage Point
- node that can find any other node on a graph using the shortest path to get to a destination
- In a graph if the current location is a vantage point then one can move to a destination using gravity and follows the shortest path

- Algorithms to flavor graphs gravitationally
- Experimentation with landmarks and vantage points
- Visualization of landmark and vantage point graphs