Spectral affinity in protein networks

We develop a novel affinity measure for pairs of proteins in PPI networks, which uses personalized PageRank, a random walk based method used in context-sensitive search on the Web. Our measure of closeness, which we call PageRank Affinity, is proportional to the number of times the smaller-degree protein is visited in a random walk that restarts at the larger-degree protein. PageRank considers paths of all lengths in a network, therefore PageRank Affinity is a precise measure that is robust to noise in the data. PageRank Affinity is also provably related to cluster co-membership, making it a meaningful measure. In our experiments on protein networks we find that our measure is better at predicting co-complex membership and finding functionally related proteins than other commonly used measures of closeness. Moreover, our experiments indicate that PageRank Affinity is very resilient to noise in the network. In addition, based on our method we build a tool that quickly finds nodes closest to a queried protein in any protein network, and easily scales to much larger biological networks.We define a meaningful way to assess the closeness of two proteins in a PPI network, and show that our closeness measure is more biologically significant than other commonly used methods. We also develop a tool, accessible at http://xialab.bu.edu/resources/pnns webcite, that allows the user to quickly find nodes closest to a queried vertex in any protein network available from BioGRID or specified by the user.Networks are often used to represent a system where the nodes are a set of agents, and the edges are the relationships/interactions between those agents. We can then use the network topology to find out more about the nodes and the relationships between them. For example, we can find vertices central to the network, which is useful for biological [1,2] and social networks [3]. In addition, we can use the network topology to find communities, in the context of the Internet [4-6], and