{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:54:20Z","timestamp":1742403260490},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2004,11,22]],"date-time":"2004-11-22T00:00:00Z","timestamp":1101081600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2004,11,22]],"date-time":"2004-11-22T00:00:00Z","timestamp":1101081600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                        <jats:title>Background<\/jats:title>\n                        <jats:p>Recent genomic and bioinformatic advances have motivated the development of numerous network models intending to describe graphs of biological, technological, and sociological origin. In most cases the success of a model has been evaluated by how well it reproduces a few key features of the real-world data, such as degree distributions, mean geodesic lengths, and clustering coefficients. Often pairs of models can reproduce these features with indistinguishable fidelity despite being generated by vastly different mechanisms. In such cases, these few target features are insufficient to distinguish which of the different models best describes real world networks of interest; moreover, it is not clear a priori that <jats:italic>any<\/jats:italic> of the presently-existing algorithms for network generation offers a predictive description of the networks inspiring them.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>We present a method to assess systematically which of a set of proposed network generation algorithms gives the most accurate description of a given biological network. To derive discriminative classifiers, we construct a mapping from the set of all graphs to a high-dimensional (in principle infinite-dimensional) \"word space\". This map defines an input space for classification schemes which allow us to state unambiguously which models are most descriptive of a given network of interest. Our training sets include networks generated from 17 models either drawn from the literature or introduced in this work. We show that different duplication-mutation schemes best describe the <jats:italic>E. coli<\/jats:italic> genetic network, the <jats:italic>S. cerevisiae<\/jats:italic> protein interaction network, and the <jats:italic>C. elegans<\/jats:italic> neuronal network, out of a set of network models including a linear preferential attachment model and a small-world model.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusions<\/jats:title>\n                        <jats:p>Our method is a first step towards systematizing network models and assessing their predictability, and we anticipate its usefulness for a number of communities.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-5-181","type":"journal-article","created":{"date-parts":[[2005,1,13]],"date-time":"2005-01-13T00:25:30Z","timestamp":1105575930000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Discriminative topological features reveal biological network mechanisms"],"prefix":"10.1186","volume":"5","author":[{"given":"Manuel","family":"Middendorf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Etay","family":"Ziv","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carter","family":"Adams","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jen","family":"Hom","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robin","family":"Koytcheff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chaya","family":"Levovitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory","family":"Woods","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Linda","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chris","family":"Wiggins","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2004,11,22]]},"reference":[{"key":"297_CR1","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/316194.316229","volume":"29","author":"C Faloutsos","year":"1999","unstructured":"Faloutsos C, Faloutsos M, Faloutsos P: On power-law relationships of the internet topology.\n                           Computer Communications Review 1999, 29: 251\u2013262. 10.1145\/316194.316229","journal-title":"Computer Communications Review"},{"key":"297_CR2","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1038\/43601","volume":"401","author":"R Albert","year":"1999","unstructured":"Albert R, Jeong H, Barab\u00e1si AL: Diameter of the world-wide web.\n                           Nature 1999, 401: 130\u2013131. 10.1038\/43601","journal-title":"Nature"},{"key":"297_CR3","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"M Newman","year":"2003","unstructured":"Newman M: The Structure and Function of Complex Networks.\n                           SIAM 2003, 45: 167.","journal-title":"SIAM"},{"key":"297_CR4","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo R, Shen-Orr SS, Itzkovitz S, Kashtan N, Alon U: Simple building blocks of complex networks.\n                           Science 2002, 298: 824\u20137. 10.1126\/science.298.5594.824","journal-title":"Science"},{"key":"297_CR5","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1038\/ng1242","volume":"35","author":"S Wuchty","year":"2003","unstructured":"Wuchty S, Oltvai ZN, Barab\u00e1si AL: Evolutionary conservation of motif constituents in the yeast protein interaction network.\n                           Nat gen 2003, 35: 176\u20139. 10.1038\/ng1242","journal-title":"Nat gen"},{"key":"297_CR6","volume-title":"arXiv:cond-mat\/0306610","author":"E Ziv","year":"2003","unstructured":"Ziv E, Koytcheff R, Wiggins CH: Novel systematic discovery of statistically significant network features.\n                           arXiv:cond-mat\/0306610 2003."},{"key":"297_CR7","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1126\/science.1099334","volume":"305","author":"Y Artzy-Randrup","year":"2004","unstructured":"Artzy-Randrup Y, Fleishman SJ, Ben-Tal N, Stone L: Comment on \"Network Motifs: Simple Building Blocks of Complex Networks\" and \"Superfamilies of Evolved and Designed Networks\".\n                           Science 2004, 305: 1107. 10.1126\/science.1099334","journal-title":"Science"},{"key":"297_CR8","doi-asserted-by":"publisher","first-page":"1107d","DOI":"10.1126\/science.1100519","volume":"305","author":"R Milo","year":"2004","unstructured":"Milo R, Itzkovitz S, Kashtan N, Levitt R, Alon U: Response to Comment on \"Network Motifs: Simple Building Blocks of Complex Networks\" and \"Superfamilies of Evolved and Designed Networks\".\n                           Science 2004, 305: 1107d. 10.1126\/science.1100519","journal-title":"Science"},{"key":"297_CR9","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1126\/science.1089167","volume":"303","author":"R Milo","year":"2004","unstructured":"Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U: Superfamilies of evolved and designed networks.\n                           Science 2004, 303: 1538. 10.1126\/science.1089167","journal-title":"Science"},{"key":"297_CR10","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1038\/ng881","volume":"31","author":"S Shen-Orr","year":"2002","unstructured":"Shen-Orr S, Milo R, Mangan S, Alon U: Network motifs in the transcriptional regulation network of Escherichia coli.\n                           Nature Genetics 2002, 31: 64\u201368. 10.1038\/ng881","journal-title":"Nature Genetics"},{"key":"297_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1038\/35075138","volume":"411","author":"H Jeong","year":"2001","unstructured":"Jeong H, Mason S, Barab\u00e1si A, Oltvai ZN: Lethality and centrality of protein networks.\n                           Nature 2001, 411: 41\u201342. 10.1038\/35075138","journal-title":"Nature"},{"key":"297_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1098\/rstb.1986.0056","volume":"314","author":"JG White","year":"1986","unstructured":"White JG, Southgate E, Thompson JN, Brenner S: The structure of the nervous system of the nematode C. elegans.\n                           Phil Trans of the Royal Society of London 1986, 314: 1\u2013340.","journal-title":"Phil Trans of the Royal Society of London"},{"key":"297_CR13","volume-title":"In Symposium on Foundations of Computer Science FOCS, IEEE","author":"R Kumar","year":"2000","unstructured":"Kumar R, Raghavan P, Rajagopalan S, Sivakumar D: Stochastic models for the web graph.\n                           In Symposium on Foundations of Computer Science FOCS, IEEE 2000."},{"key":"297_CR14","unstructured":"[http:\/\/www.columbia.edu\/itc\/applied\/wiggins\/netclass]"},{"key":"297_CR15","doi-asserted-by":"crossref","unstructured":"Sole RV, Pastor-Satorras R, Smith E, Kepler TB: A model of large-scale proteome evolution.\n                           Advances in Complex Systems 2002., 5(43):","DOI":"10.1142\/S021952590200047X"},{"key":"297_CR16","doi-asserted-by":"crossref","unstructured":"Vazquez A, Flammini A, Maritan A, Vespignani A: Modeling of protein interaction networks.\n                           ComPlexUs 2003., 1(38):","DOI":"10.1159\/000067642"},{"key":"297_CR17","doi-asserted-by":"publisher","first-page":"066702","DOI":"10.1103\/PhysRevE.66.066702","volume":"66","author":"P Grindrod","year":"2002","unstructured":"Grindrod P: Range-Dependent Random Graphs and their application to modeling large small-world proteome datasets.\n                           Phys Rev E Stat Nonlin Soft Matter Phys 2002, 66: 066702. 10.1103\/PhysRevE.66.066702","journal-title":"Phys Rev E Stat Nonlin Soft Matter Phys"},{"key":"297_CR18","doi-asserted-by":"publisher","first-page":"5401","DOI":"10.1103\/PhysRevLett.86.5401","volume":"86","author":"PL Krapivsky","year":"2001","unstructured":"Krapivsky PL, Rodgers GJ, Redner S: Degree distributions of growing networks.\n                           Phys Rev Lett 2001, 86: 5401\u20135404. 10.1103\/PhysRevLett.86.5401","journal-title":"Phys Rev Lett"},{"key":"297_CR19","volume-title":"arXiv:cond-mat\/0307184","author":"DH Kim","year":"2003","unstructured":"Kim DH, Kahng B, Kim D: The q-component static model: modeling social networks.\n                           arXiv:cond-mat\/0307184 2003."},{"key":"297_CR20","doi-asserted-by":"publisher","first-page":"278701","DOI":"10.1103\/PhysRevLett.87.278701","volume":"87","author":"KI Goh","year":"2001","unstructured":"Goh KI, Kahng B, Kim D: Universal behavior of load distribution in scale-free networks.\n                           Phys Rev Lett 2001, 87: 278701. 10.1103\/PhysRevLett.87.278701","journal-title":"Phys Rev Lett"},{"key":"297_CR21","doi-asserted-by":"publisher","first-page":"258702","DOI":"10.1103\/PhysRevLett.89.258702","volume":"89","author":"G Caldarelli","year":"2002","unstructured":"Caldarelli G, Capocci A, Rios PDL, Munoz AM: Scale-free networks from varying vertex intrinsic fitness.\n                           Phys Rev Lett 2002, 89: 258702. 10.1103\/PhysRevLett.89.258702","journal-title":"Phys Rev Lett"},{"key":"297_CR22","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1038\/30918","volume":"393","author":"D Watts","year":"1998","unstructured":"Watts D, Strogatz S: Collective dynamics of small-world networks.\n                           Nature 1998, 393: 202\u2013204. 10.1038\/30918","journal-title":"Nature"},{"key":"297_CR23","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s P, R\u00e9nyi A: On random graphs.\n                           Publicationes Mathematicae 1959, 6: 290\u2013297.","journal-title":"Publicationes Mathematicae"},{"key":"297_CR24","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1209\/epl\/i2001-00260-6","volume":"54","author":"G Bianconi","year":"2001","unstructured":"Bianconi G, Barab\u00e1si A: Competition and multiscaling in evolving networks.\n                           Europhys Lett 2001, 54: 436\u2013442. 10.1209\/epl\/i2001-00260-6","journal-title":"Europhys Lett"},{"key":"297_CR25","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si A: Emergence of scaling in random networks.\n                           Science 1999, 286: 509\u2013512. 10.1126\/science.286.5439.509","journal-title":"Science"},{"key":"297_CR26","doi-asserted-by":"publisher","first-page":"041902","DOI":"10.1103\/PhysRevE.64.041902","volume":"64","author":"D Callaway","year":"2001","unstructured":"Callaway D, Hopcroft JE, Kleinberg JM, Newman ME, Strogatz SH: Are randomly grown graphs really random?\n                           Phys Rev E Stat Nonlin Soft Matter Phys 2001, 64: 041902. 10.1103\/PhysRevE.64.041902","journal-title":"Phys Rev E Stat Nonlin Soft Matter Phys"},{"key":"297_CR27","volume-title":"Mathematics Research Report 14, University of Strathclyde","author":"JD Higham","year":"2003","unstructured":"Higham JD: Spectral Reordering of a Range-Dependent Weighted Random Graph.\n                           Mathematics Research Report 14, University of Strathclyde 2003."},{"key":"297_CR28","volume-title":"arXiv:cond-mat\/0006132","author":"A Vazquez","year":"2002","unstructured":"Vazquez A: Knowing a network by walking on it: emergence of scaling.\n                           arXiv:cond-mat\/0006132 2002."},{"key":"297_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2440-0","volume-title":"The Nature of Statistical Learning Theory","author":"V Vapnik","year":"1995","unstructured":"Vapnik V: The Nature of Statistical Learning Theory. Springer-Verlag, NY, USA; 1995."},{"key":"297_CR30","volume-title":"In Advances in Kernel Methods \u2013 Support Vector Learning","author":"T Joachims","year":"1999","unstructured":"Joachims T: Making large-Scale SVM Learning Practical. In In Advances in Kernel Methods \u2013 Support Vector Learning. Edited by: Sch\u00f6lkopf B, Burges C, Smola A. MIT-Press; 1999."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-5-181.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-5-181\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-5-181.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:21:08Z","timestamp":1728303668000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-5-181"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11,22]]},"references-count":30,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2004,12]]}},"alternative-id":["297"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-5-181","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2004,11,22]]},"assertion":[{"value":"24 July 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2004","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2004","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"181"}}