Go to Google Home
Go
A data-code-compute resource for research and education in information visualization
InfoVis Home Learning Modules Software Databases Compute Resources References

Software > ABSURDIST Algorithm

Description | Pros and Cons | Applications | Details | Usage Hints | References | Acknowledgments


line
Description

ABSURDIST (Aligning Between Systems Using Relations Derived Inside Systems for Translation) is a computational algorithm that uses within-system relations to find between-system translations (Feng, Y, et. al, 2004, Goldstone, R., 2002). In addition to performing simple string match of node labels, this algorithm also uses network structure information to identify the overlap between two given networks.

Within a network, a node is treated as a concept. ABSURDIST derives semantic similarity information for different concepts embedded within each network. The algorithm uses these internal semantic structure by itself, or in combination with external information about similarities between concepts to establish mapping of concepts that exists within two given networks. It supports networks with multiple types of weighted or unweighted, directed or unidrected relations between concepts. The algorithm exploits graph sparsity to improve computational efficiency. Parameters for running the algorithm are optimized to achieve better mapping results, as well as improve noise tolerance, iteration speed, and scalability.

The algorithm consists of the following steps:

1.  Represent both source and target system as attributed graphs
2.  Initialize the correspondence matrix C, compute the external similarity matrix E
3.  Iterate through the following steps until a convergence threshold is reached
  3.1  Compute excitation matrix R(C)
  3.2  Compute inhibition matrix I(C)
  3.3  Compute the net input N from E, R, and I
  3.4  Apply the some damping function and learning rate on N and Update C with N.
  3.5  If the result converges, i.e., update to C is smaller than a threshold, go to step 4, otherwise, go back to step 3
4.  Generate final mapping from C according to user request (1-to-1 or 1-to-m)

More details on the algorithm are available in the papers (Feng, Y, et. al, 2004, Goldstone, R., 2002, 2005).


line
Pros & Cons

ABSURDIST is an inexact graph matching algorithm.

The advantages of the algorithm are:

  • It considers the graph attributes (e.g., edge weight) as variables to establish a concept based match between two network systems.
  • The algorithms supports flexible matching by aligning two graphs based on node labels alone, graph topology, or a combination of both.

The disadvantages of this algorithm are:

  • The algorithm only scales to about 100 nodes.
  • The quality of mapping greatly drops as the graph size increases ( size > 100 nodes)
  • The algorithm does not always produce an optimum match for isomorphic networks or sparse networks.

line
Applications

Though originally developed for conceptual system alignment, as a general graph matching algorithm, ABSURDIST could be used in many other applications:

  • Ontology mapping
  • Database schema matching
  • Analogical reasoning and similarity
In general, it can be used to map any systems that can be represented as graphs. As a sample application, we've developed an applet/application that allows users to input their conceptual systems, or generate random systems as they specify, and map the two systems, as well as visualize the mapping results.

line
Details

ABSURDIST II is implemented purely in Java. The most up-to-date version of ABSURDIST (version 2.2) is available for download.

The package includes both an applet version and an application version. The applet version lets users generate random systems with randomly introduced noise, specified by the user. The application version also lets users input the source and target systems from files in a specially designed text format.

Besides the major source code implementing the algorithm, the download zip file also includes packages for various tests which were used to produce the experimental results presented in our papers. Instructions for how to use the code are provided in the readme file included in the download package.

ABSURDIST (version 2.2) can be downloaded here

For more information, visit ABSURDIST homepage.


line
Usage Hints

Please read the readme file before using the package.

To compile

After downloading abs2.zip and unziping it,

1) Put the unziped files into a base directory, say abs2
2) Create a directory classes/ under abs2/
3) Type either "ant" or "make" command

abs2% mkdir classes
abs2% ant
abs2% make

To run

- As application

abs2% make runapplic

Upon execution of the above command, the absurdist interface that is used to upload the network files and find match between two networks opens.



In the above interface, the import button on the left and right hand side can be used to load the network files. Each concept in the two network is given a unique color. The 'Map Systems' button can be used to execute the ABSURDIST algorithm to identify the overlap between the two networks. 'External Similarity' slider can be used to customize the algorithm to perform match based on pure structure (slider pointer to left); based purely on node labels (slider pointer to right) or an equal combination of both (slider at 0.5). The results of the mapping can be exported using the Export button or File > Export Results option.

The program exports two output files: .map (node mapping information) and .cor (containing the correspondence matrix information).

ABSURDIST has its own input file format. The scripts below convert the pajek file to ABSURDIST format and vice-versa.

For example, the two network files in pajek format: network1 and network2 are coverted to a ABSURDIST input format by using p_pajekToABS.pl. Using the absurdist format generated files in ABSURDIST, a map of overlapping networks is identified. Using the export option, a .map file is obtained from the interface. Further a combination of original pajek files along with a .map file is used as input to p_ABSToPajek.pl to generate a pajek file containing information about the overlap between the two networks. A sample pajek visualization showsnetwork1 in green and network2 in orange. Matching nodes as identified by ABSURDIST are connected by black lines.


line
References

line
Acknowledgments

ABSURDIST II was implemented by Ying Feng, a PhD student at Computer Science Department, with the help of Dr. Vladimir Menkov, a previous PhD student at the CS deparment, under the supervision of Dr. Robert Goldstone at  Percepts and Concepts Laboratory at IU.

This research was partially supported by a grant from the Lockheed Martin Corporation.  We would like to thank Todd Hughes, Brian Rogosky, and Ben Ashpole for helpful comments.

The documentation was compiled by Ketan Mane, Ying Feng and Katy Börner.

line
Information Visualization Cyberinfrastructure @ SLIS, Indiana University
Last Modified March 10, 2005