WalkAbout: Regional Connectivity Analysis Over Large Graphs
WalkAbout Installation Guide
This document include the instructions to install and use WalkAbout toolbox to infer regional view of a large graph. The WalkAbout code is implemented in C++. However, we have implemented a Python front end that can interactively communicate with the compiled C++ module. The python module is capable of displaying the dvr histogram. In addition, user can interactively chose the region's core borders. Based on the the identified cores by the Python module, graph is split into regions and the regional view of the graph is generated in GEXF which can be visualized by different graph visualization tools, e.g., Gephi.
The C++ component has the following dependencies:
- boost library
In order to complie the C++ compenet download the code from here, and untar.
$/cd [untar folder]/miles/slither/c
While the C++ competent can be be executed independently to compute the DVR values, and assign nodes to core regions, the grouping of nodes based on the DVR should be preformed out of band. We have included the Slither prototype which allows users to do this task interactively, but any one dimensional clustering approach can be used instead.Using the Slither front end
Open up a command line tool such as Terminal and navigate to the slither directory.
Run the following command:
In the window that appears:
- browse for the graph you wish to analyze (.tab format). NOTE: this program begins to run prohibitively slow when you use graphs with more than appx 2 million nodes. Future iterations the code will seek to stamp out those inefficiencies and improve performance.
- enter minimum and maximum walk length, as well as step between walks (e.g. min=5, max=25, step=10 will result in 3 graphs: walk lengths 5, 15, and 25).
- choose an identifier for this analysis (resulting files will use this prefix).
- click “Walk”.
Some of the following steps take a fair amount of time to execute. You can watch their progress in real time by looking at the command line window used to open the program.
After accumulating walk data and parsing those data files, the 3d visualizer will open. X-axis = degree/visit ratio, Y-axis = frequency, Z-axis = walk length. In the visualizer window:
- use the text boxes to adjust the minimum and maximum degree thresholds for displayed nodes.
- use the sliders to adjust the viewing angle.
- use File => Save Plot to save a .png image of the current view.
- when you’ve decided which histogram you'd like to single out for two-dimensional view, select that walk length from the drop-down box and click “Select walk length to view:”.
This will open the 2d visualizer. X-axis = degree/visit ratio, Y-axis = frequency. In this window:
- use the degree threshold boxes and image output as before.
- use the slider to increase or decrease number of bins.
- use the “Toggle view” button to alternate between histogram and scatter plot views.
To designate regions of nodes, click the histogram with your cursor. A regional border will be created at the x-coordinate of your click. To delete a regional border, click at the same spot of an existing border.
To omit a region from being output, or readmit a previously omitted region, use the Ignore/Un-ignore buttons on the right, next to the desired region (lettered left to right).
When your happy with your assigned regions, click Output Regions. The visualizers will close, and in the command line window you will see the program compute the data required for a regional view of the graph.
When the window says “Done!” you can either set parameters for a new analysis, show the regional view of your graph (NOTE: INCOMPLETE) or close the program and view your files.
The io directory contains the region information for the nodes in your most recently analyzed graph. The data directory contains the page rank data and regional view data from all of your analyzed graphs, prefixed with your chosen identifiers.
The src and c directories contain the program's source code. Do not alter these directories unless you need to modify the WalkAbout implementation.