BACKGROUND
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  <cit>  and social networks  <cit> .
in addition, we can use the network topology to find communities, in the context of the internet  <cit> , and social and biological networks  <cit> .
it is also useful to consider relationships between pairs of vertices.
for an interacting pair, we can look at how essential this interaction is to the network  <cit> , and use this information for community detection  <cit> , or to find properties of these pairs  <cit> .
moreover, we can use the graph topology to evaluate the closeness of pairs of vertices, which can provide additional insight into the structure of the network.
in many networks most node pairs are not connected, but it is still meaningful to consider how nodes that are not directly connected relate to each other.
a lack of an interaction may be due to physical constraints on the nodes, such as an airport only being able to support service to so many other airports, or a person only being capable of knowing so many other people.
however, it may also simply be due to noise in the network, such as the extremely high false negative rate in protein networks  <cit> .
conversely, even among node pairs that are connected it is still meaningful to see which pairs are closer to each other.
for example, we may consider a pair of vertices in the same cluster in the graph to be closer than a pair that is not.
and once again, some connections may simply be due to noise.
the simplest notion of distance between two nodes in a network is the length of the shortest path between them.
however, this is an imprecise measure, especially for small-world graphs where the longest path between any two nodes is very short  <cit> .
as an extreme example, consider large social networks, where it is speculated that the longest distance between any two people is six  <cit> .
shortest path distances consider a single path in assessing the closeness of two nodes.
if we use a measure that takes all the paths in the network into account, we should be able to compute distances that are more meaningful.
here we consider the problem of assessing the closeness of two proteins in a protein-protein interaction  network.
there has been considerable work done in this area, where measures of interconnectedness between protein pairs have been used to find functionally similar proteins  <cit> .
different notions of interconnectedness have also been used to predict false negative interactions in protein networks  <cit> .
all of these measures consider the density of interactions in the immediate neighborhood of two proteins, and some also normalize by the number of interactions of each protein, or the number of interactions in the neighborhood expected by chance.
a problem that is related to computing the distance between two proteins is finding the closest neighbors of a set of proteins.
this is addressed in  <cit>  by generalizing pairwise notions of interconnectedness.
a similar problem is considered in the context of probabilistic ppi networks, where reachability  <cit>  and shortest path distance  <cit>   are used to recover protein complexes when only some of their proteins are known.
discovering protein complexes from protein network topology is itself a very well-studied problem, and is usually addressed by clustering  <cit> .
contribution
in this work we develop a novel method to evaluate the closeness of proteins in a ppi network.
we also create a tool that allows the user to quickly find nodes closest to a queried protein in any ppi network available from biogrid or specified by the user.
our measure of closeness uses personalized pagerank, which was introduced by  <cit> , and has been used for context-sensitive search on the web  <cit> .
we define the pagerank affinity of two proteins a and b to be the minimum of pr and pr, where pr is the amount of pagerank that a contributes to b in the ppi network, which is proportional to the number of times b is visited in a random walk on the network that restarts at a. we show that our closeness measure is more biologically meaningful than other commonly used methods in terms of predicting co-complex membership and correlation with functional distance.
moreover, we show that our method is very resilient to noise in the data.
we also provide intuition for why pagerank affinity is meaningful in protein networks by stating some properties of pagerank vectors.
methods
preliminaries
we model a protein interaction network as an undirected, unweighted graph where the nodes are the proteins, and two nodes are connected by an edge if the corresponding proteins are annotated as interacting with each other.
formally, a graph is given by a set of vertices v and a set of edges e. the degree of a node u ∈ v, denoted by d, is the number of edges adjacent to u. a graph is often represented by its adjacency matrix.
the adjacency matrix of a graph g =  is defined by
we can learn a lot about the structure of a graph by taking a random walk on it.
a random walk is a process where at each step we move from some node to one of its neighbors.
the transition probabilities are given by edge weights, so in the case of an unweighted network the probability of transitioning from u to any adjacent node is 1/d.
thus the transition probability matrix  is the normalized adjacency matrix where each row sums to one:
here the d matrix is the degree matrix, which is a diagonal matrix given by
in a random walk it is useful to consider a probability distribution vector p over all the nodes in the graph.
here p is a row vector, where p is the probability that we are at node u and Σu∈v p =  <dig>  because we transition between nodes with probabilities given by w, if pt is the probability distribution vector at time t, then pt+ <dig> = ptw.
pagerank
a pagerank vector prα  is the steady state probability distribution of a random walk with restart probability α. the starting vector s gives the probability distribution for where the walk transitions after restarting.
formally, prα  is the unique solution of the linear system
the pagerank vector with a uniform vector for s gives the global pagerank of each vertex.
pagerank with non-uniform starting vectors is known as personalized pagerank.
here we always use a starting vector that has all of its probability in one vertex, defined as follows:
prα  is thus the steady-state probability distribution of a walk that always returns to u at restart, and we will refer to it as the personalized pagerank vector of u. we will use prα   to denote the amount of probability that v has in prα , and use a shorthand of pr for this quantity, dropping the α in the subscript because in our computations it is always fixed.
as pointed out in  <cit> , v's global pagerank, denoted by pr, satisfies
thus pr can be thought of as the contribution that u makes to the pagerank of v.
pagerank affinity
for two vertices u and v we define their pagerank affinity to be the minimum of the pagerank that u contributes to v and v contributes to u:
this quantity can be computed by solving the pagerank equation for prα  and prα , and reporting the minimum of the two pagerank contributions.
the restart probability of the random walk  must be greater than  <dig> to ensure that prα  and prα  have unique solutions, and must be much smaller than  <dig> to prevent the random walk from returning too often to the starting vertex and being too local.
we set α to  <dig> , which is typical for computations of pagerank.
approximate pagerank affinity
we can also use approximate pagerank to compute closeness between nodes.
while it is possible to compute exact pagerank vectors for smaller graphs by solving the pagerank equation, it is computationally infeasible to do this for larger networks.
to calculate approximate pagerank, we use the approximatepr algorithm from  <cit> , which computes an ϵ-approximate pagerank vector for a random walk with restart probability α in time o().
an ϵ-approximate pagerank vector for prα , denoted by α, satisfies
for any subset of vertices s, where p  = Σv∈s p , and vol = Σv∈s d. in other words, the amount of error in the approximate pagerank vector for any subset of vertices is at most the product of ϵ and the sum of degrees of its nodes.
algorithm description
we develop an algorithm that approximates pagerank affinity, which uses approximatepr as a subroutine.
our approximatepraffinity algorithm takes a queried vertex v, approximation parameter ϵ, and integer k as input, and returns the k nodes closest to v in the graph.
the algorithm is outlined below.
algorithm  <dig> approximatepraffinity
= approximatepr
for each u do
=
end for
for each u do
=
end for
for each u do
affinity = min, )
end for
return the k vertices with highest affinity scores
we first compute an approximate personalized pagerank vector of v, denoted by , to approximate the amount of pagerank that v gives to each vertex u, denoted by .
we then use the observation that for undirected graphs
to approximate the pagerank contribution of each vertex in the graph to v. we then calculate the affinity to v of each vertex u as
and return the k nodes with highest affinity values.
equation  <dig> follows from the discussion of computing pagerank contributions in the time-reverse markov chain in  <cit> , and the fact that in an undirected graph the amount of probability that a vertex has in the stationary distribution of a random walk is proportional to its degree.
it follows from equation  <dig> that the amount of error in the probability that u has in the approximate personalized pagerank vector of v is at most ϵ·d:
we denote by pr-aff the exact pagerank affinity of u and v, and by  the approximate pagerank affinity computed by approximatepraffinity.
using equations  <dig> and  <dig> we can verify that the amount of error in the approximate pagerank affinity of vertices u and v is at most the product of ϵ and the larger of their degrees:
runtime analysis
the approximate pagerank vector computed by approximatepr has few non-zero entries.
this saves computation time because we do not need to consider vertices with  <dig> probability in the approximate pagerank vector .
let us call the support of probability distribution vector p, denoted by supp, the set of all vertices that have non-zero probability in p:
approximatepr computes an approximate pagerank vector with small support, which is useful for large graphs that have many vertices.
more specifically, the number of non-zero entries in the approximate pagerank vector is less than :
thus the exact runtime of approximatepraffinity is the time necessary to compute , which takes o(), plus the time necessary to compute the affinity to v of each vertex in supp), which is linear in the size of the support set, plus the time necessary to find the k vertices with largest affinity scores, which takes at most k·, giving a total runtime of o. moreover, if we treat α as a constant in this analysis , this expression simplifies to o().
properties of pagerank vectors
it is well-known that a pagerank vector can be expressed as a weighted average of random walk vectors  <cit> :
the swt term gives the probability distribution of the random walk after t steps.
equation  <dig> thus shows that in computing pagerank we consider paths of all lengths, with less weight given to longer paths based on the value of α.
another important property of pagerank vectors is that if u and v are in the same cluster, both pr and pr are likely to be high.
the quality of a cluster c is measured by proportion of outgoing edges, known as conductance, which we denote by Φ. a cluster of lower conductance is better because its nodes are more connected among themselves than they are with the other nodes in the graph.
it is proved in  <cit>  that for any set c, there is a subset of vertices c' ⊆ c, such that for any vertex u ∈ c', the personalized pagerank vector of u, denoted by prα, satisfies
in other words, pr = prα  is high on average if u and v are in the same good  cluster c and u ∈ c'.
moreover, the set c' is large, as the sum of degrees of its nodes, denoted by vol, satisfies vol ≥ vol/ <dig>
other measures of closeness
in our experiments on protein networks, we compare pagerank affinity and approximate pagerank affinity with several other measures of closeness, which are described below.
some of these measures assign an affinity score to each pair of vertices, while others simply order pairs by their closeness.
shortest path and shortest path multiplicity
the shortest path closeness of two vertices is the inverse of the length of the shortest path between them.
however, using the length of the shortest path does not allow for much granularity, so we also consider the multiplicity of the shortest path to break ties between pairs that are the same distance apart.
common neighbors
a very intuitive measure of closeness of two vertices is the number of neighbors that they share in the graph.
in our experiments, we notice that in addition to counting common neighbors, it also helps to take into account whether the two nodes are directly connected, by adding a small constant to their closeness score if this is the case.
partitioning
we also compare with another measure of closeness, motivated by efforts to partition ppi networks and determine overlap with known protein complexes.
it is observed that the densest clusters are often the ones that overlap most with known complexes  <cit> .
therefore, we partition the protein network, and score pairs of vertices that are in the same cluster by the edge density of the cluster.
to partition the network, we use metis  <cit> , a widely used algorithm that finds high-quality, balanced clusters in the graph.
once we partition the network, we consider protein pairs in denser clusters closer than pairs in less dense clusters, because pairs in denser clusters are more likely to be part of the same functional unit.
of course, this approach only allows us to consider a small fraction of the pairs, because we have no way to evaluate the closeness of two proteins assigned to different clusters.
cliques and k-cores
in addition to partitioning the graph and evaluating the edge density of each cluster, we can also search for dense components directly by enumerating maximum cliques and finding k-cores.
a k-core is a vertex-induced subgraph where the degree of each node is at least k  <cit> .
we then consider pairs that are part of a larger clique closer than pairs that are part of a smaller clique, and consider pairs that are part of an m-core closer than pairs that are part of an n-core if m >n.
however, once again, these measures allow us to evaluate the closeness of only a small number of pairs in the network.
commute time
another way to assess the closeness of two nodes using a random walk on the graph is to consider the inverse of the commute time between them.
the commute time between vertices u and v is the expected number of steps taken for a random walk from u to reach v and return, which is computed as described in  <cit> .
RESULTS
we develop a tool, which is accessible at http://xialab.bu.edu/resources/pnns, that quickly finds nodes closest to a queried protein in any protein-protein interaction  network available from biogrid.
our tool implements the approximatepraffinity algorithm described in methods, and returns a list of proteins sorted by their approximate pagerank affinity to the queried protein, along with the affinity scores .
the user can specify a protein network by selecting an organism and a set of interaction types.
in addition, one may upload a custom  network, which may be weighted.
our application is also available as a command-line executable.
to assess the meaning of our closeness measure in protein networks we use protein complex annotation from  <cit> , and functional distance data from  <cit> .
we consider these datasets "gold standard" measures of protein functional similarity because they are based on information that is manually curated.
a good measure of closeness in a protein-protein interaction network should be consistent with these data: we expect many of the closest nodes in the network to be in the same protein complex, and more generally have lower functional distances.
figure  <dig> displays one of the protein networks used in our study, with proteins annotated to be in the same complex labeled using the same color: we can see that a lot of the clusters in the network indeed contain proteins that belong to the same complex.
we evaluate the closeness of protein pairs in ppi networks from biogrid  <cit> , version  <dig> .
<dig>  biogrid is a repository that lists interacting protein pairs, and for each pair gives the experimental method used to detect the interaction.
we use three different networks in our study, which differ in the type of experiment used to detect the interactions.
one of the networks is formed from interactions detected by affinity capture-western experiments , and the other two are from affinity capture-ms , and two-hybrid experiments.
in each network, we use pagerank affinity and other measures described in methods to rank protein pairs by closeness, in order to determine which measures are more biologically significant.
to calculate the pagerank affinity of all pairs of nodes in a network, we compute a personalized pagerank vector of each vertex, and then calculate a pagerank affinity score for each pair from their personalized pagerank vectors, as described in methods.
in order to see if we get similar results with the quicker approximation method that our tool implements, in each network we also calculate the approximate pagerank affinity of protein pairs by running the approximatepraffinity algorithm from each vertex.
predicting co-complex membership
we first investigate which measure of closeness is best at predicting co-complex membership.
in every network, we compare how many co-complex pairs are in the top percentile of each closeness ranking.
we also calculate the number of co-complex pairs that we expect in each percentile by chance, to see how statistically significant the results are.
figure  <dig> displays the results of our computational experiment.
there are three panels: one for each ppi network that we study.
bars of different color are used to represent the results for the different closeness measures compared.
in each sub-figure the x-axis lists different percentiles of the closeness rankings, and the y-axis lists the fraction of the total number of co-complex pairs in the network contained in the top percentile of a particular ranking.
for example, there are  <dig> co-complex pairs among the proteins in the ac-western network.
when we examine the top 1% pairs with highest pagerank affinity in this ppi network, there are  <dig> co-complex pairs among them, which constitutes a  =  <dig>  fraction displayed in the figure.
from figure  <dig> we also see that few co-complex pairs are considered close using partitioning.
partitioning seeks out clusters that are balanced in size, which often hurts their quality.
pagerank affinity is also related to cluster co-membership , but considers whether two nodes are part of a local cluster rather than a cluster in a global partition of the graph.
the closeness of two nodes is then proportional to the quality of this local cluster, which does not depend on a partition of the entire network, which is less relevant.
therefore pagerank affinity is a more flexible measure that better reflects whether two nodes are part of some quality cluster in the network.
correlation with functional distance
in addition to using protein complex annotation, we also use functional distance data to see which measures of closeness are more biologically relevant.
to calculate functional distances, we use a measure based on go  biological process annotation.
the method of  <cit>  provides a very sensitive measure of functional distance because it considers all known functions of a pair of proteins in assigning them a score.
we first investigate whether there is any global correlation between the functional distances and any measure of closeness.
in each network we rank all protein pairs by functional distance, and compute correlation with the closeness ranking of each measure using the pearson correlation coefficient  <cit> .
however, we find that there is very little global correlation between functional distances and any measure of closeness.
this is not surprising because functional annotation and protein-protein interaction data are fundamentally very different.
therefore we perform a different analysis, where we simply average the functional distances of the protein pairs in the top k percent of each closeness ranking, for different values of k. in our calculations of functional distance we take the logarithm  of the functional distance score from  <cit> ; a lower value indicates a closer functional relationship.
we notice that for most closeness rankings the average functional distance is worse for protein pairs that are further away, as expected.
the results of our experiment are presented in figure  <dig>  once again, there are three panels, one for each protein network that we study, and bars of different color are used to represent the results for the different closeness measures compared.
in each sub-figure the x-axis lists different percentiles of the closeness rankings, and the y-axis displays the average functional distance of protein pairs in the top percentile of a particular ranking.
robustness to noise
a closeness measure is particularly useful if it tells us something about the true structure of the network in the presence of noise.
the interactions in ppi networks are not random: proteins function in modules, therefore we should be able to use the community structure of the network to identify true positive and true negative interactions, unless this structure is completely destroyed by noise.
as described in methods, our measure of closeness is provably related to cluster co-membership, therefore we expect it to be resilient to noise if the network has strong community structure.
to test this hypothesis, we conduct an experiment where we build a ppi network from the complex annotation in  <cit> , add noise to it by adding/removing edges, and then evaluate the closeness of true positive and true negative interactions in the noisy network using pagerank affinity.
to build the protein network we connect two proteins by an edge if they are annotated as co-complexed in  <cit> .
we only consider protein complexes of size ≥ <dig>  which results in a network with  <dig> nodes and  <dig> edges.
to evaluate the resilience of a closeness measure to noise, we use a metric that considers the closeness of nodes in the noisy network, and counts how often true positive interactions are closer than true negative interactions.
more specifically, let g =  be the true network and  =  be the modified  network.
we add noise to the network by randomly choosing r <dig> * |e| of the true positive interactions and removing them, and randomly choosing r <dig> * |e| of the true negative interactions and adding them.
we then consider node pairs p <dig> =  ∈ v × v and p <dig> =  ∈ v × v, such that one of them is connected in the true network and the other is not: either  ∈ e and  ∉ e or  ∉ e and  ∈ e. we call  concordant if the connected pair is closer in the noisy network than the disconnected pair, and discordant otherwise.
for a particular experiment, where we take the true network, add noise to it, and calculate the closeness of node pairs in the modified network, we use nc to denote the number of concordant pairs and nd to denote the number of discordant pairs.
we then calculate a robustness score for a similarity measure as  ∈ .
a score of  <dig> indicates that each true positive interaction is closer in the noisy network than each true negative interaction, and a score of - <dig> indicates that each true positive interaction is further in the noisy network than each true negative interaction.
this experiment provides insight into why our closeness measure is effective at identifying co-complex protein pairs in ppi networks.
the protein networks used in our study are similar to , the noisy network in our experiment: they are formed from a true set of protein-protein interactions given by the protein complexes, which is altered by noise due to the nature of the experiments used to detect the interactions.
still, the noisy network preserves some of the community structure, and many of the protein pairs that have high pagerank affinity are true interactions, which are the co-complex pairs.
with this in mind, we further investigate whether our measure can be used to detect false negative interactions in ppi data by examining non-interacting pairs with highest pagerank affinity in each protein network used in our study.
for each pair, we look for other evidence of interaction between the two proteins using complex annotation from  <cit> , and also examine whether the two proteins are annotated as interacting in biogrid using other experimental methods.
we find that for many of the disconnected  pairs with highest pagerank affinity there are other  sources of evidence of interaction between the two proteins.
the results are presented in additional files  <dig>   <dig>   <dig>  where we consider the  <dig> disconnected protein pairs with highest pagerank affinity in each network.
additional file  <dig> shows that when we examine the  <dig> disconnected pairs with highest pagerank affinity in the ac-western network, we find evidence that  <dig> of them are in fact interacting.
for the acms and two-hybrid networks we find  <dig> and  <dig> such pairs , respectively .
these numbers are all much higher than expected by chance .
discussion
defining pagerank affinity
to determine the closeness of proteins a and b in a ppi network, we compute two pagerank contributions c <dig> = pr and c <dig> = pr .
to better understand how to combine the two contributions into a single score, we consider different possibilities, and see which ones are more biologically relevant in terms of predicting co-complex membership and correlation with functional distance .
we first try combinations of the form
for different values of β. here β =  <dig> corresponds to taking the minimum of c <dig> and c <dig>  β = 1/ <dig> corresponds to taking the arithmetic mean, and β =  <dig> corresponds to taking the maximum of the two contributions.
in addition, we try combinations of the form of
for different values of β. here β =  <dig> corresponds to taking the minimum of the two contributions, β = 1/ <dig> corresponds to taking the geometric mean, and β =  <dig> to taking the maximum.
when we evaluate different ways of combining the two pagerank contributions we notice that taking the minimum of c <dig> and c <dig> better predicts co-complex membership in two out of the three networks.
moreover, using the minimum of the two contributions gives a measure that is more correlated with functional distance in all three networks.
the complete results of our experiments are presented in additional files  <dig> and  <dig>  additional file  <dig> displays the results of evaluating different ways of combining the two pagerank contributions using a weighted arithmetic mean, while additional file  <dig> displays the results of evaluating different ways of combining the two values using a weighted geometric mean.
there are  <dig> panels in each figure: the first three display a comparison in terms of predicting co-complex membership , and the next three display a comparison in terms of correlation with functional distance .
for the first three panels higher values are better because they indicate more co-complex pairs that are close, while for the next three panels lower values are better because they indicate that pairs that are close have low functional distances, and are thus more functionally related.
our experiments indicate that taking the minimum of pr and pr gives a more biologically meaningful measure of closeness.
furthermore, we know that in an undirected network pr = pr, where d denotes the degree of a. therefore using the minimum of the two contributions is equivalent to reporting pr if d ≥ d, and pr otherwise.
thus our measure of closeness considers a random walk on the protein network from the larger-degree protein to the smaller-degree protein, which is a sound approach because proteins with large degree are easily reachable from most other proteins in a random walk regardless of their identity.
advantages of pagerank affinity
as discussed in methods, node pairs that are part of the same cluster in a graph will likely have higher pagerank affinity.
this property makes it a very relevant measure for protein networks because we expect pairs of proteins in the same cluster to be more functionally related, and be more likely to be in the same protein complex.
therefore it is not surprising that pagerank affinity outperforms other measures of closeness in terms of correlation with functional distance and predicting co-complex membership.
in addition, pagerank affinity is a very precise measure of closeness, and is robust to noise in the data.
as discussed in methods, personalized pagerank takes into account all paths between two nodes in a graph , by considering an arbitrarily long random walk from the starting vertex.
this allows for more precision in assessing closeness, which is especially useful in protein networks, where most protein pairs are very close to each other in terms of shortest path distance.
moreover, considering all paths between two vertices makes pagerank affinity very robust to noise in the data, because a few extraneous or missing edges are less likely to make a big difference in evaluating the closeness of two nodes.
we also have experimental evidence to support this claim, as pagerank affinity performs very well in distinguishing between true positive and true negative interactions in our simulated noisy networks.
a tool to compute pagerank affinity
one of our goals is to use our closeness measure to develop a practical tool that can be used to quickly find proteins closest to a queried vertex in a ppi network.
we can compute the pagerank affinity of one vertex to all other vertices in the network by solving a single pagerank equation .
while it is possible to do this in real time for most protein networks formed from interactions listed in biogrid today, as the size of the data continues to grow this computation will become more challenging.
moreover, even right now some of the protein networks from biogrid  are already too big to compute pagerank affinity exactly in real time.
our approximation algorithm, on the other hand, allows us to easily manage the tradeoff between computation time and the quality of the produced output.
in our experiments we have shown that when we approximate pagerank affinity, the quality of the output does not decrease much.
our tool works quickly on datasets currently available in biogrid, and easily scales to much larger protein networks and other biological networks.
CONCLUSIONS
we develop a method to evaluate the closeness of two proteins in a ppi network, and show that it is biologically meaningful in terms of predicting co-complex membership and correlation with functional distance.
moreover, we create a tool that can be used to quickly find nodes closest to a queried vertex in any protein network available from biogrid or specified by the user.
authors' contributions
kv, sht, and yx conceived and designed the experiments.
kv performed the experiments and analyzed the data.
kv, sht, and yx drafted and edited the manuscript.
all authors read and approved the final manuscript.
supplementary material
additional file 1
predicted false negative interactions in the ac-western network.
the table lists disconnected node pairs with highest pagerank affinity in the ac-western network, along with evidence for the existence of each interaction.
each row specifies a pair of proteins and the rank of their pagerank affinity score .
for each pair we list evidence of the existence of this interaction in the evidence of interaction column by writing co-complexed if the two proteins are annotated as co-complexed in  <cit> , and writing ac-western, ac-ms, two-hybrid, and other if the pair is listed as interacting in biogrid using affinity capture-western, affinity capture-ms, two-hybrid, or any other type of experiment.
click here for file
additional file 2
predicted false negative interactions in the ac-ms network.
the table lists disconnected node pairs with highest pagerank affinity in the ac-ms network, along with evidence for the existence of each interaction.
each row specifies a pair of proteins and the rank of their pagerank affinity score .
for each pair we list evidence of the existence of this interaction in the evidence of interaction column by writing co-complexed if the two proteins are annotated as co-complexed in  <cit> , and writing ac-western, ac-ms, two-hybrid, and other if the pair is listed as interacting in biogrid using affinity capture-western, affinity capture-ms, two-hybrid, or any other type of experiment.
click here for file
additional file 3
predicted false negative interactions in the two-hybrid network.
the table lists disconnected node pairs with highest pagerank affinity in the two-hybrid network, along with evidence for the existence of each interaction.
each row specifies a pair of proteins and the rank of their pagerank affinity score .
for each pair we list evidence of the existence of this interaction in the evidence of interaction column by writing co-complexed if the two proteins are annotated as co-complexed in  <cit> , and writing ac-western, ac-ms, two-hybrid, and other if the pair is listed as interacting in biogrid using affinity capture-western, affinity capture-ms, two-hybrid, or any other type of experiment.
click here for file
additional file 4
evaluating different ways of defining pagerank affinity by using a weighted arithmetic mean to combine the two pagerank contributions.
we evaluate different ways of combining c <dig> = pr and c <dig> = pr using a weighted arithmetic mean: β·max + ·min.
each value of β gives a distinct closeness measure , which is evaluated in terms of predicting co-complex membership , and correlation with functional distance  in the three networks that we study.
panels - display the number of co-complex pairs  among pairs in the top percentile of each closeness ranking in the ac-western , ac-ms , and two-hybrid  networks.
higher values indicate measures that are more biologically meaningful.
panels - display the average functional distance of pairs in the top percentile of each closeness ranking in the ac-western , ac-ms , and two-hybrid  networks.
lower values indicate measures that are more biologically meaningful.
click here for file
additional file 5
evaluating different ways of defining pagerank affinity by using a weighted geometric mean to combine the two pagerank contributions.
we evaluate different ways of combining c <dig> = pr and c <dig> = pr using a weighted geometric mean: maxβ·min1-β.
each value of β gives a distinct closeness measure , which is evaluated in terms of predicting co-complex membership , and correlation with functional distance  in the three networks that we study.
panels - display the number of co-complex pairs  among pairs in the top percentile of each closeness ranking in the ac-western , ac-ms , and two-hybrid  networks.
higher values indicates measures that are more biologically meaningful.
panels - display the average functional distance of pairs in the top percentile of each closeness ranking in the ac-western , ac-ms , and two-hybrid  networks.
lower values indicate measures that are more biologically meaningful.
click here for file
acknowledgements
konstantin voevodski is supported by an igert fellowship through nsf grant dge- <dig> awarded to the aces training program at bu center for computational science.
yu xia is supported by a research starter grant in informatics from the phrma foundation.
shang-hua teng is supported in part by nsf grant ccr- <dig>

 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 and social networks. in addition, we can use the network topology to find communities, in the context of the internet, and social and biological networks. it is also useful to consider relationships between pairs of vertices. for an interacting pair, we can look at how essential this interaction is to the network, and use this information for community detection, or to find properties of these pairs. moreover, we can use the graph topology to evaluate the closeness of pairs of vertices, which can provide additional insight into the structure of the network. in many networks most node pairs are not connected, but it is still meaningful to consider how nodes that are not directly connected relate to each other. a lack of an interaction may be due to physical constraints on the nodes, such as an airport only being able to support service to so many other airports, or a person only being capable of knowing so many other people. however, it may also simply be due to noise in the network, such as the extremely high false negative rate in protein networks. conversely, even among node pairs that are connected it is still meaningful to see which pairs are closer to each other. for example, we may consider a pair of vertices in the same cluster in the graph to be closer than a pair that is not. and once again, some connections may simply be due to noise. the simplest notion of distance between two nodes in a network is the length of the shortest path between them. however, this is an imprecise measure, especially for small-world graphs where the longest path between any two nodes is very short. as an extreme example, consider large social networks, where it is speculated that the longest distance between any two people is six. shortest path distances consider a single path in assessing the closeness of two nodes. if we use a measure that takes all the paths in the network into account, we should be able to compute distances that are more meaningful. here we consider the problem of assessing the closeness of two proteins in a protein-protein interaction network. there has been considerable work done in this area, where measures of interconnectedness between protein pairs have been used to find functionally similar proteins. different notions of interconnectedness have also been used to predict false negative interactions in protein networks. all of these measures consider the density of interactions in the immediate neighborhood of two proteins, and some also normalize by the number of interactions of each protein, or the number of interactions in the neighborhood expected by chance. a problem that is related to computing the distance between two proteins is finding the closest neighbors of a set of proteins. this is addressed in by generalizing pairwise notions of interconnectedness. a similar problem is considered in the context of probabilistic ppi networks, where reachability and shortest path distance are used to recover protein complexes when only some of their proteins are known. discovering protein complexes from protein network topology is itself a very well-studied problem, and is usually addressed by clustering. contribution in this work we develop a novel method to evaluate the closeness of proteins in a ppi network. we also create a tool that allows the user to quickly find nodes closest to a queried protein in any ppi network available from biogrid or specified by the user. our measure of closeness uses personalized pagerank, which was introduced by, and has been used for context-sensitive search on the web. we define the pagerank affinity of two proteins a and b to be the minimum of pr and pr, where pr is the amount of pagerank that a contributes to b in the ppi network, which is proportional to the number of times b is visited in a random walk on the network that restarts at a. we show that our closeness measure is more biologically meaningful than other commonly used methods in terms of predicting co-complex membership and correlation with functional distance. moreover, we show that our method is very resilient to noise in the data. we also provide intuition for why pagerank affinity is meaningful in protein networks by stating some properties of pagerank vectors. methods preliminaries we model a protein interaction network as an undirected, unweighted graph where the nodes are the proteins, and two nodes are connected by an edge if the corresponding proteins are annotated as interacting with each other. formally, a graph is given by a set of vertices v and a set of edges e. the degree of a node u ∈ v, denoted by d, is the number of edges adjacent to u. a graph is often represented by its adjacency matrix. the adjacency matrix of a graph g = is defined by we can learn a lot about the structure of a graph by taking a random walk on it. a random walk is a process where at each step we move from some node to one of its neighbors. the transition probabilities are given by edge weights, so in the case of an unweighted network the probability of transitioning from u to any adjacent node is 1/d. thus the transition probability matrix is the normalized adjacency matrix where each row sums to one: here the d matrix is the degree matrix, which is a diagonal matrix given by in a random walk it is useful to consider a probability distribution vector p over all the nodes in the graph. here p is a row vector, where p is the probability that we are at node u and Σu∈v p = because we transition between nodes with probabilities given by w, if pt is the probability distribution vector at time t, then pt+ = ptw. pagerank a pagerank vector prα is the steady state probability distribution of a random walk with restart probability α. the starting vector s gives the probability distribution for where the walk transitions after restarting. formally, prα is the unique solution of the linear system the pagerank vector with a uniform vector for s gives the global pagerank of each vertex. pagerank with non-uniform starting vectors is known as personalized pagerank. here we always use a starting vector that has all of its probability in one vertex, defined as follows: prα is thus the steady-state probability distribution of a walk that always returns to u at restart, and we will refer to it as the personalized pagerank vector of u. we will use prα to denote the amount of probability that v has in prα, and use a shorthand of pr for this quantity, dropping the α in the subscript because in our computations it is always fixed. as pointed out in, v's global pagerank, denoted by pr, satisfies thus pr can be thought of as the contribution that u makes to the pagerank of v. pagerank affinity for two vertices u and v we define their pagerank affinity to be the minimum of the pagerank that u contributes to v and v contributes to u: this quantity can be computed by solving the pagerank equation for prα and prα, and reporting the minimum of the two pagerank contributions. the restart probability of the random walk must be greater than to ensure that prα and prα have unique solutions, and must be much smaller than to prevent the random walk from returning too often to the starting vertex and being too local. we set α to, which is typical for computations of pagerank. approximate pagerank affinity we can also use approximate pagerank to compute closeness between nodes. while it is possible to compute exact pagerank vectors for smaller graphs by solving the pagerank equation, it is computationally infeasible to do this for larger networks. to calculate approximate pagerank, we use the approximatepr algorithm from, which computes an ϵ-approximate pagerank vector for a random walk with restart probability α in time o(). an ϵ-approximate pagerank vector for prα, denoted by α, satisfies for any subset of vertices s, where p = Σv∈s p, and vol = Σv∈s d. in other words, the amount of error in the approximate pagerank vector for any subset of vertices is at most the product of ϵ and the sum of degrees of its nodes. algorithm description we develop an algorithm that approximates pagerank affinity, which uses approximatepr as a subroutine. our approximatepraffinity algorithm takes a queried vertex v, approximation parameter ϵ, and integer k as input, and returns the k nodes closest to v in the graph. the algorithm is outlined below. algorithm approximatepraffinity     = approximatepr    for each u do        =    end for    for each u do        =    end for    for each u do       affinity = min, )    end for    return the k vertices with highest affinity scores we first compute an approximate personalized pagerank vector of v, denoted by, to approximate the amount of pagerank that v gives to each vertex u, denoted by. we then use the observation that for undirected graphs to approximate the pagerank contribution of each vertex in the graph to v. we then calculate the affinity to v of each vertex u as and return the k nodes with highest affinity values. equation follows from the discussion of computing pagerank contributions in the time-reverse markov chain in, and the fact that in an undirected graph the amount of probability that a vertex has in the stationary distribution of a random walk is proportional to its degree. it follows from equation that the amount of error in the probability that u has in the approximate personalized pagerank vector of v is at most ϵ·d: we denote by pr-aff the exact pagerank affinity of u and v, and by the approximate pagerank affinity computed by approximatepraffinity. using equations and we can verify that the amount of error in the approximate pagerank affinity of vertices u and v is at most the product of ϵ and the larger of their degrees: runtime analysis the approximate pagerank vector computed by approximatepr has few non-zero entries. this saves computation time because we do not need to consider vertices with probability in the approximate pagerank vector. let us call the support of probability distribution vector p, denoted by supp, the set of all vertices that have non-zero probability in p: approximatepr computes an approximate pagerank vector with small support, which is useful for large graphs that have many vertices. more specifically, the number of non-zero entries in the approximate pagerank vector is less than: thus the exact runtime of approximatepraffinity is the time necessary to compute, which takes o(), plus the time necessary to compute the affinity to v of each vertex in supp), which is linear in the size of the support set, plus the time necessary to find the k vertices with largest affinity scores, which takes at most k·, giving a total runtime of o. moreover, if we treat α as a constant in this analysis, this expression simplifies to o(). properties of pagerank vectors it is well-known that a pagerank vector can be expressed as a weighted average of random walk vectors: the swt term gives the probability distribution of the random walk after t steps. equation thus shows that in computing pagerank we consider paths of all lengths, with less weight given to longer paths based on the value of α. another important property of pagerank vectors is that if u and v are in the same cluster, both pr and pr are likely to be high. the quality of a cluster c is measured by proportion of outgoing edges, known as conductance, which we denote by Φ. a cluster of lower conductance is better because its nodes are more connected among themselves than they are with the other nodes in the graph. it is proved in that for any set c, there is a subset of vertices c' ⊆ c, such that for any vertex u ∈ c', the personalized pagerank vector of u, denoted by prα, satisfies in other words, pr = prα is high on average if u and v are in the same good cluster c and u ∈ c'. moreover, the set c' is large, as the sum of degrees of its nodes, denoted by vol, satisfies vol ≥ vol/ other measures of closeness in our experiments on protein networks, we compare pagerank affinity and approximate pagerank affinity with several other measures of closeness, which are described below. some of these measures assign an affinity score to each pair of vertices, while others simply order pairs by their closeness. shortest path and shortest path multiplicity the shortest path closeness of two vertices is the inverse of the length of the shortest path between them. however, using the length of the shortest path does not allow for much granularity, so we also consider the multiplicity of the shortest path to break ties between pairs that are the same distance apart. common neighbors a very intuitive measure of closeness of two vertices is the number of neighbors that they share in the graph. in our experiments, we notice that in addition to counting common neighbors, it also helps to take into account whether the two nodes are directly connected, by adding a small constant to their closeness score if this is the case. partitioning we also compare with another measure of closeness, motivated by efforts to partition ppi networks and determine overlap with known protein complexes. it is observed that the densest clusters are often the ones that overlap most with known complexes. therefore, we partition the protein network, and score pairs of vertices that are in the same cluster by the edge density of the cluster. to partition the network, we use metis, a widely used algorithm that finds high-quality, balanced clusters in the graph. once we partition the network, we consider protein pairs in denser clusters closer than pairs in less dense clusters, because pairs in denser clusters are more likely to be part of the same functional unit. of course, this approach only allows us to consider a small fraction of the pairs, because we have no way to evaluate the closeness of two proteins assigned to different clusters. cliques and k-cores in addition to partitioning the graph and evaluating the edge density of each cluster, we can also search for dense components directly by enumerating maximum cliques and finding k-cores. a k-core is a vertex-induced subgraph where the degree of each node is at least k. we then consider pairs that are part of a larger clique closer than pairs that are part of a smaller clique, and consider pairs that are part of an m-core closer than pairs that are part of an n-core if m >n. however, once again, these measures allow us to evaluate the closeness of only a small number of pairs in the network. commute time another way to assess the closeness of two nodes using a random walk on the graph is to consider the inverse of the commute time between them. the commute time between vertices u and v is the expected number of steps taken for a random walk from u to reach v and return, which is computed as described in.  we develop a tool, which is accessible at http://xialab.bu.edu/resources/pnns, that quickly finds nodes closest to a queried protein in any protein-protein interaction network available from biogrid. our tool implements the approximatepraffinity algorithm described in methods, and returns a list of proteins sorted by their approximate pagerank affinity to the queried protein, along with the affinity scores. the user can specify a protein network by selecting an organism and a set of interaction types. in addition, one may upload a custom network, which may be weighted. our application is also available as a command-line executable. to assess the meaning of our closeness measure in protein networks we use protein complex annotation from, and functional distance data from. we consider these datasets "gold standard" measures of protein functional similarity because they are based on information that is manually curated. a good measure of closeness in a protein-protein interaction network should be consistent with these data: we expect many of the closest nodes in the network to be in the same protein complex, and more generally have lower functional distances. figure displays one of the protein networks used in our study, with proteins annotated to be in the same complex labeled using the same color: we can see that a lot of the clusters in the network indeed contain proteins that belong to the same complex. we evaluate the closeness of protein pairs in ppi networks from biogrid, version. biogrid is a repository that lists interacting protein pairs, and for each pair gives the experimental method used to detect the interaction. we use three different networks in our study, which differ in the type of experiment used to detect the interactions. one of the networks is formed from interactions detected by affinity capture-western experiments, and the other two are from affinity capture-ms, and two-hybrid experiments. in each network, we use pagerank affinity and other measures described in methods to rank protein pairs by closeness, in order to determine which measures are more biologically significant. to calculate the pagerank affinity of all pairs of nodes in a network, we compute a personalized pagerank vector of each vertex, and then calculate a pagerank affinity score for each pair from their personalized pagerank vectors, as described in methods. in order to see if we get similar results with the quicker approximation method that our tool implements, in each network we also calculate the approximate pagerank affinity of protein pairs by running the approximatepraffinity algorithm from each vertex. predicting co-complex membership we first investigate which measure of closeness is best at predicting co-complex membership. in every network, we compare how many co-complex pairs are in the top percentile of each closeness ranking. we also calculate the number of co-complex pairs that we expect in each percentile by chance, to see how statistically significant the results are. figure displays the results of our computational experiment. there are three panels: one for each ppi network that we study. bars of different color are used to represent the results for the different closeness measures compared. in each sub-figure the x-axis lists different percentiles of the closeness rankings, and the y-axis lists the fraction of the total number of co-complex pairs in the network contained in the top percentile of a particular ranking. for example, there are co-complex pairs among the proteins in the ac-western network. when we examine the top 1% pairs with highest pagerank affinity in this ppi network, there are co-complex pairs among them, which constitutes a = fraction displayed in the figure. from figure we also see that few co-complex pairs are considered close using partitioning. partitioning seeks out clusters that are balanced in size, which often hurts their quality. pagerank affinity is also related to cluster co-membership, but considers whether two nodes are part of a local cluster rather than a cluster in a global partition of the graph. the closeness of two nodes is then proportional to the quality of this local cluster, which does not depend on a partition of the entire network, which is less relevant. therefore pagerank affinity is a more flexible measure that better reflects whether two nodes are part of some quality cluster in the network. correlation with functional distance in addition to using protein complex annotation, we also use functional distance data to see which measures of closeness are more biologically relevant. to calculate functional distances, we use a measure based on go biological process annotation. the method of provides a very sensitive measure of functional distance because it considers all known functions of a pair of proteins in assigning them a score. we first investigate whether there is any global correlation between the functional distances and any measure of closeness. in each network we rank all protein pairs by functional distance, and compute correlation with the closeness ranking of each measure using the pearson correlation coefficient. however, we find that there is very little global correlation between functional distances and any measure of closeness. this is not surprising because functional annotation and protein-protein interaction data are fundamentally very different. therefore we perform a different analysis, where we simply average the functional distances of the protein pairs in the top k percent of each closeness ranking, for different values of k. in our calculations of functional distance we take the logarithm of the functional distance score from; a lower value indicates a closer functional relationship. we notice that for most closeness rankings the average functional distance is worse for protein pairs that are further away, as expected. the results of our experiment are presented in figure once again, there are three panels, one for each protein network that we study, and bars of different color are used to represent the results for the different closeness measures compared. in each sub-figure the x-axis lists different percentiles of the closeness rankings, and the y-axis displays the average functional distance of protein pairs in the top percentile of a particular ranking. robustness to noise a closeness measure is particularly useful if it tells us something about the true structure of the network in the presence of noise. the interactions in ppi networks are not random: proteins function in modules, therefore we should be able to use the community structure of the network to identify true positive and true negative interactions, unless this structure is completely destroyed by noise. as described in methods, our measure of closeness is provably related to cluster co-membership, therefore we expect it to be resilient to noise if the network has strong community structure. to test this hypothesis, we conduct an experiment where we build a ppi network from the complex annotation in, add noise to it by adding/removing edges, and then evaluate the closeness of true positive and true negative interactions in the noisy network using pagerank affinity. to build the protein network we connect two proteins by an edge if they are annotated as co-complexed in. we only consider protein complexes of size ≥ which results in a network with nodes and edges. to evaluate the resilience of a closeness measure to noise, we use a metric that considers the closeness of nodes in the noisy network, and counts how often true positive interactions are closer than true negative interactions. more specifically, let g = be the true network and = be the modified network. we add noise to the network by randomly choosing r * |e| of the true positive interactions and removing them, and randomly choosing r * |e| of the true negative interactions and adding them. we then consider node pairs p = ∈ v × v and p = ∈ v × v, such that one of them is connected in the true network and the other is not: either ∈ e and ∉ e or ∉ e and ∈ e. we call concordant if the connected pair is closer in the noisy network than the disconnected pair, and discordant otherwise. for a particular experiment, where we take the true network, add noise to it, and calculate the closeness of node pairs in the modified network, we use nc to denote the number of concordant pairs and nd to denote the number of discordant pairs. we then calculate a robustness score for a similarity measure as ∈. a score of indicates that each true positive interaction is closer in the noisy network than each true negative interaction, and a score of - indicates that each true positive interaction is further in the noisy network than each true negative interaction. this experiment provides insight into why our closeness measure is effective at identifying co-complex protein pairs in ppi networks. the protein networks used in our study are similar to, the noisy network in our experiment: they are formed from a true set of protein-protein interactions given by the protein complexes, which is altered by noise due to the nature of the experiments used to detect the interactions. still, the noisy network preserves some of the community structure, and many of the protein pairs that have high pagerank affinity are true interactions, which are the co-complex pairs. with this in mind, we further investigate whether our measure can be used to detect false negative interactions in ppi data by examining non-interacting pairs with highest pagerank affinity in each protein network used in our study. for each pair, we look for other evidence of interaction between the two proteins using complex annotation from, and also examine whether the two proteins are annotated as interacting in biogrid using other experimental methods. we find that for many of the disconnected pairs with highest pagerank affinity there are other sources of evidence of interaction between the two proteins. the results are presented in additional files where we consider the disconnected protein pairs with highest pagerank affinity in each network. additional file shows that when we examine the disconnected pairs with highest pagerank affinity in the ac-western network, we find evidence that of them are in fact interacting. for the acms and two-hybrid networks we find and such pairs, respectively. these numbers are all much higher than expected by chance. discussion defining pagerank affinity to determine the closeness of proteins a and b in a ppi network, we compute two pagerank contributions c = pr and c = pr. to better understand how to combine the two contributions into a single score, we consider different possibilities, and see which ones are more biologically relevant in terms of predicting co-complex membership and correlation with functional distance. we first try combinations of the form for different values of β. here β = corresponds to taking the minimum of c and c β = 1/ corresponds to taking the arithmetic mean, and β = corresponds to taking the maximum of the two contributions. in addition, we try combinations of the form of for different values of β. here β = corresponds to taking the minimum of the two contributions, β = 1/ corresponds to taking the geometric mean, and β = to taking the maximum. when we evaluate different ways of combining the two pagerank contributions we notice that taking the minimum of c and c better predicts co-complex membership in two out of the three networks. moreover, using the minimum of the two contributions gives a measure that is more correlated with functional distance in all three networks. the complete results of our experiments are presented in additional files and additional file displays the results of evaluating different ways of combining the two pagerank contributions using a weighted arithmetic mean, while additional file displays the results of evaluating different ways of combining the two values using a weighted geometric mean. there are panels in each figure: the first three display a comparison in terms of predicting co-complex membership, and the next three display a comparison in terms of correlation with functional distance. for the first three panels higher values are better because they indicate more co-complex pairs that are close, while for the next three panels lower values are better because they indicate that pairs that are close have low functional distances, and are thus more functionally related. our experiments indicate that taking the minimum of pr and pr gives a more biologically meaningful measure of closeness. furthermore, we know that in an undirected network pr = pr, where d denotes the degree of a. therefore using the minimum of the two contributions is equivalent to reporting pr if d ≥ d, and pr otherwise. thus our measure of closeness considers a random walk on the protein network from the larger-degree protein to the smaller-degree protein, which is a sound approach because proteins with large degree are easily reachable from most other proteins in a random walk regardless of their identity. advantages of pagerank affinity as discussed in methods, node pairs that are part of the same cluster in a graph will likely have higher pagerank affinity. this property makes it a very relevant measure for protein networks because we expect pairs of proteins in the same cluster to be more functionally related, and be more likely to be in the same protein complex. therefore it is not surprising that pagerank affinity outperforms other measures of closeness in terms of correlation with functional distance and predicting co-complex membership. in addition, pagerank affinity is a very precise measure of closeness, and is robust to noise in the data. as discussed in methods, personalized pagerank takes into account all paths between two nodes in a graph, by considering an arbitrarily long random walk from the starting vertex. this allows for more precision in assessing closeness, which is especially useful in protein networks, where most protein pairs are very close to each other in terms of shortest path distance. moreover, considering all paths between two vertices makes pagerank affinity very robust to noise in the data, because a few extraneous or missing edges are less likely to make a big difference in evaluating the closeness of two nodes. we also have experimental evidence to support this claim, as pagerank affinity performs very well in distinguishing between true positive and true negative interactions in our simulated noisy networks. a tool to compute pagerank affinity one of our goals is to use our closeness measure to develop a practical tool that can be used to quickly find proteins closest to a queried vertex in a ppi network. we can compute the pagerank affinity of one vertex to all other vertices in the network by solving a single pagerank equation. while it is possible to do this in real time for most protein networks formed from interactions listed in biogrid today, as the size of the data continues to grow this computation will become more challenging. moreover, even right now some of the protein networks from biogrid are already too big to compute pagerank affinity exactly in real time. our approximation algorithm, on the other hand, allows us to easily manage the tradeoff between computation time and the quality of the produced output. in our experiments we have shown that when we approximate pagerank affinity, the quality of the output does not decrease much. our tool works quickly on datasets currently available in biogrid, and easily scales to much larger protein networks and other biological networks.  we develop a method to evaluate the closeness of two proteins in a ppi network, and show that it is biologically meaningful in terms of predicting co-complex membership and correlation with functional distance. moreover, we create a tool that can be used to quickly find nodes closest to a queried vertex in any protein network available from biogrid or specified by the user. authors' contributions kv, sht, and yx conceived and designed the experiments. kv performed the experiments and analyzed the data. kv, sht, and yx drafted and edited the manuscript. all authors read and approved the final manuscript. supplementary material additional file 1 predicted false negative interactions in the ac-western network. the table lists disconnected node pairs with highest pagerank affinity in the ac-western network, along with evidence for the existence of each interaction. each row specifies a pair of proteins and the rank of their pagerank affinity score. for each pair we list evidence of the existence of this interaction in the evidence of interaction column by writing co-complexed if the two proteins are annotated as co-complexed in, and writing ac-western, ac-ms, two-hybrid, and other if the pair is listed as interacting in biogrid using affinity capture-western, affinity capture-ms, two-hybrid, or any other type of experiment. click here for file additional file 2 predicted false negative interactions in the ac-ms network. the table lists disconnected node pairs with highest pagerank affinity in the ac-ms network, along with evidence for the existence of each interaction. each row specifies a pair of proteins and the rank of their pagerank affinity score. for each pair we list evidence of the existence of this interaction in the evidence of interaction column by writing co-complexed if the two proteins are annotated as co-complexed in, and writing ac-western, ac-ms, two-hybrid, and other if the pair is listed as interacting in biogrid using affinity capture-western, affinity capture-ms, two-hybrid, or any other type of experiment. click here for file additional file 3 predicted false negative interactions in the two-hybrid network. the table lists disconnected node pairs with highest pagerank affinity in the two-hybrid network, along with evidence for the existence of each interaction. each row specifies a pair of proteins and the rank of their pagerank affinity score. for each pair we list evidence of the existence of this interaction in the evidence of interaction column by writing co-complexed if the two proteins are annotated as co-complexed in, and writing ac-western, ac-ms, two-hybrid, and other if the pair is listed as interacting in biogrid using affinity capture-western, affinity capture-ms, two-hybrid, or any other type of experiment. click here for file additional file 4 evaluating different ways of defining pagerank affinity by using a weighted arithmetic mean to combine the two pagerank contributions. we evaluate different ways of combining c = pr and c = pr using a weighted arithmetic mean: β·max + ·min. each value of β gives a distinct closeness measure, which is evaluated in terms of predicting co-complex membership, and correlation with functional distance in the three networks that we study. panels - display the number of co-complex pairs among pairs in the top percentile of each closeness ranking in the ac-western, ac-ms, and two-hybrid networks. higher values indicate measures that are more biologically meaningful. panels - display the average functional distance of pairs in the top percentile of each closeness ranking in the ac-western, ac-ms, and two-hybrid networks. lower values indicate measures that are more biologically meaningful. click here for file additional file 5 evaluating different ways of defining pagerank affinity by using a weighted geometric mean to combine the two pagerank contributions. we evaluate different ways of combining c = pr and c = pr using a weighted geometric mean: maxβ·min1-β. each value of β gives a distinct closeness measure, which is evaluated in terms of predicting co-complex membership, and correlation with functional distance in the three networks that we study. panels - display the number of co-complex pairs among pairs in the top percentile of each closeness ranking in the ac-western, ac-ms, and two-hybrid networks. higher values indicates measures that are more biologically meaningful. panels - display the average functional distance of pairs in the top percentile of each closeness ranking in the ac-western, ac-ms, and two-hybrid networks. lower values indicate measures that are more biologically meaningful. click here for file acknowledgements konstantin voevodski is supported by an igert fellowship through nsf grant dge- awarded to the aces training program at bu center for computational science. yu xia is supported by a research starter grant in informatics from the phrma foundation. shang-hua teng is supported in part by nsf grant ccr- 
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. moreover, our experiments indicate that pagerank affinity is very resilient to noise in the network. we can learn a lot about a particular protein by querying its neighborhood in a ppi network to find proteins with similar function. a spectral approach that considers random walks between nodes of interest is particularly useful in evaluating closeness in ppi 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. 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. 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. 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. we also develop a tool, accessible at http://xialab.bu.edu/resources/pnns, 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. spectral measures of closeness are more robust to noise in the data and are more precise than simpler methods based on edge density and shortest path length.
 protein-protein interaction networks enable us to better understand the functional organization of the proteome. we can learn a lot about a particular protein by querying its neighborhood in a ppi network to find proteins with similar function. a spectral approach that considers random walks between nodes of interest is particularly useful in evaluating closeness in ppi networks. spectral measures of closeness are more robust to noise in the data and are more precise than simpler methods based on edge density and shortest path length.  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, 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. 