Czy sieci rządzą światem? : od Eulera do Barabasiego

• Autorzy: Tarapata Z.

Warianty tytułu

EN

Do Networks Control the World? : From Euler to Barabasi

• Języki publikacji: PL

Abstrakty

PL

W pracy poruszono problem różnorodnych zastosowań modeli i metod teorii grafów i sieci. W szczególności zwrócono uwagę na cechy charakterystyczne współczesnych sieci rzeczywistych. Przeanalizowano, w jaki sposób modeluje się te sieci, jakie mają własności i co z tego wynika. Poruszono algorytmiczne aspekty sieci złożonych ukierunkowane na złożoność obliczeniową metod wyznaczania wartości charakterystyk sieci. Kilkanaście interdyscyplinarnych przykładów rzeczywistych sieci zilustrowało opisywane własności sieci. We wnioskach opisano tendencje rozwojowe współczesnej teorii grafów i sieci, zwłaszcza w kontekście modelowania ewolucji sieci złożonych.

EN

In the paper problem of multi-applications of graph and networks theory models and methods is considered. The paper is especially focused on specific features of real networks. Analysis methods of these networks, their properties and what result from these analyses are discussed. Algorithmic aspects focused on computational complexity of methods to compute values of network's characteristics are considered. Several interdisciplinary examples of real networks illustrate network's properties being described. In conclusions current and future trends in development of complex networks are considered.

Słowa kluczowe

PL

sieci złożone; systemy złożone; bezskalowość; małe światy; zastosowania sieci złożonych; algorytmiczne aspekty sieci złożonych

EN

complex networks; complex systems; scale free; small-world; applications of complex networks; algorithmic aspects of complex networks

• Wydawca: Institute of Computer and Information Systems, Faculty of Cybernetics, Military University of Technology
• Czasopismo: Biuletyn Instytutu Systemów Informatycznych
• Rocznik: 2012
• Tom: nr 10
• Strony: 31--51
• Opis fizyczny: Bibliogr. 52 poz., il., wykr.

Twórcy

autor

Tarapata Z.

• Instytut Systemów Informatycznych, Wydział Cybernetyki. Wojskowa Akademia Techniczna, ul. Gen. S. Kaliskiego 2, 00-908 Warszawa,

Bibliografia

