Scale free distribution of nodes in Euclidean graphs

• Autorzy: Dominik A. , Walczak Z. , Wojciechowski J. , Wojciechowski J.
• Konferencja: Evolutionary Computation and Global Optimization 2006 / National Conference (9 ; 31.05-2.06.2006 ; Murzasichle, Poland)
• Języki publikacji: EN

Abstrakty

EN

In the paper we propose a new model of spatial distribution of nodes in graphs which can be represented in the Euclidean space. Such graphs appear in many areas of computer science, for instance wireless networks design, Traveling Salesman and Vehicle Routing Problems. We show analogies between scale-free and Euclidean graphs. Although the distribution of node's degrees in Euclidean graphs is not scale-free, the spatial distribution of node's follows the power law. We analyze distribution of population density in different continents, propose a model to generate such distributions and provide numerical experiments concerning its quality. Finally, the impact of our model on different NP-complete problems in Euclidean graphs is analyzed.

Słowa kluczowe

EN

Euclidean space; Euclidean graphs; spatial distribution; uniform distribution; traveling salesman problem; vehicle routing problem; nodes; scale free; scale free distribution

PL

przestrzeń euklidesowa; graf euklidesowy; rozkład przestrzenny; rozkład jednostajny; problem komiwojażera; problem marszrutyzacji; węzły sieci; sieć bezskalowa; rozkład sieci bezskalowej

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2006
• Tom: z. 156
• Strony: 107--115
• Opis fizyczny: Bibliogr. 17 poz., tab., rys., wykr.

Twórcy

autor

Dominik A.

autor

Walczak Z.

autor

Wojciechowski J.

autor

Wojciechowski J.

• Faculty of Electronics and Information Technology, Warsaw University of Technology,

Bibliografia

• [1] Gridded population of the world (gpw) data set. Columbia University; International Food Policy Research Institute (IFPRI); and World Resources Institute (WRI). Available at http://sedac.ciesin.columbia.edu/plue/gpw, 1995.
• [2] Concorde tsp solver. Available at http://www.tsp.gatech.edu/concorde.html Available, 2000.
• [3] Reka Albert and Albert-Laszlo Barabasi. Statistical mechanics of complex networks. Review of Modern Physics, pages 47-97, January 2002.
• [4] Albert-Laszlo Barabasi and Zoltan N. Oltvai. Network biology: Understanding the cell's functional organization. Nature, pages 101-113, February 2004.
• [5] Aharon Blank and Sorin Solomon. Power laws and cities population. http://arxiv.org/html/cond-mat/0003240, 2000.
• [6] J.M Braun, M.L., Buhmann. The noisy euclidean traveling salesman problem and learning. Advances in Neural Information Processing Systems, 2002.
• [7] D. Brelaz. New methods to color vertices of a graph. Communications of the ACM, 22:251-256, 1979.
• [8] Brent N. Clark, Charles J. Colbourn and David S. Johnson. Unit disk graphs. Discrete Math., 86(1-3):165-177, 1990.
• [9] G. Zipf. Human behavior and the principles of last effort. 1949.
• [10] D. Johnson and M.A. McGeoch. The Traveling Salesman Problem and its Variations, chapter Experimental analysis of heuristics for the STSP. Kluwer Academic Publishers, 2002.
• [11] E.L. Lloyd. Broadcast scheduling for tdma in wireless multihop networks. Handbook of Wireless Networks and Mobile Computing, pages 347-370, 2002.
• [12] A. Mehrotra and M.A. Trick. A column generation approach to graph coloring. Technical report, Carnegie Mellon University, 1995.
• [13] A.A.Bertossi, R. Battoti and M.A. Bonuccelli. Assigning codes in wireless networks: Bounds and scaling properties. Wireless Networks, pages Vol. 5, 195-209, 1999.
• [14] S.Krirkpatick, B. Selman, R. Monasson, R. Zecchina and L. Troyansky. Determining computational complexity from characteristic 'phase transition'. Nature, 400:133-137, 1999.
• [15] Albert-Laszlo Barabasi, Reka Albert, Hawoong Jeong. Diameter of the world-wide web. Nature, page 130, September 1999.
• [16] Jano I. van Hemert and Neil B. Urquhart. Phase transition properties of clustered traveling salesman problem instances generated with evolutionary computation. In Parallel Problem Solvers from Nature VIII, pages 150-159, 2004.
• [17] Xiao Fan Wang and Guanrong Chen. Complex networks: Small-word, scale-free and beyond. IEEE Circuits and Systems Magazine, pages 6-20, First quarter 2003.