{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T10:21:27Z","timestamp":1773224487697,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"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 interactions (PPIs) play fundamental roles in nearly all biological processes, and provide major insights into the inner workings of cells. A vast amount of PPI data for various organisms is available from BioGRID and other sources. The identification of communities in PPI networks is of great interest because they often reveal previously unknown functional ties between proteins. A large number of global clustering algorithms have been applied to protein networks, where the entire network is partitioned into clusters. Here we take a different approach by looking for local communities in PPI networks.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We develop a tool, named Local Protein Community Finder, which quickly finds a community close to a queried protein in any network available from BioGRID or specified by the user. Our tool uses two new local clustering algorithms Nibble and PageRank-Nibble, which look for a good cluster among the most popular destinations of a short random walk from the queried vertex. The quality of a cluster is determined by proportion of outgoing edges, known as conductance, which is a relative measure particularly useful in undersampled networks. We show that the two local clustering algorithms find communities that not only form excellent clusters, but are also likely to be biologically relevant functional components. We compare the performance of Nibble and PageRank-Nibble to other popular and effective graph partitioning algorithms, and show that they find better clusters in the graph. Moreover, Nibble and PageRank-Nibble find communities that are more functionally coherent.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>The Local Protein Community Finder, accessible at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/xialab.bu.edu\/resources\/lpcf\" ext-link-type=\"uri\">http:\/\/xialab.bu.edu\/resources\/lpcf<\/jats:ext-link>, allows the user to quickly find a high-quality community close to a queried protein in any network available from BioGRID or specified by the user. We show that the communities found by our tool form good clusters and are functionally coherent, making our application useful for biologists who wish to investigate functional modules that a particular protein is a part of.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-10-297","type":"journal-article","created":{"date-parts":[[2009,9,21]],"date-time":"2009-09-21T12:26:17Z","timestamp":1253535977000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":58,"title":["Finding local communities in protein networks"],"prefix":"10.1186","volume":"10","author":[{"given":"Konstantin","family":"Voevodski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,9,18]]},"reference":[{"key":"3027_CR1","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\u2013643. 10.1038\/nature04670","journal-title":"Nature"},{"key":"3027_CR2","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1140\/epjb\/e2004-00124-y","volume":"38","author":"M Newman","year":"2004","unstructured":"Newman M: Fast algorithm for detecting community structure in networks. Eur Phys J B 2004, 38: 321\u2013330. 10.1140\/epjb\/e2004-00124-y","journal-title":"Eur Phys J B"},{"key":"3027_CR3","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\u20137826. 10.1073\/pnas.122653799","journal-title":"Proc Natl Acad Sci USA"},{"key":"3027_CR4","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\u2013818. 10.1038\/nature03607","journal-title":"Nature"},{"key":"3027_CR5","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":"3027_CR6","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\u2013234."},{"key":"3027_CR7","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\u20131493. 10.1016\/S1389-1286(99)00040-7","journal-title":"Computer Networks"},{"key":"3027_CR8","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\u201370. 10.1109\/2.989932","journal-title":"Computer"},{"key":"3027_CR9","first-page":"604","volume-title":"Proc ACM Conf on Hypertext and Hypermedia","author":"J Kleinberg","year":"1998","unstructured":"Kleinberg J: Authoritative sources in a hyperlinked environment. Proc ACM Conf on Hypertext and Hypermedia 1998, 604\u2013632."},{"key":"3027_CR10","volume-title":"Technical report, Stanford University","author":"L Page","year":"1998","unstructured":"Page L, Brin S, Motwani R, Winograd T: The pagerank citation ranking: Bringing order to the web. Technical report, Stanford University 1998."},{"key":"3027_CR11","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","volume":"30","author":"S Brin","year":"1998","unstructured":"Brin S, Page L: The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 1998, 30: 107\u2013117. 10.1016\/S0169-7552(98)00110-X","journal-title":"Computer Networks and ISDN Systems"},{"key":"3027_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Proc Sympos on Complexity of Computer Computations","author":"R Karp","year":"1972","unstructured":"Karp R: Reducibility among combinatorial problems. Proc Sympos on Complexity of Computer Computations 1972, 85\u2013103."},{"key":"3027_CR13","first-page":"2","volume-title":"Proc IEEE Foundations of Computer Science","author":"U Feige","year":"1991","unstructured":"Feige U, Goldwasser S, Lovasz L, Szegedy M: Approximating clique is almost NP-complete. Proc IEEE Foundations of Computer Science 1991, 2\u201312."},{"key":"3027_CR14","doi-asserted-by":"publisher","first-page":"2443","DOI":"10.1093\/nar\/gkg340","volume":"31","author":"D Bu","year":"2003","unstructured":"Bu D, Zhao Y, Cai L, Xue H, Zhu X, Lu H, Zhang J, Sun S, Ling L, Zhang N, Li G, Chen R: Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Res 2003, 31: 2443\u20132450. 10.1093\/nar\/gkg340","journal-title":"Nucleic Acids Res"},{"key":"3027_CR15","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1093\/bioinformatics\/btl014","volume":"22","author":"H Yu","year":"2006","unstructured":"Yu H, Paccanaro A, Trifonov V, Gerstein M: Predicting interactions in protein networks by completing defective cliques. Bioinformatics 2006, 22: 823\u2013829. 10.1093\/bioinformatics\/btl014","journal-title":"Bioinformatics"},{"key":"3027_CR16","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A Sinclair","year":"1989","unstructured":"Sinclair A, Jerrum M: Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation 1989, 82: 93\u2013113. 10.1016\/0890-5401(89)90067-9","journal-title":"Information and Computation"},{"key":"3027_CR17","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/1471-2105-4-2","volume":"4","author":"G Bader","year":"2003","unstructured":"Bader G, Hogue C: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 2003, 4: 2. 10.1186\/1471-2105-4-2","journal-title":"BMC Bioinformatics"},{"key":"3027_CR18","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\u201312128. 10.1073\/pnas.2032324100","journal-title":"Proc Natl Acad Sci USA"},{"key":"3027_CR19","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\u20132290. 10.1093\/bioinformatics\/btl370","journal-title":"Bioinformatics"},{"key":"3027_CR20","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\u20133020. 10.1093\/bioinformatics\/bth351","journal-title":"Bioinformatics"},{"key":"3027_CR21","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":"3027_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1186\/1471-2105-10-99","volume":"10","author":"J Vlasblom","year":"2009","unstructured":"Vlasblom J, Wodak S: Markov clustering versus affinity propagation for the partitioning of protein interaction graphs. BMC Bioinformatics 2009, 10: 99. 10.1186\/1471-2105-10-99","journal-title":"BMC Bioinformatics"},{"key":"3027_CR23","volume-title":"A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning","author":"DA Spielman","year":"2008","unstructured":"Spielman DA, Teng S: A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning. 2008. 0809.3232v1 [cs.DS]"},{"key":"3027_CR24","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\u20132173. 10.1093\/bioinformatics\/btm291","journal-title":"Bioinformatics"},{"key":"3027_CR25","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\u2013486."},{"key":"3027_CR26","volume-title":"Proc IEEE Int Prallel & Distributed Processing Sympos","author":"A Abou","year":"2006","unstructured":"Abou A, Karypis G: Multilevel algorithms for partitioning power-law graphs. Proc IEEE Int Prallel & Distributed Processing Sympos 2006."},{"key":"3027_CR27","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00083-3","volume":"90","author":"C Alpert","year":"1999","unstructured":"Alpert C, Kahng A, Yao Z: Spectral partitioning: The more eigenvectors the better. Discreet Applied Mathematics 1999, 90: 3\u201326. 10.1016\/S0166-218X(98)00083-3","journal-title":"Discreet Applied Mathematics"},{"key":"3027_CR28","volume-title":"Neural Information Processing Systems","author":"M Meila","year":"2001","unstructured":"Meila M, Shi J: Learning Segmentation by Random Walks. Neural Information Processing Systems 2001."},{"key":"3027_CR29","first-page":"367","volume-title":"Proc IEEE Foundations of Computer Science","author":"R Kannan","year":"2000","unstructured":"Kannan R, Vempala S, Vetta A: On clusterings: good, bad and spectral. Proc IEEE Foundations of Computer Science 2000, 367\u2013377."},{"key":"3027_CR30","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1109\/43.159993","volume":"11","author":"L Hagen","year":"1992","unstructured":"Hagen L, Kahng A: New spectral methods for ratio cut partitioning and clustering. IEEE Trans on CAD of Integrated Circtuis and Systems 1992, 11: 1074\u20131085. 10.1109\/43.159993","journal-title":"IEEE Trans on CAD of Integrated Circtuis and Systems"},{"key":"3027_CR31","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.laa.2006.07.020","volume":"421","author":"DA Spielman","year":"2007","unstructured":"Spielman DA, Teng S: Spectral partitioning works: Planar graphs and finite element meshes. Linear Algebra Appl 2007, 421: 284\u2013305. 10.1016\/j.laa.2006.07.020","journal-title":"Linear Algebra Appl"},{"key":"3027_CR32","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1137\/S0097539705447244","volume":"35","author":"J Kelner","year":"2006","unstructured":"Kelner J: Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus. SIAM J Comput 2006, 35: 882\u2013902. 10.1137\/S0097539705447244","journal-title":"SIAM J Comput"},{"key":"3027_CR33","first-page":"751","volume-title":"Proc IEEE Foundations of Computer Science","author":"P Biswal","year":"2008","unstructured":"Biswal P, Lee JR, Rao S: Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows. Proc IEEE Foundations of Computer Science 2008, 751\u2013760."},{"key":"3027_CR34","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00083-3","volume":"90","author":"C Alpert","year":"1999","unstructured":"Alpert C, Kahng A, Yao S: Spectral partitioning with multiple eigenvectors. Discrete Applied Mathematics 1999, 90: 3\u201326. 10.1016\/S0166-218X(98)00083-3","journal-title":"Discrete Applied Mathematics"},{"key":"3027_CR35","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\u2013117."},{"key":"3027_CR36","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\u2013279."},{"key":"3027_CR37","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\u201366. 10.2307\/2685263","journal-title":"Am Stat"},{"key":"3027_CR38","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\u20139. 10.1093\/nar\/gkj109","journal-title":"Nucleic Acids Res"},{"key":"3027_CR39","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1038\/nbt1116","volume":"23","author":"J Han","year":"2005","unstructured":"Han J, Dupuy D, Bertin N, Cusick M, Vidal M: Effect of sampling on topology predictions of protein-protein interactions. Nat Biotechnol 2005, 23: 839\u2013844. 10.1038\/nbt1116","journal-title":"Nat Biotechnol"},{"key":"3027_CR40","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1126\/science.1158684","volume":"322","author":"H Yu","year":"2008","unstructured":"Yu H, Braun P, Yildirim MA, Lemmens I, Venkatesan K, Sahalie J, Hirozane-Kishikawa T, Gebreab F, Li N, Simonis N, Hao T, Rual JF, Dricot A, Vazquez A, Murray RR, Simon C, Tardivo L, Tam S, Svrzikapa N, Fan C, de Smet AS, Motyl A, Hudson ME, Park J, Xin X, Cusick ME, Moore T, Boone C, Snyder M, Roth FP, Barabasi AL, Tavernier J, Hill DE, Vidal M: High-quality binary protein interaction map of the yeast interactome network. Science 2008, 322: 104\u2013110. 10.1126\/science.1158684","journal-title":"Science"},{"key":"3027_CR41","doi-asserted-by":"publisher","first-page":"W115","DOI":"10.1093\/nar\/gkp406","volume":"37","author":"Z Hu","year":"2009","unstructured":"Hu Z, Hung J, Wang Y, Chang Y, Huang C, Huyck M, DeLisi C: VisANT 3.5: multi-scale network visualization, analysis and inference based on the gene ontology. Nucleic Acids Res 2009, 37: W115\u2013121. 10.1093\/nar\/gkp406","journal-title":"Nucleic Acids Res"},{"key":"3027_CR42","first-page":"321","volume":"20","author":"E Boyle","year":"2004","unstructured":"Boyle E, Weng S, Jin H, Botstein D, Cherry J, Sherlock G: GO::TermFinder-open source software for accessing Gene Ontology information and finding significantly enriched Gene Ontology terms associated with a list of genes. Bioinformatics 2004, 20: 321\u2013330.","journal-title":"Bioinformatics"},{"key":"3027_CR43","doi-asserted-by":"publisher","first-page":"D577","DOI":"10.1093\/nar\/gkm909","volume":"36","author":"EL Hong","year":"2008","unstructured":"Hong EL, Balakrishnan R, Dong Q, Christie KR, Park J, Binkley G, Costanzo MC, Dwight SS, Engel SR, Fisk DG, Hirschman JE, Hitz BC, Krieger CJ, Livstone MS, Miyasato SR, Nash RS, Oughtred R, Skrzypek MS, Weng S, Wong E, Zhu KK, Dolinski K, Botstein D, Cherry JM: Gene Ontology annotations at SGD: new data sources and annotation methods. Nucleic Acids Res 2008, 36: D577\u2013581. 10.1093\/nar\/gkm909","journal-title":"Nucleic Acids Res"},{"key":"3027_CR44","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","volume":"5","author":"S Seidman","year":"1983","unstructured":"Seidman S: Network structure and minimum degree. Social Networks 1983, 5: 269\u2013287. 10.1016\/0378-8733(83)90028-X","journal-title":"Social Networks"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-10-297.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T21:40:13Z","timestamp":1630446013000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-10-297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,18]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["3027"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-10-297","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,18]]},"assertion":[{"value":"21 April 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 September 2009","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 September 2009","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"297"}}