• [1] R. Antkiewicz, M. Chmielewski, R. Kasprzyk, A. Najgebauer, ”The prediction of terrorist threat on basis of semantic associations and complex network evolution”, Military Communications and Information Systems Conference’2007, Behorden Spiegel, Bonn (2007).
• [2] R. Antkiewicz , A. Najgebauer, J. Rulka, Z. Tarapata, R. Wantoch-Rekowski, ”Knowledge-Based Pattern Recognition Method and Tool to Support Mission Planning and Simulation”, ICCCI’2011, Part I, Lecture Notes in Computer Science, Vol. 6922, Springer-Verlag Berlin Heidelberg, 478-487 (2011).
• [3] A.-L. Barabási, R. Albert, ”Emergence of scaling in random networks”, Science, Vol. 286, 509-512 (1999).
• [4] C. Bartosiak, R. Kasprzyk, Z. Tarapata, ”Application of Graphs and Networks Similarity Measures for Analyzing Complex Networks”, Biuletyn Instytutu Systemów Informatycznych, Nr 7, 1-7 (2011).
• [5] C. Bartosiak, Analiza modeli i algorytmów ewolucji sieci społecznych na przykładzie wybranej sieci rzeczywistej, praca magisterska (kierownik: Z. Tarapata), WAT, Warszawa, 2012.
• [6] B. Bollobas, Modern Graph Theory, Springer-Verlag, Berlin Heidelberg, 2001.
• [7] U. Brandes, ”A Faster Algorithm for Betweenness Centrality”, Journal of Mathematical Sociology, Vol. 25, 163-177 (2001).
• [8] R. Diestel, Graph Theory, Springer-Verlag, Berlin Heidelberg, 2005.
• [9] J. Duch, J. S. Waitzman, L. A. N. Amaral, ”Quantifying the Performance of Individual Players in a Team Activity”, PLoS ONE 5(6): e10937 (2010), doi:10.1371/journal.pone.0010937
• [10] P. Erdős, A. Rényi, ”On random graphs I”, Publ. Math. Debrecen, Vol. 6, 290-297 (1959).
• [11] L. Euler, ”Solutio problematis ad geometriam situs pertinentis”, Comment. Academiae Sci. I. Petropolitanae 8, 128-140 (1736).
• [12] T. Florczak, Grafowo-sieciowe metody reprezentacji i identyfikacji sytuacji decyzyjnych, praca magisterska (kierownik: Z. Tarapata), WAT, Warszawa, 2012.
• [13] L. Freeman, ”A set of Measures of Centrality Based on Betweenness”, Sociometry, Vol.40, 35-41(1977).
• [14] A. Fronczak, P. Fronczak, Świat sieci złożonych: Od fizyki do Internetu, Wydawnictwo Naukowe PWN, Warszawa, 2009.
• [15] C. Hierholzer, ”Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren”, Mathematische Annalen 6 (1): 30–32, doi:10.1007/BF01442866 (1873).
• [16] A. S. Ismail, R. Hasni, K. G. Subramanian, ”Some applications of Eulerian graphs”, International Journal of Mathematical Science Education, Technomathematics Research Foundation, Vol. 2, Nr 2, 1 – 10 (2009).
• [17] R. Kasprzyk, ”The vaccination against epidemic spreading in complex networks”, Biuletyn Instytutu Systemów Informatycznych, Vol. 3, 39-43 (2009).
• [18] R. Kasprzyk, B. Lipiński, K. Wilkos, M. Wilkos, C. Bartosiak, ”CARE – Creative Application to Remedy Epidemics”, Biuletyn Instytutu Systemów Informatycznych, Vol. 3, 45-52 (2009).
• [19] R. Kasprzyk, Modele ewolucji systemów złożonych i metody badania ich charakterystyk dla potrzeb komputerowej identyfikacji potencjalnych sytuacji kryzysowych, rozprawa doktorska, Wojskowa Akademia Techniczna, Warszawa, 2011.
• [20] V. Krebs, ”Mapping Networks of Terrorist Cells”, Connections, Vol. 24(3), 43-52 (2002).
• [21] J. Leskovec, Horvitz E., ”Planetary-Scale Views on an Instant-Messaging Network”, Proceedings of the 17th International World Wide Web Conference (WWW'2008), April 21-25, 2008, Beijing, China, (915-924) Beijing, 2008.
• [22] X. Liu, C. K. Tse and M. Small, ”Composing music with complex networks”, International Conference on Complex Sciences: Theory and Applications (COMPLEX2009), 2196-2205, Shanghai, 2009.
• [23] J. L. Pena, H. Touchette, ”A network theory analysis of football strategies”, arXiv:1206.6904v1 [math.CO] (2012).
• [24] P. Pevzner, H. Tang, M. Waterman, ”An Eulerian trail approach to DNA fragment assembly”, Proceedings of the National Academy of Sciences of the United States of America 98 (17): 9748–9753 (2001).
• [25] F. Radicchi, ”Who is the best player ever? A complex network analysis of the history of professional tennis”, arXiv:1101.4028v1 [physics.soc-ph] (2011).
• [26] Z. Tarapata, ”Multicriteria weighted graphs similarity and its application for decision situation pattern matching problem”, Proceedings of the 13th IEEE/IFAC International Conference on Methods and Models in Automation and Robotics MMAR’2007, August 27-30, Szczecin, Poland, 2007.
• [27] Z. Tarapata, R. Kasprzyk, ”An application of multicriteria weighted graph similarity method to social networks analyzing”, Proceedings of the 2009 International Conference on Advances in Social Network Analysis and Mining, July 20-22, 2009, Athens (Greece), IEEE Computer Society, 366-368 (2009).
• [28] Z. Tarapata, M. Chmielewski, R. Kasprzyk, ”An Algorithmic Approach To Social Knowledge Processing And Reasoning Based On Graph Representation – A Case Study”, ACIIDS 2010, Lecture Notes in Artificial Intelligence, 5991, Springer-Verlag Berlin Heidelberg, 93-104 (2010).
• [29] Z. Tarapata, R. Kasprzyk, ”Graph-based optimization method for information diffusion and attack durability in networks”, RSCTC 2010, Lecture Notes in Artificial Intelligence, 6086, Springer-Verlag Berlin Heidelberg, 698-709 (2010).
• [30] Z. Tarapata, Models and algorithms for knowledge-based decision support and simulation in defence and transport applications, rozprawa habilitacyjna, Wojskowa Akademia Techniczna, Warszawa, 2011.
• [31] Z. Tarapata, Czy sieci rządzą światem? - Od Eulera do Barabasiego, wykład inauguracyjny, WAT, Warszawa, 2 października 2012 r.
• [32] J. Travers, S. Milgram, ”An Experimental Study of the Small World Problem”, Sociometry, Vol. 32, Nr 4, 425-443 (1969).
• [33] D. J. Watts, S. Strogatz, ”Collective dynamics of ‘small-world’ networks”, Nature, Vol. 393, 440-442 (1998).
• [34] B. S. Yilmaz, O. D. Gunel, ”Probable applications of complex networks in public relations practices: A scenario-based approach”, PRism 6(1) (2009), http://praxis.massey.ac.nz/prism_online_journ.html.
• [35] History of Mathematics: On Leonhard Euler (1707-1783), ScienceWeek (2003), 6 Nov. 2005, http://scienceweek.com/2003/sc031121-6.htm.
• [36] http://vator.tv/news/2010-12-28-top-10-biggest-social-media-stories-of-2010
• [37] http://www.fernfachhochschule.ch/ffhs/afe/lws/forschung/research/view?set_language=en
• [38] http://www.beyondthemap.ca/english/explore_web.html
• [39] http://about-france.com/paris-metromap.htm
• [40] http://www.sciencedirect.com/science/article/pii/S0375960108015867
• [41] http://da.wikipedia.org/wiki/Fil:High_Speed_Railroad_Map_Europe_2011.png
• [42] http://www.cut.nazwa.pl/ptg/konfer/include/wydaw.php?r=2007&ab=7b
• [43] http://www.mslima.com/mfadt/thesis/2004/08/transportation-routes.html
• [44] http://www.vectorstock.com/royalty-freevector/circulation-of-blood-vector-97672
• [45] http://www.alz.org/brain_polish/05.asp
• [46] http://www.asbmb.org/asbmbtoday/asbmbtoday_article.aspx?id=14931
• [47] http://phys.strath.ac.uk/information/acadstaff/ernesto.estrada.php
• [48] http://www.crossway.org/blog/2007/01/mapping-nt-social-networks/
• [49] http://www.dailymail.co.uk/sciencetech/article-2064746/Facebook-shrinks-degreesseparation-just-FOUR.html
• [50] http://thehypertextual.com/2011/03/07/middle-east-strategy-lesson-social-networksbeat-weapons/
• [51] http://strona.wcy.wat.edu.pl/index.php?option=com_content&task=view&id=247&Itemid=131
• [52] http://www.youtube.com/watch?v=2guKJfvq4uI