Features
Download
Documentation
Install
Quick Start
Input Formats
User Manual
Theoretical Overview
Layouts
Forums and Lists
JavaDoc
Change History
Examples
News
Papers & Citations
Source Code
Links
Data Sources

Layout Algorithms

Network data is generally quite "high dimensional", meaning that it is difficult or impossible to create a two-dimensional representation in which all the distance relations among the nodes hold true. So various layout techniques make different trade-offs when squishing the networks down flat. And some seem to work better for movies

Current layout techniques

Because SoNIA is designed in a Java "Object-Oriented" fashion, additional algorithms can be "plugged in" fairly easily. The following algorithms are currently being tested, what follows is a short summary of what we have learned:

Kamada-Kawai (spring embedder / MDS)

To date, this layout gives by far the best performance for movies. KK takes the "slice" similarity matrix, converts it to dissimilarity, computes the all-pairs-shortest-paths (geodesic distances) and represents the network as a system of springs with a relaxed length proportional to edge length.  Nodes start from user-defined initial positions, and are iteratively repositioned to minimize the overall "energy" of the spring system using a steepest descent procedure.  If the network has a fairly low dimensionality, this should result in a layout where screen distances correspond to edge lengths.  (Subject to convergence on local minima) Although the KK procedure is a "spring-embedder", the procedure is analogous to some forms of non-metric MDS. 

KK movie example

Fructerman-Reingold (spring embedder)

Slice similarity matrix is converted to dissimilarity.  Network is represented as a system in which all nodes repel each other equally, but are attracted to the nodes to which they are connected, with a resting distance proportional to edge weight.  Starts from user-defined initial coordinates, and moves all nodes according to a vector sum of all the forces they "feel".  Layout is forced to converge by gradually decreasing the distance which nodes are allowed to move at each update according to the cooling schedule.

fr movie example

"rubber band" Fructerman-Reingold

Same as above, but attempts to minimize "spurious" motion by "rubberbanding" each node to its starting location (usually defined as its location in the previous layout).

fr rubber band movie example

Moody's Peer Influence

Similarity matrix is row-normalized and iteratively multiplied by the x and y coordinate vectors, resulting in positioning in which each node's position is the average of the nodes it is connected to (its "peers") weighted by the arc weights (their "influence") and include a value for self-weight.

PI movie example

Metric MDS (SVD)

Converts matrix to all-pairs-shortest-path dismilarities, computes the Singular Value Decomposition of the matrix, and positions nodes according to to the first two Eigenvectors (others can be chosen).  Small amounts of "noise" can be added to the matrix reduce node overlaps, as it generally results in a very "structural equivalence" picture of the network. 

MDS movie example

Original file coordinates

Displays nodes at the positions given in the input file.  (can be rescaled, etc)

Circular (static)

Yup, its a circle. Shows nodes arranged in a circle in the order they were parsed from the input file.