Application of Graphs and Networks Similarity Measures for Analyzing Complex Networks

• Autorzy: Bartosiak C. , Kasprzyk R. , Tarapata Z.

Warianty tytułu

PL

Wykorzystanie metod badania podobieństwa grafów i sieci do analizy sieci złożonych

• Języki publikacji: EN

Abstrakty

EN

In the paper we focus on the research of graphs and networks similarity measures for analyzing complex networks. This kind of researches has a very wide range of applications in the military and civilian domains and tasks such as: law enforcement, criminal investigation, counter-terrorism as well as algorithms used in web search engines, analysis of bio systems or chemical compounds and many others. Using a tool, which we have implemented, we show an experimental analysis of an airlines network. Afterwards we present opportunities of making use of our methods and tool for analyzing real systems which can be modelled using graphs and network models.

PL

W artykule zaproponowano koncepcję wykorzystania metod badania podobieństwa grafów i sieci do analizy sieci złożonych. Omówiono podstawowe modele sieci złożonych oraz metody badania podobieństwa grafów i sieci. Następnie przedstawiono opis popularnych środowisk do analizy grafów i sieci oraz autorskie narzędzie do badania podobieństwa grafów i sieci. Przedstawiono praktyczny przykład wykorzystania zbudowanej aplikacji potwierdzający jej użyteczność w analizie sieci złożonych.

Słowa kluczowe

EN

graph similarity measures; complex networks; gephi

PL

grafowe miary podobieństwa; sieci złożone; gephi

• Wydawca: Institute of Computer and Information Systems, Faculty of Cybernetics, Military University of Technology
• Czasopismo: Biuletyn Instytutu Systemów Informatycznych
• Rocznik: 2011
• Tom: nr 7
• Strony: 1--7
• Opis fizyczny: Bibliogr. 19 poz., rys., wykr.

Twórcy

autor

Bartosiak C.

autor

Kasprzyk R.

autor

Tarapata Z.

• Faculty of Cybernetics, Military University of Technology, Kaliskiego Str. 2, 00 908 Warsaw, Poland,

Bibliografia

• [1] R. Antkiewicz, M. Chmielewski, R. Kasprzyk, A. Najgebauer, Z. Tarapata: The prediction of terrorist threat on basis of semantic associations and complex network evolution. Proceedings of Military Communications and Information Systems Conference, 2007.
• [2] A.-L. Barabási, R. Albert: Emergence of scaling in random networks. Science, Vol. 286, 509−512 (1999).
• [3] C. Bartosiak: Analiza związku między metodami wyznaczania podobieństwa grafów i sieci oraz analizy sieci złożonych. Praca inżynierska, promotor – Z. Tarapata, konsultant – R. Kasprzyk, Wydział Cybernetyki, Wojskowa Akademia Techniczna, Warszawa 2009.
• [4] M. Bastian, S. Heymann, M. Jacomy: Gephi: an open source software for exploring and manipulating networks. International AAAI Conference on Weblogs and Social Media, 2009.
• [5] V. D. Blondel, A. Gajardo, M. Heymans, P. Senellart, P. V. Dooren: A measure of similarity between graph vertices applications to synonym extraction and web searching. SIAM Review, Vol. 46 (4), 647-666 (2004).
• [6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Wprowadzenie do algorytmów. Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
• [7] P. Erdős, A. Rényi: On random graphs I. Publ. Math. Debrecen, Vol. 6, 290−297 (1959).
• [8] M. Hattori, Y. Okuno, S. Goto, M. Kanehisa: Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways. Journal of the American Chemical Society, Vol. 125, 11853−11865 (2003).
• [9] R. Kasprzyk: Fault and attack resistance of complex networks. X International Workshop for Candidates for a Doctor’s Degree OWD, Wisła, Poland, 2008.
• [10] R. Kasprzyk: The vaccination against epidemic spreading in complex networks. Biuletyn Instytutu Systemów Informatycznych, Vol. 3, 39−43 (2009).
• [11] 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).
• [12] D. Kempe, J. M. Kleinberg, E. Tardos: Maximizing the spread of influence through a social network. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003.
• [13] R. Pastor-Satorras, A. Vespignani: Epidemic spreading in scale-free networks. Phys. Rev. Lett., Vol. 86, 3200−3203 (2001).
• [14] 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), 1149−1155, Szczecin, Poland 2007.
• [15] 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, 20−22.07.2009, Athens (Greece), IEEE Computer Society, 366−368, 2009.
• [16] Y. Wang, F. Makedon, J. Ford, H. Huang: A bipartite graph matching framework for finding correspondences between structural elements in two proteins. Engineering in Medicine and Biology Society, Vol. 2, 2972−2975 (2004).
• [17] D. J. Watts, S. Strogatz: Collective dynamics of 'small-world' networks. Nature, Vol. 393, 440−442 (1998).
• [18] http://butunclebob.com/ArticleS.UncleBob.PrinciplesOfOod
• [19] http://gephi.org/