zbMATH — the first resource for mathematics

Stability in the self-organized evolution of networks. (English) Zbl 1181.90054
Summary: The modeling and analysis of large networks of autonomous agents is an important topic with applications in many different disciplines. One way of modeling the development of such networks is by means of an evolutionary process. The autonomous and selfishly acting agents are randomly chosen to become active according to an underlying probability distribution. They may apply some kind of local mutation operator to the network and decide about accepting these changes via some fitness-based selection whereas the fitness models the agent’s preferences. This general framework for the self-organized evolution of networks can be instantiated in many different ways. For interesting instances, one would like to know whether stable topologies eventually evolve and how long this process may take. Here, known results for an instantiation based on random spanning trees and a fitness-based selection according to global graph centrality measures are improved. Moreover, a more natural and local fitness-based selection using only the information on nearest neighbors is presented and analyzed with respect to the expected time needed to reach a stable state.

90B15 Stochastic network models in operations research
91B69 Heterogeneous agent models
68T05 Learning and adaptive systems in artificial intelligence
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX Cite
Full Text: DOI
[1] Agnarsson, G., Deo, N., Micikevicis, P.: On the expected number of level-i-nodes in a random labeled tree. Bull. ICA 41, 51–60 (2004) · Zbl 1055.05029
[2] Anshelevich, E., Dasgupta, A., Tardos, E., Wexler, T.: Near-optimal network design with selfish agents. In: ACM Symposium on Theory of Computing (STOC’03), pp. 511–520 (2003) · Zbl 1192.68019
[3] Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: IEEE Symposium on Foundations of Computer Science (FOCS’04) (2004) · Zbl 1173.91321
[4] Bala, V., Goyal, S.: A noncooperative model of network formation. Econometrica 68, 1181–1230 (2000) · Zbl 1022.91047
[5] Brémaud, P.: Markov Chains, Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, Berlin (1998) · Zbl 0949.60009
[6] Entringer, R.C., Meir, A., Moon, J.W., Székely, L.: On the wiender index of trees from certain families. Australas. J. Combin. 10, 211–224 (1994) · Zbl 0824.05019
[7] Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.: On a network creation game. In: Symposium on Principles of Distributed Computing (PODC’03), pp. 347–351 (2003) · Zbl 1322.91013
[8] Fischermann, M., Hoffmann, A., Rautenbach, D., Szekely, L., Volkmann, L.: Wiener index versus maximum degree in trees. Discrete Appl. Math. 122, 127–137 (2002) · Zbl 0993.05061
[9] Garnier, J., Kallel, L., Schoenauer, M.: Rigorous hitting times for binary mutations. Evol. Comput. 7(2), 173–203 (1999) · Zbl 05412792
[10] Jansen, T., Theile, M.: Stability in the self-organized evolution of networks. In: Lipson, H. (ed.) Conference on Genetic and Evolutionary Computation (GECCO’07), pp. 931–938. Assoc. Comput. Mach., New York (2007) · Zbl 1181.90054
[11] Janson, S.: The wiener index of simply generated random trees. Random Struct. Algorithms 22(4), 337–358 (2003) · Zbl 1025.05021
[12] Jordan, M.E.C.: Sur les assemblages des lignes. J. Reine Angew. Math. 70, 185–190 (1869) · JFM 02.0344.01
[13] Lehmann, K., Kaufmann, M.: Evolutionary algorithms for the self-organized evolution of networks. In: Conference on Genetic and Evolutionary Computation (GECCO’05), pp. 563–570 (2005)
[14] Luczak, T.: The height of a random tree. Technical report, Adam Mickiewicz University (1993)
[15] Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005) · Zbl 1092.60001
[16] Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1997) · Zbl 0849.68039
[17] Papadimitriou, C.H.: Algorithms, games, and the Internet. In: ACM Symposium on Theory of Computing (STOC’01). Lecture Notes in Computer Science, vol. 2076, pp. 1–5. Springer, Berlin (2001)
[18] Prüfer, H.: Neuer Beweis eines Satzes über Permutationen. Archiv für Mathematik und Physik, pp. 142–144 (1918) · JFM 46.0106.04
[19] Renyi, A., Szekeres, G.: On the height of trees. J. Aust. Math. Soc. 7, 497–507 (1967) · Zbl 0153.25802
[20] Rojas, R.: Neural Networks. Springer, Berlin (1996) · Zbl 0861.68072
[21] Williams, D.: Probability with Martingales. Cambridge Mathematical Textbooks (1991) · Zbl 0722.60001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.