Abstract
Unraveling the community structure of real-world networks is an important and challenging problem. Recently, it has been shown that methods based on optimizing a clustering measure, in particular modularity, have a resolution bias, e.g. communities with sizes below some threshold remain unresolved. This problem has been tackled by incorporating a parameter in the method which influences the size of the communities. Methods incorporating this type of parameter are also called multi-resolution methods. In this paper we consider fast greedy local search optimization of a clustering objective function with two different objective functions incorporating a resolution parameter: modularity and a function we introduced in a recent work, called w-log-v. We analyze experimentally the performance of the resulting algorithms when applied to protein-protein interaction (PPI) networks. Specifically, publicly available yeast protein networks from past studies, as well as the present BioGRID database, are considered. Furthermore, to test robustness of the methods, various types of randomly perturbed networks obtained from the BioGRID data are also considered. Results of extensive experiments show improved or competitive performance over MCL, a state-of-the-art algorithm for complex detection in PPI networks, in particular on BioGRID data, where w-log-v obtains excellent accuracy and robustness performance.
Chapter PDF
Similar content being viewed by others
Keywords
- Positive Predictive Value
- Community Detection
- Resolution Parameter
- Detect Protein Complex
- Condensed Graph
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Blondel, V.D., et al.: Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008(10), P10008+ (2008)
Brohée, S., van Helden, J.: Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics 7(1), 488+ (2006)
Cherry, J.M., et al.: Saccharomyces Genome Database: the genomics resource of budding yeast. Nucleic Acids Research (2011)
Chua, H.N., et al.: Using indirect protein-protein interactions for protein complex prediction. Journal of Bioinformatics and Computational Biology 6(3), 435–466 (2008)
Collins, S., et al.: Towards a comprehensive atlas of the physical interactome of saccharomyces cerevisiae. In: Molecular Cellular Proteomics, pp. 600200–600381 (2007)
Edwards, A.M., et al.: Bridging structural biology and genomics: assessing protein interaction data with known complexes. Trends in Genetics 18(10), 529–536 (2002)
Fortunato, S.: Community detection in graphs. Physics Reports 486, 75–174 (2010)
Fortunato, S., Barthélemy, M.: Resolution limit in community detection. Proceedings of the National Academy of Sciences 104(1), 36–41 (2007)
Gavin, A.C., et al.: Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature 415(6868), 141–147 (2002)
Gavin, A.-C., Aloy, P., Grandi, P., Krause, R., Boesche, M., Marzioch, M., Rau, C., Jensen, L.J., Bastuck, S., Dumpelfeld, B., Edelmann, A., Heurtier, M.-A., Hoffman, V., Hoefert, C., Klein, K., Hudak, M., Michon, A.-M., Schelder, M., Schirle, M., Remor, M., Rudi, T., Hooper, S., Bauer, A., Bouwmeester, T., Casari, G., Drewes, G., Neubauer, G., Rick, J.M., Kuster, B., Bork, P., Russell, R.B., Superti-Furga, G.: Proteome survey reveals modularity of the yeast cell machinery. Nature 440(7084), 631–636 (2006)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America 99(12), 7821–7826 (2002a)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. National. Academy of Science 99, 7821–7826 (2002b)
Ho, Y., et al.: Systematic identification of protein complexes in saccharomyces cerevisiae by mass spectrometry. Nature 415(6868), 180–183 (2002)
Krogan, N.J., et al.: Global landscape of protein complexes in the yeast saccharomyces cerevisiae. Nature 440(7084), 637–643 (2006)
Lambiotte, R.: Multi-scale Modularity in Complex Networks. In: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, pp. 546–553 (2010)
Lancichinetti, A., Fortunato, S.: Community detection algorithms: A comparative analysis. Phys. Rev. E 80, 56117 (2009)
Lewis, A., et al.: The function of communities in protein interaction networks at multiple scales. BMC Syst Biol. 4, 100 (2010)
Li, X., et al.: Computational approaches for detecting protein complexes from protein interaction networks: a survey. BMC Genomics, 11(suppl. 1), S3+ (2010)
Mewes, H.W., et al.: MIPS: a database for genomes and protein sequences. Nucleic Acids Res. 30, 31–34 (2002)
Nepusz, T., et al.: Detecting overlapping protein complexes in protein-protein interaction networks. Nature Methods (2012)
Pu, S., et al.: Identifying functional modules in the physical interactome of Saccharomyces cerevisiae. Proteomics 7(6), 944–960 (2007)
Ronhovde, P., Nussinov, Z.: Multiresolution community detection for megascale networks by information-based replica correlations. Physical Review E, 80(1), 016109+ (2009)
Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences of the United States of America 105(4), 1118–1123 (2008)
Stark, C., et al.: Biogrid: a general repository for interaction datasets. Nucleic Acids Research 34(Database-Issue), 535–539 (2006)
Uetz, P., et al.: A comprehensive analysis of protein-protein interactions in saccharomyces cerevisiae. Nature 403(6770), 623–627 (2000)
Van Dongen, S.: Graph Clustering Via a Discrete Uncoupling Process. SIAM Journal on Matrix Analysis and Applications 30(1), 121–141 (2008)
van Laarhoven, T., Marchiori, E.: Graph clustering with local search optimization: does the objective function matter? (submitted, 2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Laarhoven, T., Marchiori, E. (2012). Robust Community Detection Methods with Resolution Parameter for Complex Detection in Protein Protein Interaction Networks. In: Shibuya, T., Kashima, H., Sese, J., Ahmad, S. (eds) Pattern Recognition in Bioinformatics. PRIB 2012. Lecture Notes in Computer Science(), vol 7632. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34123-6_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-34123-6_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34122-9
Online ISBN: 978-3-642-34123-6
eBook Packages: Computer ScienceComputer Science (R0)