Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-09T06:21:10.222Z Has data issue: false hasContentIssue false
  • English
  • Français

The hourglass effect in hierarchical dependency networks

Published online by Cambridge University Press:  06 September 2017

KAESER M. SABRIN  and
CONSTANTINE DOVROLIS
KAESER M. SABRIN
Affiliation:
School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA (e-mail: [email protected], [email protected])
CONSTANTINE DOVROLIS
Affiliation:
School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA (e-mail: [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Many hierarchically modular systems are structured in a way that resembles an hourglass. This “hourglass effect” means that the system generates many outputs from many inputs through a relatively small number of intermediate modules that are critical for the operation of the entire system, referred to as the waist of the hourglass. We investigate the hourglass effect in general, not necessarily layered, hierarchical dependency networks. Our analysis focuses on the number of source-to-target dependency paths that traverse each vertex, and it identifies the core of a dependency network as the smallest set of vertices that collectively cover almost all dependency paths. We then examine if a given network exhibits the hourglass property or not, comparing its core size with a “flat” (i.e., non-hierarchical) network that preserves the source dependencies of each target in the original network. As a possible explanation for the hourglass effect, we propose the Reuse Preference model that captures the bias of new modules to reuse intermediate modules of similar complexity instead of connecting directly to sources or low complexity modules. We have applied the proposed framework in a diverse set of dependency networks from technological, natural, and information systems, showing that all these networks exhibit the general hourglass property but to a varying degree and with different waist characteristics.

Keywords

modularityhierarchyevolvabilityrobustnesscomplexitycentralitycore-peripherynetworkshourglass networksbow-tie networksdependency networks
Type
Research Article
Information
Network Science , Volume 5 , Issue 4 , December 2017 , pp. 490 - 528
Copyright
Copyright © Cambridge University Press 2017 

References

Akhshabi, S., & Dovrolis, C. (2011). The evolution of layered protocol stacks leads to an hourglass-shaped architecture. In ACM SIGCOMM Computer Communication Review, vol. 41, ACM, pp. 206–217.Google Scholar
Akhshabi, S., Sarda, S., Dovrolis, C., & Yi, S. (2014). An explanatory evo-devo model for the developmental hourglass. f1000research, 3 (156). doi: 10.12688/f1000research.4583.2.CrossRefGoogle ScholarPubMed
Alberts, B., Johnson, A., Lewis, J., Raff, M., Roberts, K., & Walter, P. (2002). Molecular biology of the cell (4th ed.). New York: Garland Science.Google Scholar
Baldwin, C. Y., & Clark, K. B. (2000). Design rules: The power of modularity. Vol. 1. Cambridge, MA: MIT Press.Google Scholar
Barabási, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286 (5439), 509–512.Google Scholar
Beutler, B. (2004). Inferences, questions and possibilities in toll-like receptor signalling. Nature, 430 (6996), 257–263.Google Scholar
Bhardwaj, N., Yan, K.-K., & Gerstein, M. B. (2010). Analysis of diverse regulatory networks in a hierarchical context shows consistent tendencies for collaboration in the middle levels. Proceedings of the National Academy of Sciences, 107 (15), 6841–6846.CrossRefGoogle Scholar
Bhattacharya, P., Iliofotou, M., Neamtiu, I., & Faloutsos, M. (2012). Graph-based analysis and prediction for software evolution. In Proceedings of the 2012 International Conference on Software Engineering, IEEE Press, pp. 419–429.Google Scholar
Borgatti, S. P., & Everett, M. G. (2000). Models of core/periphery structures. Social Networks, 21 (4), 375–395.CrossRefGoogle Scholar
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., . . . Wiener, J. (2000). Graph structure in the web. Computer Networks, 33 (1), 309–320.Google Scholar
Callebaut, W. & Rasskin-Gutman, D. (2005). Modularity: Understanding the Development and Evolution of Natural Complex Systems. Cambridge, MA: MIT Press.Google Scholar
Capocci, A., Servedio, V., Colaiori, F., Buriol, L. S., Donato, D., Leonardi, S., & Caldarelli, G. (2006). Preferential attachment in the growth of social networks: The Internet encyclopedia Wikipedia. Physical Review E, 74 (3), 036116.CrossRefGoogle ScholarPubMed
Casci, T. (2011). Development: Hourglass theory gets molecular approval. Nature Reviews Genetics, 12 (2), 76–76.Google Scholar
Clune, J., Mouret, J.-B., & Lipson, H. (2013). The evolutionary origins of modularity. Proceedings of the Royal Society of London B: Biological Sciences, 280 (1755), 20122863.Google Scholar
Corominas-Murtra, B., Goñi, J., Solé, R., & Rodríguez-Caso, C. (2013). On the origins of hierarchy in complex networks. Proceedings of the National Academy of Sciences, 110 (33), 13316–13321.Google Scholar
Csermely, P., London, A., Wu, L.-Y., & Uzzi, B. (2013). Structure and dynamics of core/periphery networks. Journal of Complex Networks, 1 (2), 93–123.CrossRefGoogle Scholar
Csete, M., & Doyle, J. (2004). Bow ties, metabolism and disease. TRENDS in Biotechnology, 22 (9), 446–450.Google Scholar
Domazet-Lošo, T., & Tautz, D. (2010). A phylogenetically based transcriptome age index mirrors ontogenetic divergence patterns. Nature, 468 (7325), 815–818.Google Scholar
Easley, D., & Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge: Cambridge University Press.Google Scholar
Fortuna, M. A., Bonachela, J. A., & Levin, S. A. (2011). Evolution of a modular software network. Proceedings of the National Academy of Sciences, 108 (50), 19985–19989.Google Scholar
Fowler, J. H., & Jeon, S. (2008). The authority of supreme court precedent. Social Networks, 30 (1), 16–30.Google Scholar
Fowler, J. H., Johnson, T. R., Spriggs, J. F., Jeon, S., & Wahlbeck, P. J. (2007). Network analysis and the law: Measuring the legal importance of precedents at the us supreme court. Political Analysis, 15 (3), 324–346.CrossRefGoogle Scholar
Friedlander, T., Mayo, A. E., Tlusty, T., & Alon, U. (2015). Evolution of bow-tie architectures in biology. PLoS Computational Biology, 11 (3), e1004055.CrossRefGoogle ScholarPubMed
Gorman, M. (2015). Codeviz: A callgraph visualiser. Available at: http://www.csn.ul.ie/~mel/projects/codeviz/.Google Scholar
Gousios, G. (2015). java-callgraph: Java call graph utilities. Available at: https://github.com/gousiosg/java-callgraph.Google Scholar
Hinton, G. E., & Salakhutdinov, R. R. (2006). Reducing the dimensionality of data with neural networks. Science, 313 (5786), 504–507.CrossRefGoogle ScholarPubMed
Holme, P. (2005). Core-periphery organization of complex networks. Physical Review E, 72 (4), 046111.Google Scholar
Huang, C.-C., & Kusiak, A. (1998). Modularity in design of products and systems. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 28 (1), 66–77.CrossRefGoogle Scholar
Ishakian, V., Erdös, D., Terzi, E., & Bestavros, A. (2012). A framework for the evaluation and management of network centrality. In Sdm, SIAM, pp. 427–438.Google Scholar
Jain, S., & Krishna, S. (2002). Large extinctions in an evolutionary model: The role of innovation and keystone species. Proceedings of the National Academy of Sciences, 99 (4), 2055–2060.Google Scholar
Kanehisa, M., & Goto, S. (2000). Kegg: Kyoto encyclopedia of genes and genomes. Nucleic Acids Research, 28 (1), 27–30.Google Scholar
Kanehisa, M., Goto, S., Sato, Y., Kawashima, M., Furumichi, M., & Tanabe, M. (2014). Data, information, knowledge and principle: Back to metabolism in kegg. Nucleic Acids Research, 42 (D1), D199–D205.Google Scholar
Kashtan, N., & Alon, U. (2005). Spontaneous evolution of modularity and network motifs. Proceedings of the National Academy of Sciences of the United States of America, 102 (39), 13773–13778.Google Scholar
Kashtan, N., Noor, E., & Alon, U. (2007). Varying environments can speed up evolution. Proceedings of the National Academy of Sciences, 104 (34), 13711–13716.CrossRefGoogle ScholarPubMed
Kirschner, M., & Gerhart, J. (1998). Evolvability. Proceedings of the National Academy of Sciences, 95 (15), 8420–8427.Google Scholar
Kirsten, H., & Hogeweg, P. (2011). Evolution of networks for body plan patterning; interplay of modularity, robustness and evolvability. PLoS Computational Biology, 7 (10), e1002208.Google Scholar
Kitano, H. (2004). Biological robustness. Nature Reviews Genetics, 5 (11), 826–837.Google Scholar
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. S. (1999). The web as a graph: Measurements, models, and methods. In International Computing and Combinatorics Conference. Lecture Notes in Computer Science book series, vol. 1627. Springer, pp. 1–17.Google Scholar
Krapivsky, P. L., & Redner, S. (2005). Network growth by copying. Physical Review E, 71 (3), 036118.Google Scholar
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tompkins, A., & Upfal, E. (2000). The web as a graph. In Proceedings of the 19th ACM sigmod-sigact-sigart Symposium on Principles of Database Systems, ACM.Google Scholar
Legal Information Institute, Cornell University Law School. (2015). Historic Supreme Court Decisions. Available at: https://www.law.cornell.edu/. Accessed: 2015-10-30.Google Scholar
Lorenz, D. M., Jeng, A., & Deem, M. W. (2011). The emergence of modularity in biological systems. Physics of Life Reviews, 8 (2), 129–160.Google ScholarPubMed
Ma, H.-W., & Zeng, A.-P. (2003). The connectivity structure, giant strong component and centrality of metabolic networks. Bioinformatics, 19 (11), 1423–1430.Google Scholar
Mengistu, H., Huizinga, J., Mouret, J. B., & Clune, J. (2016). The evolutionary origins of hierarchy. PLoS Computational Biology, 12 (6), e1004829.Google Scholar
Meunier, D., Lambiotte, R., & Bullmore, E. T. (2010). Modular and hierarchically modular organization of brain networks. Frontiers in Neuroscience, 4, 200. doi: 10.3389/fnins.2010.00200.Google Scholar
Mihm, J., Loch, C. H., Wilkinson, D., & Huberman, B. A. (2010). Hierarchical structure and search in complex organizations. Management Science, 56 (5), 831–848.Google Scholar
Myers, C. R. (2003). Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs. Physical Review E, 68 (4), 046116.Google Scholar
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14 (1), 265–294.Google Scholar
Newman, M. (2010). Networks: An Introduction. Oxford, UK: Oxford University Press.Google Scholar
Newman, M. E. J., Forrest, S., & Balthrop, J. (2002). Email networks and the spread of computer viruses. Physical Review E, 66 (3), 035101.Google Scholar
Oda, K., & Kitano, H. (2006). A comprehensive map of the toll-like receptor signaling network. Molecular Systems Biology, 2, 2006.0015. doi: 10.1038/msb4100057.Google Scholar
Palsson, B. O. (2015). Systems Biology. Cambridge: Cambridge University Press.Google Scholar
Parnas, D. L., Clements, P. C., & Weiss, D. M. (1984). The modular structure of complex systems. In Proceedings of the 7th International Conference on Software Engineering, IEEE Press, pp. 408–417.Google Scholar
Quint, M., Drost, H.-G., Gabel, A., Ullrich, K. K., Bönn, M., & Grosse, I. (2012). A transcriptomic hourglass in plant embryogenesis. Nature, 490 (7418), 98–101.Google Scholar
Quiroga, R. Q., Reddy, L., Kreiman, G., Koch, C., & Fried, I. (2005). Invariant visual representation by single neurons in the human brain. Nature, 435 (7045), 1102–1107.CrossRefGoogle ScholarPubMed
Ravasz, E., & Barabási, A.-L. (2003). Hierarchical organization in complex networks. Physical Review E, 67 (2), 026112.Google Scholar
Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barabási, A.-L. (2002). Hierarchical organization of modularity in metabolic networks. Science, 297 (5586), 1551–1555.Google Scholar
Ravindra, K. A., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Englewood Cliffs, NJ: Prentice Hall.Google Scholar
Rexford, J., & Dovrolis, C. (2010). Future internet architecture: clean-slate versus evolutionary research. Communications of the ACM, 53 (9), 36–40.Google Scholar
Riesenhuber, M., & Poggio, T. (1999). Hierarchical models of object recognition in cortex. Nature Neuroscience, 2 (11), 1019–1025.Google Scholar
Rombach, M. P., Porter, M. A., Fowler, J. H., & Mucha, P. J. (2014). Core-periphery structure in networks. SIAM Journal on Applied Mathematics, 74 (1), 167–190.Google Scholar
Saito, H., Toyoda, M., Kitsuregawa, M., & Aihara, K. (2007). A large-scale study of link spam detection by graph algorithms. In Proceedings of the 3rd International Workshop on Adversarial Information Retrieval on the Web, ACM, pp. 45–48.Google Scholar
Sales-Pardo, M., Guimera, R., Moreira, A. A., & Amaral, L. A. N. (2007). Extracting the hierarchical organization of complex systems. Proceedings of the National Academy of Sciences, 104 (39), 15224–15229.Google Scholar
Schilling, M. A. (2000). Toward a general modular systems theory and its application to interfirm product modularity. Academy of Management Review, 25 (2), 312–334.Google Scholar
Simon, H. A. (1991). The architecture of complexity. In Facets of Systems Science. New York: Springer US, pp. 457–476.Google Scholar
Siyari, P., Dilkina, B., & Dovrolis, C. (2016). Lexis: An optimization framework for discovering the hierarchical structure of sequential data. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD '16, New York, NY, USA: ACM, pp. 1185–1194.Google Scholar
Smolke, C. (2009). The metabolic pathway engineering handbook: Tools and applications, Vol. 2. Boca Raton, FL: CRC Press.Google Scholar
Stelling, J., Sauer, U., Szallasi, Z., Doyle, F., & Doyle, J. (2004). Robustness of cellular functions. Cell, 118 (6), 675–685.Google Scholar
Supper, J., Spangenberg, L., Planatscher, H., Dräger, A., Schröder, A., & Zell, A. (2009). Bowtiebuilder: Modeling signal transduction pathways. BMC Systems Biology, 3 (1), 1.Google Scholar
Swaminathan, J. M., Smith, S. F., & Sadeh, N. M. (1998). Modeling supply chain dynamics: A multiagent approach. Decision Sciences, 29 (3), 607–632.Google Scholar
Tanaka, R., Csete, M., & Doyle, J. (2005). Highly optimised global organisation of metabolic networks. IEE Proceedings-Systems Biology, 152 (4), 179–184.Google Scholar
Tarjan, R. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1 (2), 146–160.Google Scholar
Valverde, S., & Solé, R. V. (2007). Self-organization versus hierarchy in open-source social networks. Physical Review E, 76 (4), 046118.Google Scholar
Vitali, S., Glattfelder, J. B., & Battiston, S. (2011). The network of global corporate control. PloS One, 6 (10), e25995.Google Scholar
Wagner, G. P., Pavlicev, M., & Cheverud, J. M. (2007). The road to modularity. Nature Reviews Genetics, 8 (12), 921–931.Google Scholar
Yan, K.-K., Fang, G., Bhardwaj, N., Alexander, R. P., & Gerstein, M. (2010). Comparing genomes to computer operating systems in terms of the topology and evolution of their regulatory control networks. Proceedings of the National Academy of Sciences, 107 (20), 9186–9191.Google Scholar
Yu, H., & Gerstein, M. (2006). Genomic analysis of the hierarchical structure of regulatory networks. Proceedings of the National Academy of Sciences, 103 (40), 14724–14731.Google Scholar
Yu, H., Kim, P. M., Sprecher, E., Trifonov, V., & Gerstein, M. (2007). The importance of bottlenecks in protein networks: Correlation with gene essentiality and expression dynamics. PLoS Computational Biology, 3 (4), e59.Google Scholar
Zhao, J., Yu, H., Luo, Jian-Hua, Cao, Zhi-Wei, & Li, Yi-Xue. (2006). Hierarchical modularity of nested bow-ties in metabolic networks. BMC Bioinformatics, 7 (1), 386.Google Scholar