Introduction        Installation        Usage      NetMatch by Example     Download     Bugs Report     About

Introduction

NetMatch supports subgraph matching queries against a target network, previously loaded into the Cytoscape workspace. Approximate queries are special subgraphs that may contain: (a) nodes and edges labeled with a special wildcard symbol ?, which can match any single value of a user specified node or edge attribute; (b) approximate paths, which are paths of length <= n or >=n, where n is a positive integer, that can connect two nodes. NetMatch handles target and query graphs with multi-edges (more than one edge between two nodes), loops (edges starting and ending at the same node), and a list of attributes for each edge and node. The searching (matching) process is carried out by using the state space representation where a state is a partial mapping and a transition between two states corresponds to the addition of a new pair of matched graph nodes. The aim of the matching process is the determination of a mapping, which is a bijection, and consists of a set of node pairs covering all the query graph nodes. When a pair of nodes is added to the partial mapping, consistency conditions are checked. Such consistency rules allow the pruning of the search space, reducing significantly the computational cost of the matching process. Approximate query graphs are handled by first independently processing all maximal specified subparts and then joining in all possible ways the results of the subqueries. The joining process connects the subparts by all paths satisfying the approximate paths present in the query. NetMatch can be set to interpret labeled/unlabeled, directed/undirected networks. Users can express queries in NetMatch by (a) loading from an existing file, (b) importing from the Cytoscape workspace, (c) drawing using the NetMatch query drawing tool.

Installation

Several options are be available:

• Graph Properties:
  • Checkbox Labeled enables/disables nodes and edges labels usage (i.e. if the graph has labels and the checkbox is disables it  will be treated as an unlabeled graph)
  • Checkbox Directed enables/disables edges direction for both query and target network (i.e. if the graph is directed and the checkbox is disabled it will be treated as an undirected graph)

• Query properties:
  • In the box Query Properties it is possible to select a query and optionally its node and edge attributes (query and attributes are loaded from Cytoscape or the query drawing tool). Node and edge attributes are only searched if the Labeled mode is set. When an incomplete set of attributes are loaded, NetMatch considers the remaining nodes unlabeled. In particular, the option "Use node IDs as attributes"  uses the node IDs  as attributes

• Network properties:
  • Select a target network in the Network Properties box and its node and edge attributes (target and attributes are loaded from Cytoscape). When an incomplete set of attributes are loaded, NetMatch considers the remaining nodes unlabeled. In particular, the option "Use node IDs as attributes"  takes as node attributes the node IDs.

   

  • Network Node/Edge Attributes:

    • through these menus the user can select nodes/edges attributes to be used during the match. The attribute selected can be boolean, integer, floating point, string or list attribute.  In this last case the query attribute will searched into the list attribute.

     

    • If the item "List of Attributes" is selected a windows (see figure on the right) allowing to select the attributes will be prompted. The query attribute will be searched into this list of attribute.

• Options:
  When query, network and attributes are selected it is possible to start NetMatch. The possibilities are:
   
  • Acquire Data: When this button is pressed all open networks and their attributes are loaded in NetMatch, even if they are loaded in Cytoscape after NetMatch is started.
     
  • Go: Run the query.
     
  • Reset: Reset NetMatch interface. If there are networks loaded in Cytoscape, they are automatically loaded.

• The match number (numbered 1 to the number of query results, in no particular order).
• The list of the network node identifiers (as given in the corresponding .sif file).
• 2D graphical representation of that match.

Clicking on one such match, its nodes in the network (shown in the Cytoscape desktop) are selected (highlighted). If "Create a new child network" is checked and a match result is clicked then a new network containing the query is created and displayed in the Cytoscape window. The "Save" button stores information of query results in a text file. 

When more than 500 matches are found, it can be time consuming to display all results. In this case, NetMatch asks if the user wants to display all results, display only the text results or don’t show results (in order to refine the search).

Query Drawing

• Node or Edge attribute: Once "Edit Attribute..." is selected, it is possible to add the attribute label by enabling the Labeled radio button and specify the label. Notice that, the attribute label (nodes/edges) in the query can be boolean, integer, floating point, and string. NetMatch supports also relational attributes for nodes: > int_val/floating_point_val,  < int_val/floating_point_val, >= int_val/floating_point_val, <= int_val/floating_point_val.
  Notice that in current version of NetMatch  list attributes in the query cannot be defined. These will be defined in the next version of the software.

• Approximate path attribute: A Path attribute can be modified in the same way by clicking with the right mouse button. The path length must be greater equal or less than a specific value.

Using Wizard

The radio buttons (Directed/Undirected) enable/disable edges direction for both query and target network (i.e. if "Undirected" is selected target network and query will be treated as an undirected graphs)

NetMatch by Example