PajekAnimator ReadMe Sept 3, 2001. _____________________________ |PajekAnimator 1.0 --------------------------------------- ------[Written by Skye Bender-deMoll skyebend@santafe.edu skyebend@bennington.edu http://student.bennington.edu/~skyebend PajekAnimator provides a crude way of animating the structural transitions between network layouts at different points in time. The intention is to assist the eye in discovering relationships by providing clear cues about node "movement" using sinusoidal interpolation of the coordinates of nodes at successive points in time. PajekAnimator is a hacked together chunk of Java code meant to be used as a utility /demonstration of concept in conjunction with the network visualization and analysis software, Pajek. Pajek is Windows-based freeware, written by Vladimir Batagelj and Andrej Mrvar,University of Ljubljana,Slovenia downloadable from: http://vlado.fmf.uni-lj.si/pub/networks/pajek/ SPECS PajekAimator was written in Java, and requires that a Java virtual machine is installed. (http://java.sun.com). It has only been tested on a Windows NT machine running Java 1.3, but should work with earlier version of Java as well. Launch PajekAnimator from the command line by navigating to the directory containing it and typing (case sensitive): PajekAnimator1.0.jar or by double clicking the PajekAnimator1.0.jar icon. INPUT FORMAT Reads networks from text files in Pajek's default *.net Arc/Edge list file format. Will not read Pajek Arclist/Edgelist format, or Pajek matrix format. Requires that if "*Arcs" and "*Edges" both exist in file, "*Arcs" must be before "*Edges" (Pajek's default). Requires that the networks which are to be interpolated have the same number of vertices. Network files must all be in the same directory, and they must all have the same name followed by a three digit number: "<###>.net" Example: myNetwork001.net myNetwork002.net myNetwork367.net Each file must have a unique number. Files are assembled from lowest number to highest, and are assumed to represent successive networks, although missing values are permitted. Names of nodes, and number of Arcs/Edges can change between networks, but the ordering of vertices in the file must remain consistent. PajekAnimator assumes that nodes at the same location in the file (same line number) are in fact the same node. (all Pajek defaults) NOTE: Unlike Pajek, UCINET, and PajekConverter, PajekAnimator CANNOT process spaces in node labels, even if they are surrounded by "". (Sorry, I was writing the code in a hurry) OUTPUT FORMAT Writes out a *.paj Pajek project file containing the set of original networks, with a user specifiable number of "interpolated" networks between each. The node and arc/ edge attributes for the interpolated networks between each pair of original networks will be the same as the values for the 2nd network. (In fact, the attributes are treated as one long string which is patched onto each line after the coordinates have been changed) The name of the first network will be its original name, all subsequent networks will be named: <###>i ex: "C:/NetworkData/myNetwork027i9" INSTRUCTIONS Construct network layouts in Pajek (see below) and save in *.net format with sequentially numbered file names. Launch PajekAnimator. Select the number of coordinates in the file (X and Y, or X,Y and Z). Enter the number of "frames" (interpolated networks) to generate between each pair of network files. Click the "Read Files.." button. A load file dialog should appear. Select the first (starting) *.net file in the sequence. A second load file dialog will appear. Select the last (ending) *.net file. PajekAnimator will try to locate all the files with the same name and file numbers between the starting and ending file numbers. The files will be parsed and loaded into memory. (As the code is fairly inefficient, this make take some time for large networks with lots of edges) When the parsing is finished, "Parsing successful" will be printed to the status window. Click "Make animated file" PajekAnimator will construct the interpolated networks, saving them out as temp files in order to conserve memory. When all the temp files have been created, a save file dialog will appear, prompting for the name of the *.paj file to save the collection of networks. The temp files will be deleted, and "Save Complete" printed to the status window. Load the *.paj file into Pajek for display. INTERPOLATION DETAILS For each successive pair series of networks {Nt, Nt+1,..., Nt+n}, PajekAnimator interpolates the X an Y (and Z) coordinates of each node i according to the following rough algorithm: nMax = number of networks kMax = number of interpolations per pair iMax = number of nodes in networks for n = 0, n = nMax, n++ k = 0, k = kMax, k++ for i = 0, i = iMax, i++ X(n,i,k) = X(n,i) + ((1-Cos(PI*k/kMax))/2)*(X(n+1,i)-X(n,i)) [same for Y] [same for z] end end end where X(n,i) is the node i's original coordinate (from Pajek layout) from network n, X(n+1,i) is the nodes coordinate in the next original layout, and X(n,i,k) is the node's new position (in the Kth interpolated network). In other words, the x and y coordinates are not interpolated linearly, because the rapid start and stop are hard to follow visually. The interpolation is done so that the distance in each of the interpolations is an (inverted) cosine fraction of the difference between the starting and ending positions. The cosine means that the nodes appear to "move" slowly at the beginning and endings of the transitions. (I'm sure other algorithms might be more effective...) To make things a little more complicated (and better visually) the networks are parsed backwards, so that when played in order, we first see Nt0, then Nt1 with Nt0's coordinates (this shows the creation /deletion of edges), then a series of interpolated networks resulting in Nt1 with its original coords, then Nt2 with Nt1's coords.... PLEASE NOTE: this algorithm should not be interpreted as performing any sort of structural evaluation or implementing any layout procedure. It is solely an animation technique to allow the eye to visually associate the locations and proximities of nodes in successive layouts. LAYOUT SUGGESTIONS This techniques seems to work best and is most informative when the layouts are very close in Hamming distance. That is, when the number of arc additions deletions between the layouts is fairly low. If the network is relatively unstructured, and there is a lot of change between layouts, the result is a bunch of nodes zipping around. If the animation is going to tell a "story" about changes in the network, it is important that the layouts from Pajek accurately represent the network structure. If the layout algorithms have not fully converged, nodes will change positions due to the "random" results of the algorithm rather than relational changes in the network. For this reason, Kamada-Kawai seems to give better results than Fruchmen-Reinghold. But the algorithms may not always converge on a stable layout before reaching Pajek's stopping conditions. For that reason, I often run the KK algorithm multiple times, until its application results in little or no change in the network. This often is not possible for large networks. If the networks have been produced from dynamic network data, I'd recommend using the smallest practical available scale of temporal data. If the layout is stabilized, the actual changes in the network may provide much better positioning information than the "fictional" animated motion. Another drawback to the KK algorithm is that it doesn't handle isolated nodes or disconnected components very well. One possibility is to remove the isolates in Pajek, but this must be done after the animation has been produced, as PajekAnimator is expecting the same number of nodes in the same order. Perhaps future versions will locate nodes by label, so the network size requirement can be relaxed. TIPS FOR CONSTRUTING TIME-BASED ANIMATIONS IN PAJEK CONSTRUCTING (we are not talking tried and true techniques here, this program is only three days old. Pleas let me know if you know how to do this more easily, or how to automate parts of it...) Import the *.net file for the time-based network. (either coded "by hand" or with PajekConverter) Choose Net/Transform/Generate in time, enter the starting and ending times, and the interval. Pajek will generate a series of networks representing the presence and absence of edges for the specific times. (Neither PajekConverter or PajekAnimator let you have nodes which appear or disappear, yet..) However, any layout algorithm applied to one of these networks will also change the coordinates of the nodes in all the other networks. Go to the first network. Choose either a random or circular starting position and optimize the layout using KK or FR (from here on I'm assuming KK). Make sure that the layout has in fact converged as well as possible. (check the Options/Interrupt settings in the draw window, repeat the layout several times, etc) Save the network to a file, with a name like "network001.net" Go to the second network. (it will now be displayed using the coords from the first network layout). Make sure that the Layout/Energy/Starting Positions option in the draw window is set to "Given xy". My theory is that even if the layout was not at a global minima, starting the 2nd layout from the coordinates of the first will help insure that the 2nd network will converge to a layout which is "close" (Euclidean dist.) to the first. Optimize the 2nd layout. Save it out as "network002.net" Repeat for all networks, and then quit Pajek. (fastest way to clear all) Construct the .paj file of interpolated networks using PajekAnimator. (see above) PLAYING BACK Start Pajek. Choose File/ProjectFile/Read to load the "networkAnimation.paj" file into Pajek. (the file WILL NOT appear if you click the load network icon) All of the networks will load in order. This make take some time if you are working with large networks. (This animation technique is NOT a very efficient use of disk space!) Go to the first network. Choose Draw. Make sure that Options/PreviousNext/Optimise Layout is set to "No", or you will undo all your hard work. Make sure Options/PreviousNext/Seconds to Wait is 0. You can now click through the frames one at a time using the "Next" button, or set Options/PreviousNext/MaxNumber to the number of networks you have loaded, and you can go through them all in a hurry, flip-book style. Or, set Max Number to the number of interpolated frames + 1, and you can step through the original networks one at a time with (hopefully) smoothly animated transitions. If the transitions are too jerky or nodes move to fast, try generating more interpolated frames. But keep in mind that each frame has the same file size as the original network! Large networks take much longer to draw to the screen, so you might actually want to add some delay if you have a very small network. OTHER USES The animation technique can be used in more ways than just to illustrate dynamic network changes. It is also helpful for displaying the relation between several alternate layouts / representations of the network. For ex. animating the construction of a Watts-Strogatts circular-substrate-rewire model on a circular layout, and than showing the transition to a more "natural" graph distance layout (KK). Or showing transition between geographic and network coordinates... DISCUSSION Like I said, this is a really simple crude program. It is quite wasteful to have to produce so many networks for the animation, each one takes up just as much space as the original. As the algorithm and idea are so simple, I think we should all (very politely) lean on Andrej and Vladimir to implement this in Pajek directly, as it would be much faster and easier...