Modeling and designing real-world networks. (English) Zbl 1248.05192
Lerner, Jürgen (ed.) et al., Algorithmics of large and complex networks. Design, analysis, and simulation. Berlin: Springer (ISBN 978-3-642-02093-3/pbk). Lecture Notes in Computer Science 5515, 359-379 (2009).
Summary: In the last 10 years a new interest in so-called real-world graph structures has developed. Since the structure of a network is crucial for the processes on top of it a well-defined network model is needed for simulations and other kinds of experiments. Thus, given an observable network structure, models try to explain how they could have evolved. But sometimes also the opposite question is important: Given a system with specific constraints, what kind of rules will lead to a network with the specified structure? This overview article discusses first different real-world networks and their structures that have been analyzed in the last decade and models that explain how these structures can emerge. This chapter concentrates on those structures and models that are very simple and can likely be included into technical networks such as P2P-networks or sensor networks. In the second part we will then discuss how difficult it is to design local network generating rules that lead to a globally satisfying network structure.
For the entire collection see [Zbl 1165.68015].
For the entire collection see [Zbl 1165.68015].
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
Keywords:
real-; P2P networks; sensor networks; world graph structures; real-world networks; network evolutionReferences:
| [1] | Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Review of Modern Physics 74, 47–97 (2002) · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47 |
| [2] | Albert, R., Jeong, H., Barabási, A.-L.: Error and attack tolerance of complex networks. Nature 406, 378–382 (2000) · doi:10.1038/35019019 |
| [3] | Alon, U.: An Introduction to Systems Biology: Design Principles of Biological Circuits. Chapman & Hall/CRC, Boca Raton (2006) · Zbl 1141.92002 |
| [4] | Andersen, R., Chung, F., Lu, L.: Analyzing the small world phenomenon using a hybrid model with local network flow. In: Leonardi, S. (ed.) WAW 2004. LNCS, vol. 3243, pp. 19–30. Springer, Heidelberg (2004) · Zbl 1109.68321 · doi:10.1007/978-3-540-30216-2_2 |
| [5] | Barabási, A.-L.: Linked - The New Science of Network. Perseus, Cambridge (2002) |
| [6] | Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999) · Zbl 1226.05223 · doi:10.1126/science.286.5439.509 |
| [7] | Baumann, N., Stiller, S.: Network Models. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS, vol. 3418, pp. 341–372. Springer, Heidelberg (2005) · Zbl 1118.68310 · doi:10.1007/978-3-540-31955-9_13 |
| [8] | Berners-Lee, T., Hall, W., Hendler, J.A., O’Hara, K., Shadbolt, N., Weitzner, D.J.: A framework for web science. Foundations and Trends in Web Science 1(1), 1–130 (2006) · Zbl 1143.68318 · doi:10.1561/1800000001 |
| [9] | Bollobás, B.: Random Graphs, 2nd edn. Cambridge Studies in Advanced Mathematics, vol. 73. Cambridge University Press, London (2001) · Zbl 0979.05003 · doi:10.1017/CBO9780511814068 |
| [10] | Bollobás, B., Riordan, O.M.: Mathematical results on scale-free random graphs. In: Handbook of Graphs and Networks, pp. 1–34. Springer, Heidelberg (2003) · Zbl 1062.05080 |
| [11] | Bollobás, B., Riordan, O.M.: The diameter of a scale–free random graph. Combinatorica 24(1), 5–34 (2004) · Zbl 1047.05038 · doi:10.1007/s00493-004-0002-2 |
| [12] | Bornholdt, S., Schuster, H.G. (eds.): Handbook of Graphs and Networks. Wiley-VCH, Weinheim (2003) · Zbl 1044.90002 |
| [13] | Brandes, U., Erlebach, T. (eds.): Network Analysis - Methodological Foundations. Springer, Heidelberg (2005) · Zbl 1069.68001 |
| [14] | Chung, F., Lu, L.: The small world phenomenon in hybrid power law graphs. In: Ben-Naim, E., Frauenfelder, H., Toroczkai, Z. (eds.) Complex Networks, pp. 91–106 (2004) · Zbl 1080.05085 · doi:10.1007/978-3-540-44485-5_4 |
| [15] | Chung, F., Lu, L.: Complex Graphs and Networks. American Mathematical Society, Providence (2006) · Zbl 1114.90071 · doi:10.1090/cbms/107 |
| [16] | Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Physical Review E 70, 066111 (2004) · doi:10.1103/PhysRevE.70.066111 |
| [17] | Clauset, A., Shalizi, C.R., Newman, M.E.J.: Power–law distributions in empirical data. ArXiv (June 2007) · Zbl 1176.62001 |
| [18] | Dorogovtsev, S.N., Mendes, J.F.F.: Evolution of Networks. Oxford University Press, Oxford (2003) · Zbl 1109.68537 · doi:10.1093/acprof:oso/9780198515906.001.0001 |
| [19] | Erdos, P., Rényi, A.: On random graphs. Publicationes Mathematicae 6, 290–297 (1959) · Zbl 0092.15705 |
| [20] | Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. Computer Communications Review 29, 251–262 (1999) · Zbl 0889.68050 · doi:10.1145/316194.316229 |
| [21] | Ferrante, A., Pandurangan, G., Park, K.: On the hardness of optimization in power-law graphs. Theor. Comput. Sci. 393(1-3), 220–230 (2008) · Zbl 1135.68512 · doi:10.1016/j.tcs.2007.12.007 |
| [22] | Gilbert, E.N.: Random graphs. Anual Math. Statist. 30, 1141–1144 (1959) · Zbl 0168.40801 · doi:10.1214/aoms/1177706098 |
| [23] | Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 7821–7826 (2002) · Zbl 1032.91716 · doi:10.1073/pnas.122653799 |
| [24] | Jansen, T., Theile, M.: Stability in the self-organized evolution of networks. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, pp. 931–938 (2007) · Zbl 1181.90054 · doi:10.1145/1276958.1277147 |
| [25] | Kleinberg, J.: Navigation in a small world. Nature 406, 845 (2000) · Zbl 1296.05181 · doi:10.1038/35022643 |
| [26] | Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 163–170 (2000) · Zbl 1296.05181 · doi:10.1145/335305.335325 |
| [27] | Lehmann, K.A., Kaufmann, M.: Evolutionary algorithms for the self-organized evolution of networks. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2005), pp. 563–570 (2005) · doi:10.1145/1068009.1068105 |
| [28] | Lehmann, K.A., Kaufmann, M.: Random Graphs, Small Worlds and Scale-Free Networks. In: Steinmetz, R., Wehrle, K. (eds.) Peer-to-Peer Systems and Applications. LNCS, vol. 3485, pp. 57–76. Springer, Heidelberg (2005) · doi:10.1007/11530657_6 |
| [29] | Lehmann, K.A., Post, H.D., Kaufmann, M.: Hybrid graphs as a framework for the small-world effect. Physical Review E 73, 056108 (2006) · doi:10.1103/PhysRevE.73.056108 |
| [30] | Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: Densification laws, shrinking diameters, and possible explanations. In: Proceedings of the 11th ACM SIGKDD (2005) · doi:10.1145/1081870.1081893 |
| [31] | Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD) 1(1, 2) (2007) |
| [32] | Liljeros, F.: Sexual networks in contemporary western societies. Physica A 338, 238–245 (2004) · doi:10.1016/j.physa.2004.02.046 |
| [33] | Liljeros, F., Edling, C.R., Amaral, L.A.N., Stanley, H.E., Åberg, Y.: The web of human sexual contacts. . Nature 411, 907–908 (2001) · doi:10.1038/35082140 |
| [34] | Lotka, A.: The frequency distribution of scientific productivity. Journal of the Washington Academy of Sciences 16, 317–323 (1926) |
| [35] | Milo, R., Itzkovitz, S., Kashtan, N., Levitt, R., Shen-Orr, S., Ayzenshtat, I., Sheffer, M., Alon, U.: Superfamilies of evolved and designed networks. Science 303, 1538–1542 (2004) · doi:10.1126/science.1089167 |
| [36] | Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: Simple building blocks of complex networks. Science 298, 824–827 (2002) · doi:10.1126/science.298.5594.824 |
| [37] | Mark, E.J.: The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences 98(2), 404–409 (2001) · Zbl 1065.00518 · doi:10.1073/pnas.98.2.404 |
| [38] | Newman, M.E.J., Barabási, A.-L., Watts, D.J. (eds.): The Structure and Dynamics of Networks. Princeton University Press, Princeton (2006) · Zbl 1362.00042 |
| [39] | Nunkesser, M., Sawitzki, D.: Blockmodels. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS, vol. 3418, pp. 253–292. Springer, Heidelberg (2005) · Zbl 1118.68343 · doi:10.1007/978-3-540-31955-9_10 |
| [40] | Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005) · doi:10.1038/nature03607 |
| [41] | Pastor-Satorras, R., Vespignani, A.: Epidemic spreading in scale-free networks. Physical Review Letters 86(4), 3200–3203 (2001) · doi:10.1103/PhysRevLett.86.3200 |
| [42] | Robins, G., Pattison, P., Kalish, Y., Lusher, D.: An introduction to exponential random graph (p *) models for social networks. Social Networks 29, 173–191 (2007) · doi:10.1016/j.socnet.2006.08.002 |
| [43] | Robins, G., Snijder, T., Wang, P., Handcock, M., Pattison, P.: Recent developments in exponential random graph (p *) models for social networks. Social Networks 29, 192–215 (2007) · doi:10.1016/j.socnet.2006.08.003 |
| [44] | Song, C., Havlin, S., Makse, H.A.: Origins of fractality in the growth of complex networks. Nature 2, 275–281 (2006) |
| [45] | Walsh, T.: Search in a small world. In: Proceedings of the IJCAI 1999 (1999) |
| [46] | Wasserman, S., Faust, K.: Social Network Analysis - Methods and Applications, revised, reprinted edn. Cambridge University Press, Cambridge (1999) |
| [47] | Watts, D.J.: Small Worlds- The Dynamics of Networks between Order and Randomness. Princeton Studies in Complexity. Princeton University Press, Princeton (1999) |
| [48] | Watts, D.J., Strogatz, S.H.: Collective dynamics of ’small-world’ networks. Nature 393, 440–442 (1998) · Zbl 1368.05139 · doi:10.1038/30918 |
| [49] | Zweig, K.A.: On Local Behavior and Global Structures in the Evolution of Complex Networks. Ph.D thesis, University of Tübingen, Wilhelm-Schickard-Institut für Informatik (2007) |
| [50] | Zweig, K.A., Zimmermann, K.: Wanderer between the worlds – self-organized network stability in attack and random failure scenarios. In: Proceedings of the 2nd IEEE SASO (2008) · doi:10.1109/SASO.2008.35 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
