Graph difference (tutorial)

From visone manual
Jump to navigation Jump to search

This tutorial shows, how the R console can be used to manipulate and compare graphs beyond the functionality that visone provides.

Scenario

We'll assume in the following, that you have two networks on the same set of nodes and want to find out which of their edges differ. An important precondition is, that there exist an identifying attribute that:

  • gives every node a value
  • has the same value for each node in both networks
  • has within one network a different value for every node.

This attribute will be used in the following to establish the relation between the two networks. For this tutorial we assume it is called nodeid and is of type text.

Creating the difference network

Select the tab containing your first network and open the R console. Give your network a name in the input field next to the send button and press "send". For this tutorial we'll assume that it is named g1.

Now the command ls() should list g1. ls() can always be used to list all objects in the current R environment.

Send your second network to the R console: select it in the main window, name it (g2 in this tutorial), and press "send". The command ls() should now show the two networks.

The idea of this tutorial is, to create the difference network by subtraction of the networks adjacency matrices. Therefore, it is first of all necessary, to get those in the correct node order. We'll achieve this by deriving a node order from the attribute identifying the nodes (nodeid).

The order of the nodes in g1 is derived by: order1<-sort(V(g1)$nodeid,index.return=T)$ix.

This command combines a number of things, let's visit them in detail:

  • V(g1) yields the nodes (vertices) of g1
  • V(g1)$nodeid then provides the list of nodeid attribute values for those nodes, i.e. gives a list of node ids in the order of the nodes in the graph
  • sort() does what it says, it sorts.
    • As first parameter we provide the list of values to sort (V(g1)$nodeid, the node ids).
    • Since we are not interested in the sorted list but in their order, we tell sort() to return this order with the parameter index.return=T.
    • Sort will then return a list with two fields x our sorted list and ix the indices of the original list in sorted order. Of those we only need the second and consequently store that in order1.

We do the same for the second network with order2<-sort(V(g2)$nodeid,index.return=T)$ix. The two lists order1 and order2 can now be used as ordering permution on the node sets of the two networks, i.e. they put the nodes of the two networks in the same order. As an example V(g1)$nodeid[order1] lists the node ids in the just established order and should be exactly the same as V(g2)$nodeid[order2], i.e. the node ids of the second network in correct order.

To get the adjacency matrix of a network we would use the command a1<-get.adjacency(g1). Here we want these matrices in our node order and thus reorder them accordingly by a1<-get.adjacency(g1)[order1,order1]. The "[order1,order1]"-part just reorders rows and columns of the matrix. Use the two commands a1<-get.adjacency(g1)[order1,order1] and a2<-get.adjacency(g2)[order2,order2] to create a1 and a2, the two adjacency matrices of your networks in correct node order.

The difference between those can then easily be derived as the entrywise matrix difference: diff<-a2-a1. diff is the matrix with entry -1 for an edge that was deleted, 1 for an added edge and 0 if the edge did not change.

Now we can create the network with only the changed edges: diffnetwork<-graph.adjacency(diff, weighted="change"). The function graph.adjacency() creates a graph from an adjacency matrix with an edge for every entry that does not equal zero. In that the parameter weighted="change" stores the corresponding values in an edge attribute with the name "change". Before we load that back into visone we want to reattach the node ids with: V(diffnetwork)$nodeid<-V(g1)$nodeid[order1]

Finally, you can select the newly created network "diffnetwork" in the combobox of the dialog (next to the "load network" button) and load it into visone using the "load network" button.

Visualizing the difference

Close the console and you should see your network of changed edges. Assuming, that your networks where undirected, every edge will be shown as to opposing, directed edges. Use the "transformation"-tab and the "links" and "merge" with the option "contrary directed" to merge those into undirected edges.

Back to the undirected graph we do know, which edges changed but not, what happened to them. Using the "change" attribute created in R we can easily visualize what happened:

  • Select the "visualization" tab.
  • Go to category "mapping", type "color" and property "link color".
  • As attribute choose "change" and method "color table".
  • Now you can select the color for -1, i.e. edges that were deleted and 1 (the added edges). For this example we will use red and blue.
  • Use the "visualize" button to apply your color setting and you should get a graph with a red edge for every edge that was present in the first network but not in the second and a blue edge for every edge that is present in the second, but not in the first.