Sunday, 23 September 2012

Organizing networks using their dense regions

Many systems in fields ranging from biology to sociology, to politics and finance can be represented as networks. For example, in protein interaction networks each node represents a protein and each link, connecting a pair of nodes, quantifies the strength of the interaction between those proteins. Similarly, in political voting networks nodes represent politicians and the edges connecting pairs of politicians represent the similarity of their legislative voting records. Despite the significant differences in the underlying systems, the common network representation enables researchers in different fields to ask questions that can be surprisingly similar. Given this, it would be useful to have a systematic method to highlight similarities in networks from different fields to identify problems that might be tackled using the same techniques. For example, if a biological network representing covariation in neural activity in different regions of the brain could be shown to be structurally similar to a financial network representing correlation of stock returns, certain analytical tools and models might be applicable to both problems.
A taxonomy of networks

In our paper, we tackle this problem by first developing a method to quantify the similarity of different networks based on their community structure. A community in a network, loosely put, is a set of nodes which are more connected to each other than they are to the rest of the network (like a group of friends who have the majority of the social interactions with each-other). We introduce the idea of “mesoscopic response functions” which are curves that summarize the community structure of each network at different scales and enable us to define a single number that quantifies the similarity of network pairs. Importantly, this approach allows us to compare networks with different numbers of nodes and different link densities. We then use this similarity measure to construct taxonomies of networks. From an historical perspective, classification of objects in this way has been central to the progress of science, as demonstrated by the periodic table of elements in chemistry and the phylogenetic tree of organisms in biology.

The taxonomies constructed using our approach are successful at grouping networks that are known to be similar. For example, political voting networks for the US Congress, UK House of Commons and United Nation are clustered together in the same group. Perhaps more importantly, the method also identifies networks that are not grouped with members of the same class and are therefore unusual in some way. For example, a Facebook network for Caltech is not grouped with the Facebook networks of other universities. We also used the technique to detect historically significant financial and political changes in temporal sequences of networks; we found the stock market network corresponding to the 1987 crash and the voting network corresponding to the American Civil War to stand out from their respective sequences of networks.

You can read the full story in our paper “Taxonomies of networks from community structure” in Physical Review E 86, 036104 (2012)  In the paper, we demonstrate the range of fields in which this approach can be usefully applied using a set of 746 networks and case studies that include US Congressional voting, Facebook friendship, fungal growth, United Nations voting, and stock market return correlation networks. Dan, JP and Nick

No comments:

Post a Comment