{"id":2896,"date":"2016-03-02T15:56:32","date_gmt":"2016-03-02T15:56:32","guid":{"rendered":"http:\/\/www.blopig.com\/blog\/?p=2896"},"modified":"2016-03-02T15:56:32","modified_gmt":"2016-03-02T15:56:32","slug":"network-comparison","status":"publish","type":"post","link":"https:\/\/www.blopig.com\/blog\/2016\/03\/network-comparison\/","title":{"rendered":"Network Comparison"},"content":{"rendered":"

Why network comparison?<\/strong><\/h3>\n

Many complex systems can be represented as networks, including friendships (e.g. Facebook), the World Wide Web trade relations and biological interactions. For a friendship network, for example, individuals are represented as nodes and an edge between two nodes represents a friendship. The study of networks has thus been a very active area of research in recent years, and, in particular, network comparison has become increasingly relevant. Network comparison, itself, has many wide-ranging applications, for example, comparing protein-protein interaction networks could lead to increased understanding of underlying biological processes. Network comparison can also be used to study the evolution of networks over time and for identifying sudden changes and shocks.<\/p>\n

\"net\"<\/a>

An example of a network.<\/p><\/div>\n

How do we compare networks?<\/strong><\/h5>\n

There are numerous methods that can be used to compare networks, including alignment methods, fitting existing models,
\nglobal properties such as density of the network, and comparisons based on local structure. As a very simple example, one could base comparisons on a single summary statistic such as the number of triangles in each network. If there was a significant difference between these counts (relative to the number of nodes in each network) then we would conclude that the networks are different; for example, one may be a social network in which triangles are common – “friends of friends are friends”. However, this a very crude approach and is often not helpful to the problem of determining whether the two networks are similar. Real-world networks can be very large, are often deeply inhomogeneous and have multitude of properties, which makes the problem of network comparison very challenging.<\/p>\n

A network comparison methodology: Netdis<\/h3>\n

Here, we describe a recently introduced network comparison methodology. At the heart of this methodology is a topology-based similarity measure between networks, Netdis [1]. The Netdis statistic assigns a value between 0 and 1 (close to 1 for very good matches between networks and close to 0 for similar networks) and, consequently, allows many networks to be compared simultaneously via their Netdis values.<\/p>\n

<\/h5>\n
The method<\/strong><\/h5>\n

Let us now describe how the Netdis statistic is obtained and used for comparison of the networks G and H with n and m nodes respectively.<\/p>\n

For a network G, pick a node i and obtain its two-step ego-network. That is, the network induced by collection of all nodes in G that are connected to i via a path containing at most two edges. By induced we mean that a edge is present in the two-step ego-network of i if and only if it is also present in the original network G. We then count the number of times that various subgraphs occur in the ego-network, which we denote by \"N_{w,i}(G)\" for subgraph w. For computational reasons, this is typically restricted to subgraphs on 5 or fewer nodes. This processes is repeated for all nodes in G, for fixed k=3,4,5.<\/p>\n

    \n
  1. Under an appropriately chosen null model, an expected value for the quantities \"N_{w,i}(G)\" is given, denoted by \"E_w^i(G)\". We omit some of these details here, but the idea is to centre the quantities \"N_{w,i}(G)\" to remove background noise from an individual networks.<\/li>\n
  2. Under an appropriately chosen null model, an expected value for the quantities \"N_{w,i}(G)\" is given, denoted by \"E_w^i(G)\". \u00a0We omit some of these details here, but the idea is to centre the quantities \"N_{w,i}(G)\" to remove background noise from an individual networks.<\/li>\n
  3. Calculate: \u00a0\"eq1\"<\/a><\/li>\n
  4. To compare networks G and H, define:\"eq2\"<\/a>where A(k) is the set of all subgraphs on k nodes and\"eq3\"<\/a>is a normalising constant that ensures that the statistic \"netD_2^S(k)\" \u00a0takes values between -1 and 1. \u00a0The corresponding Netdis statistic is:\u00a0\"eq4\"<\/a>\u00a0which now takes values in the interval between 0 and 1.<\/li>\n
  5. The pairwise Netdis values from the equation above are then used to\u00a0build a similarity matrix for all query networks. This can be done for any \"k, but for computational reasons, this typically needs to be limited to \"k\leq5\". Note that for \u00a0 \u00a0 k=3,4,5 we obtain three different distance matrices.<\/li>\n
  6. The performance of Netdis can be assessed by comparing the nearest neighbour \u00a0 \u00a0assignments of networks according to Netdis with a ‘ground truth’ or ‘reference’ clustering. A \u00a0network is said to have a correct nearest neighbour whenever its nearest neighbour according to Netdis is in the same cluster as the network itself. \u00a0The overall performance of \u00a0 Netdis on a given data set can then be quantified using the nearest neighbour score (NN), \u00a0 which for a given set of networks is defined to be the fraction of networks that are assigned\u00a0correct nearest neighbours by Netdis.<\/li>\n<\/ol>\n
    \"tree\"<\/a>

    The phylogenetic tree obtained by Netdis for protein interaction networks. The tree agrees with the currently accepted phylogeny between these species.<\/p><\/div>\n

    Why Netdis?<\/h5>\n

    The Netdis methodology has been shown to be effective at correctly clustering networks from a variety of data sets, including both model networks and real world networks, such Facebook. In particular, the methodology allowed for the correct phylogenetic tree for five species (human, yeast, fly, hpylori and ecoli) to be obtained from a Netdis comparison of their protein-protein interaction networks. Desirable properties of the Netdis methodology are the following:<\/p>\n

    \\item The statistic is based on counts of small subgraphs (for example triangles) in local neighbourhoods of nodes. By taking into account a variety of subgraphs, we capture the topology more effectively than by just considering a single summary statistic (such as number of triangles). Also, by considering local neighbourhoods, rather than global summaries, we can often deal more effectively with inhomogeneous graphs.<\/p>\n