{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:34:21Z","timestamp":1773272061442,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Syst Biol"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Protein-protein interaction (PPI) 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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>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 <jats:italic>PageRank Affinity<\/jats:italic>, 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 <jats:italic>PageRank Affinity<\/jats:italic> is a precise measure that is robust to noise in the data. <jats:italic>PageRank Affinity<\/jats:italic> 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 <jats:italic>PageRank Affinity<\/jats:italic> 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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>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 <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/xialab.bu.edu\/resources\/pnns\" ext-link-type=\"uri\">http:\/\/xialab.bu.edu\/resources\/pnns<\/jats:ext-link>, 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.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1752-0509-3-112","type":"journal-article","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T11:46:54Z","timestamp":1259668014000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Spectral affinity in protein networks"],"prefix":"10.1186","volume":"3","author":[{"given":"Konstantin","family":"Voevodski","sequence":"first","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]},{"given":"Yu","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,11,29]]},"reference":[{"key":"380_CR1","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1038\/35075138","volume":"411","author":"H Jeong","year":"2001","unstructured":"Jeong H, Mason S, Barabasi A, Oltvai Z: Lethality and centrality in protein networks. Nature. 2001, 411: 41-42. 10.1038\/35075138","journal-title":"Nature"},{"key":"380_CR2","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1093\/molbev\/msi072","volume":"22","author":"M Hahn","year":"2005","unstructured":"Hahn M, Kern A: Comparative Genomics of Centrality and Essentiality in Three Eukaryotic Protein-Interaction Networks. Mol Biol Evol. 2005, 22: 803-806. 10.1093\/molbev\/msi072","journal-title":"Mol Biol Evol"},{"key":"380_CR3","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1016\/j.socnet.2005.11.003","volume":"28","author":"J Fowler","year":"2006","unstructured":"Fowler J: Legislative cosponsorship networks in the US House and Senate. Social Networks. 2006, 28: 454-465. 10.1016\/j.socnet.2005.11.003.","journal-title":"Social Networks"},{"key":"380_CR4","first-page":"225","volume-title":"Proc ACM Conf on Hypertext and Hypermedia","author":"D Gibson","year":"1998","unstructured":"Gibson D, Kleinberg J, Raghavan P: Inferring Web communities from link topology. Proc ACM Conf on Hypertext and Hypermedia. 1998, 225-234."},{"key":"380_CR5","doi-asserted-by":"publisher","first-page":"1481","DOI":"10.1016\/S1389-1286(99)00040-7","volume":"31","author":"R Kumar","year":"1999","unstructured":"Kumar R, Raghavan P, Rajagopalan S, Tomkins A: Trawling the Web for emerging cyber-communities. Computer Networks. 1999, 31: 1481-1493. 10.1016\/S1389-1286(99)00040-7.","journal-title":"Computer Networks"},{"key":"380_CR6","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1109\/2.989932","volume":"35","author":"G Flake","year":"2002","unstructured":"Flake G, Lawrence S, Giles C, Coetzee F: Self-organization and identification of Web communities. Computer. 2002, 35: 66-70. 10.1109\/2.989932.","journal-title":"Computer"},{"key":"380_CR7","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1038\/nature03607","volume":"435","author":"G Palla","year":"2005","unstructured":"Palla G, Derenyi I, Farkas I, Vicsek T: Uncovering the overlapping community structure of complex networks in nature and society. Nature. 2005, 435: 814-818. 10.1038\/nature03607","journal-title":"Nature"},{"key":"380_CR8","doi-asserted-by":"publisher","first-page":"026132","DOI":"10.1103\/PhysRevE.72.026132","volume":"72","author":"A Clauset","year":"2005","unstructured":"Clauset A: Finding local community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys. 2005, 72: 026132-","journal-title":"Phys Rev E Stat Nonlin Soft Matter Phys"},{"key":"380_CR9","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1038\/nature04670","volume":"440","author":"N Krogan","year":"2006","unstructured":"Krogan N, Cagney G, Yu H, Zhong G, Guo X, Ignatchenko A, Li J, Pu S, Datta N, Tikuisis A, Punna T, Peregrin-Alvarez J, Shales M, Zhang X, Davey M, Robinson M, Paccanaro A, Bray J, Sheung A, Beattie B, Richards D, Canadien V, Lalev A, Mena F, Wong P, Starostine A, Canete M, Vlasblom J, Wu S, Orsi C, Collins S, Chandran S, Haw R, Rilstone J, Gandi K, Thompson N, Musso G, Onge PS, Ghanny S, Lam M, Butland G, Altaf-U A, Kanaya S, Shilatifard A, O'Shea E, Weissman J, Ingles J, Hughes T, Parkinson J, Gerstein M, Wodak S, Emili A, Greenblatt J: Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature. 2006, 440: 637-643. 10.1038\/nature04670","journal-title":"Nature"},{"key":"380_CR10","volume-title":"Tech. rep., Stichting Mathematicsh Centrum","author":"J Anthonisse","year":"1971","unstructured":"Anthonisse J: The rush in a directed graph. Tech. rep., Stichting Mathematicsh Centrum. 1971"},{"key":"380_CR11","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan M, Newman M: Community structure in social and biological networks. Proc Natl Acad Sci USA. 2002, 99: 7821-7826. 10.1073\/pnas.122653799","journal-title":"Proc Natl Acad Sci USA"},{"key":"380_CR12","doi-asserted-by":"publisher","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"M Newman","year":"2004","unstructured":"Newman M, Girvan M: Finding and evaluating community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys. 2004, 69: 026113-","journal-title":"Phys Rev E Stat Nonlin Soft Matter Phys"},{"key":"380_CR13","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1093\/bioinformatics\/btg415","volume":"20","author":"N Przulj","year":"2004","unstructured":"Przulj N, Wigle D, Jurisica I: Functional topology in a network of protein interactions. Bioinformatics. 2004, 20: 340-348. 10.1093\/bioinformatics\/btg415","journal-title":"Bioinformatics"},{"key":"380_CR14","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1023\/A:1020495201615","volume":"2","author":"R Jansen","year":"2002","unstructured":"Jansen R, Lan N, Qian J: Integration of genomic datasets to predict protein complexes in yeast. J Struct Funct Genomics. 2002, 2: 71-81. 10.1023\/A:1020495201615","journal-title":"J Struct Funct Genomics"},{"key":"380_CR15","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1038\/nature750","volume":"417","author":"C von Mering","year":"2002","unstructured":"von Mering C, Krause R, Snell B, Cornell M, Oliver S, Fields S, Bork P: Comparative assessment of large-scale data sets of protein-protein interactions. Nature. 2002, 417: 399-403. 10.1038\/nature750","journal-title":"Nature"},{"key":"380_CR16","doi-asserted-by":"publisher","first-page":"11149","DOI":"10.1073\/pnas.200327197","volume":"97","author":"L Amaral","year":"2000","unstructured":"Amaral L, Scala A, Barthelemyt M, Stanley H: Classes of small-world networks. Proc Natl Acad Sci USA. 2000, 97: 11149-11152. 10.1073\/pnas.200327197","journal-title":"Proc Natl Acad Sci USA"},{"key":"380_CR17","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D Watts","year":"1998","unstructured":"Watts D, Strogatz S: Collective dynamics of 'small-world' networks. Nature. 1998, 393: 440-442. 10.1038\/30918","journal-title":"Nature"},{"key":"380_CR18","volume-title":"Six Degrees of Separation: A Play","author":"J Guare","year":"1990","unstructured":"Guare J: Six Degrees of Separation: A Play. 1990, Vintate Books"},{"key":"380_CR19","doi-asserted-by":"crossref","unstructured":"Yip A, Horvath S: Gene network interconnectedness and the generalized topological overlap measure. BMC Bioinformatics. 2007, 8 (22):","DOI":"10.1186\/1471-2105-8-22"},{"key":"380_CR20","doi-asserted-by":"publisher","first-page":"1623","DOI":"10.1093\/bioinformatics\/btl145","volume":"22","author":"N Chua","year":"2006","unstructured":"Chua N, Sung W, Wong L: Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions. Bioinformatics. 2006, 22: 1623-1630. 10.1093\/bioinformatics\/btl145","journal-title":"Bioinformatics"},{"key":"380_CR21","doi-asserted-by":"publisher","first-page":"2043","DOI":"10.1093\/bioinformatics\/bti305","volume":"21","author":"K Okada","year":"2005","unstructured":"Okada K, Kanaya S, Asai K: Accurate extraction of functional associations between proteins based on common interaction partners and common domains. Bioinformatics. 2005, 21: 2043-2048. 10.1093\/bioinformatics\/bti305","journal-title":"Bioinformatics"},{"key":"380_CR22","doi-asserted-by":"publisher","first-page":"12579","DOI":"10.1073\/pnas.2132527100","volume":"100","author":"M Samanta","year":"2003","unstructured":"Samanta M, Liang S: Predicting protein functions from redundancies in large-scale protein interaction networks. Proc Natl Acad Sci USA. 2003, 100: 12579-12583. 10.1073\/pnas.2132527100","journal-title":"Proc Natl Acad Sci USA"},{"key":"380_CR23","doi-asserted-by":"publisher","first-page":"4372","DOI":"10.1073\/pnas.0735871100","volume":"100","author":"D Goldberg","year":"2003","unstructured":"Goldberg D, Roth F: Assessing experimentally derived interactions in a small world. Proc Natl Acad Sci USA. 2003, 100: 4372-4376. 10.1073\/pnas.0735871100","journal-title":"Proc Natl Acad Sci USA"},{"key":"380_CR24","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1093\/bioinformatics\/btl581","volume":"23","author":"A Li","year":"2007","unstructured":"Li A, Horvath S: Network neighborhood analysis with the multi-node topological overlap measure. Bioinformatics. 2007, 23: 222-231. 10.1093\/bioinformatics\/btl581","journal-title":"Bioinformatics"},{"key":"380_CR25","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1101\/gr.2203804","volume":"14","author":"S Asthana","year":"2004","unstructured":"Asthana S, King O, Gibbons F, Roth F: Predicting Protein Complex Membership Using Probabilistic Network Reliability. Genome Res. 2004, 14: 1170-1175. 10.1101\/gr.2203804","journal-title":"Genome Res"},{"key":"380_CR26","first-page":"14","volume-title":"Probabilistic Paths for Protein Complex Inference","author":"H Huang","year":"2007","unstructured":"Huang H, Zhang L, Roth F, Bader J: Probabilistic Paths for Protein Complex Inference. 2007, 4532: 14-28. Springer Berlin\/Heidelberg"},{"key":"380_CR27","doi-asserted-by":"crossref","unstructured":"Bader G, Hogue C: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics. 2003, 4 (2):","DOI":"10.1186\/1471-2105-4-2"},{"key":"380_CR28","doi-asserted-by":"publisher","first-page":"12123","DOI":"10.1073\/pnas.2032324100","volume":"100","author":"V Spirin","year":"2003","unstructured":"Spirin V, Mirny L: Protein complexes and functional modules in molecular networks. Proc Natl Acad Sci USA. 2003, 100: 12123-12128. 10.1073\/pnas.2032324100","journal-title":"Proc Natl Acad Sci USA"},{"key":"380_CR29","doi-asserted-by":"publisher","first-page":"2283","DOI":"10.1093\/bioinformatics\/btl370","volume":"22","author":"J Chen","year":"2006","unstructured":"Chen J, Yuan B: Detecting functional modules in the yeast protein-protein interaction network. Bioinformatics. 2006, 22: 2283-2290. 10.1093\/bioinformatics\/btl370","journal-title":"Bioinformatics"},{"key":"380_CR30","doi-asserted-by":"publisher","first-page":"3013","DOI":"10.1093\/bioinformatics\/bth351","volume":"20","author":"A King","year":"2004","unstructured":"King A, Przulj N, Jurisica I: Protein complex prediction via cost-based clustering. Bioinformatics. 2004, 20: 3013-3020. 10.1093\/bioinformatics\/bth351","journal-title":"Bioinformatics"},{"key":"380_CR31","doi-asserted-by":"publisher","first-page":"R6","DOI":"10.1186\/gb-2003-5-1-r6","volume":"5","author":"C Brun","year":"2003","unstructured":"Brun C, Chevenet F, Martin D, Wojcik J, Guenoche A, Jacq B: Functional classification of proteins for the prediction of cellular function from a protein-protein interaction network. Genome Biol. 2003, 5: R6- 10.1186\/gb-2003-5-1-r6","journal-title":"Genome Biol"},{"key":"380_CR32","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1109\/TKDE.2003.1208999","volume":"15","author":"T Haveliwala","year":"2003","unstructured":"Haveliwala T: Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. IEEE Trans on Knowledge and Data Engineering. 2003, 15: 784-796. 10.1109\/TKDE.2003.1208999.","journal-title":"IEEE Trans on Knowledge and Data Engineering"},{"key":"380_CR33","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-540-30216-2_9","volume-title":"Proc Workshop on Algorithms and Models for the Web-Graph","author":"D Fogaras","year":"2004","unstructured":"Fogaras D, Racz B: Towards scaling fully personalized pagerank. Proc Workshop on Algorithms and Models for the Web-Graph. 2004, 105-117."},{"key":"380_CR34","first-page":"271","volume-title":"Proc World Wide Web Conf","author":"G Jeh","year":"2003","unstructured":"Jeh G, Widom J: Scaling personalized web search. Proc World Wide Web Conf. 2003, 271-279."},{"key":"380_CR35","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-77004-6_12","volume-title":"Proc Workshop on Algorithms and Models for the Web-Graph","author":"R Andersen","year":"2007","unstructured":"Andersen R, Borgs C, Chayes J, Hopcraft J, Mirrokni V, Teng S: Local computation of PageRank contributions. Proc Workshop on Algorithms and Models for the Web-Graph. 2007, 150-165. full_text."},{"key":"380_CR36","first-page":"475","volume-title":"Proc IEEE Foundations of Computer Science","author":"R Andersen","year":"2006","unstructured":"Andersen R, Chung F, Lang K: Local graph partitioning using PageRank vectors. Proc IEEE Foundations of Computer Science. 2006, 475-486."},{"key":"380_CR37","volume-title":"Proc IEEE Parallel & Distributed Processing Symposium","author":"A Abou","year":"2006","unstructured":"Abou A, Karypis G: Multilevel algorithms for partitioning power-law graphs. Proc IEEE Parallel & Distributed Processing Symposium. 2006"},{"key":"380_CR38","volume-title":"Recent Trends in Graph Theory, Algebraic Combinatorics, and Graph Algorithms","author":"V Batagelj","year":"2001","unstructured":"Batagelj V, Zavernik M: Cores Decomposition of Networks. Recent Trends in Graph Theory, Algebraic Combinatorics, and Graph Algorithms. 2001"},{"key":"380_CR39","doi-asserted-by":"publisher","first-page":"1873","DOI":"10.1109\/TPAMI.2007.1103","volume":"29","author":"H Qiu","year":"2007","unstructured":"Qiu H, Hancock E: Clustering and embedding using commute times. IEEE Trans on Pattern Analysis and Machine Intelligence. 2007, 29: 1873-1890. 10.1109\/TPAMI.2007.1103.","journal-title":"IEEE Trans on Pattern Analysis and Machine Intelligence"},{"key":"380_CR40","doi-asserted-by":"publisher","first-page":"D41","DOI":"10.1093\/nar\/gkh092","volume":"32","author":"H Mewes","year":"2004","unstructured":"Mewes H, Amid C, Arnold R, Frishman D, Guldener U, Mannhaupt G, Munsterkotter M, Pagel P, Strack N, Stumpflen V, Warfsmann J, Ruepp A: MIPS: analysis and annotation of proteins from whole genomes. Nucleic Acids Res. 2004, 32: D41-44. 10.1093\/nar\/gkh092","journal-title":"Nucleic Acids Res"},{"key":"380_CR41","doi-asserted-by":"publisher","first-page":"2163","DOI":"10.1093\/bioinformatics\/btm291","volume":"23","author":"H Yu","year":"2007","unstructured":"Yu H, Jansen R, Gerstein M: Developing a similarity measure in biological function space. Bioinformatics. 2007, 23: 2163-2173. 10.1093\/bioinformatics\/btm291","journal-title":"Bioinformatics"},{"key":"380_CR42","doi-asserted-by":"publisher","first-page":"D535","DOI":"10.1093\/nar\/gkj109","volume":"34","author":"C Stark","year":"2006","unstructured":"Stark C, Breitkreutz BJ, Reguly T, Boucher L, Breitkreutz A, Tyers M: BioGRID: a general repository for interaction datasets. Nucleic Acids Res. 2006, 34: D535-9. 10.1093\/nar\/gkj109","journal-title":"Nucleic Acids Res"},{"key":"380_CR43","doi-asserted-by":"publisher","first-page":"59","DOI":"10.2307\/2685263","volume":"42","author":"JL Rodgers","year":"1988","unstructured":"Rodgers JL, Nicewander WA: Thirteen ways to look at the correlation coefficient. Am Stat. 1988, 42: 59-66. 10.2307\/2685263.","journal-title":"Am Stat"}],"container-title":["BMC Systems Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1752-0509-3-112.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T03:24:38Z","timestamp":1630466678000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcsystbiol.biomedcentral.com\/articles\/10.1186\/1752-0509-3-112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11,29]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["380"],"URL":"https:\/\/doi.org\/10.1186\/1752-0509-3-112","relation":{},"ISSN":["1752-0509"],"issn-type":[{"value":"1752-0509","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,11,29]]},"assertion":[{"value":"12 June 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2009","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2009","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"112"}}