TY - JOUR T1 - Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım TT - A New Approach to Determining Effective Nodes in Linked Graphs AU - Öztemiz, Furkan AU - Karci, Ali PY - 2022 DA - January DO - 10.21205/deufmd.2022247014 JF - Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi JO - DEUFMD PB - Dokuz Eylül Üniversitesi WT - DergiPark SN - 1302-9304 SP - 143 EP - 155 VL - 24 IS - 70 LA - tr AB - Graf(Çizge) teorisi veri biliminin gelişmesi ile birçok farklı alanda modelleme ve analiz işlemlerinin gerçekleştirilmesinde kullanılmıştır. Farklı türdeki problemlerin çözümlenmesi için çizge teorisinde çok sayıda algoritma ve yöntem geliştirilmiştir. Bu çalışmada bir çizge yapısı içerisinde bulunan etkili düğümlerin tespit edilmesi amaçlanmıştır. Çizge üzerindeki etkili düğümler sosyal ağlar içerisindeki baskın bireylerin, ulaşım ağları içerisindeki yoğun ve kritik konuma sahip kavşak noktalarının, borsa sistemlerinde birbirini etkileyen firmaların ve seri üretim yapan bir fabrikada otomasyon sisteminin kilit adımlarının tespit edilmesi vb.. birçok farklı alanda çözüm sunmaktadır. Çizgeler üzerindeki etkili düğümlerin tespit edilmesi için çeşitli algoritmalar geliştirilmiştir. Bu çalışmada yönsüz ve ağırlıksız bir çizgedeki etkili düğümlerin tespit edilmesi için yeni bir algoritma önerilmiştir. Ayrıca mevcut etkili düğüm keşfetme algoritmalarından PageRank, Closeness, Eigenvector, Degree merkezlilik ölçütleri ile karşılaştırılması yapılmıştır. Çalışmada algoritmalara ait sonuçlar dikkate alınarak çizgedeki düğümlerin etkili olma sıralamalarına yer verilmiştir. Algoritmanın kodlanması ve görselleştirme işlemleri için R programlama dili kullanılmıştır. KW - Merkezlilik algoritmaları KW - Çizge teorisi KW - Etkili düğüm KW - Temel kesme N2 - Graph theory has been used in the development of data science with realization of modeling and analysis processes in many different fields. Numerous algorithms and methods have been developed in graph theory to solve different types of problems. In this study, it is aimed to identify the active nodes in a graph structure. Effective nodes on the graph provide solutions in many different areas such as identifying dominant individuals in social networks, intensive and critical intersections in transportation networks, companies that affect each other in stock market systems, key steps of an automation system in a factory that makes mass production etc.. Various algorithms have been developed for detecting effective-influence nodes on graphs. In this study, a new algorithm is proposed to determine the effective nodes in a non-directional and unweighted graph. Also, comparison with existing effective node discovery algorithms like PageRank, Closeness, Eigenvector, Degree centrality criterion has been made. In the study, taking into consideration the results of the algorithms, the influence ranking of the nodes in the graph are given. R programming language is used for coding and visualization of the algorithm. CR - [1] Seker, S.E. 2015. Çizge Teorisi(Graph Theory). YBS Ansiklopedi, v.2. s. 17-29, CR - [2] Riaz, F. and Ali, K. M. 2011. Applications of Graph Theory in Computer Science. Third International Conference on Computational Intelligence, Communication Systems and Networks, Bali, s. 142-145. DOI: 10.1109/CICSyN.2011.40. CR - [3] Kenett, D.Y., Tumminello, M., Madi, A., Gur-Gershgoren, G., Mantegna, R.N. and Ben-Jacob, E. 2010. Dominating Clasp of the Financial Sector Revealed by Partial Correlation Analysis of the Stock Market. PLOS ONE 20 Dec, DOI: 10.1371/journal.pone.0015032 CR - [4] Cozzens, M.B., Kelleher, L.L. 1988. Dominating sets in social network graphs, ELSEVIER Cilt. 16, Issue. 3, December, s. 267-279, DOI: 10.1016/0165-4896(88)90041-8 CR - [5] Kintali, S. 2008. Betweenness Centrality : Algorithms and Lower Bounds, arxiv.org/abs/0809.1906v2, 19 Oct CR - [6] Xing, W. and Ghorbani, A. 2004. Weighted PageRank algorithm. Proceedings. Second Annual Conference on Communication Networks and Services Research, Fredericton, NB, Canada, s. 305-314, DOI: 10.1109/DNSR.2004.1344743. CR - [7] Yuanyuan, Z., Xiaohua, J., Yanxiang, H. 2006. Energy Efficient Distributed Connected Dominating Sets Construction in Wireless Sensor Networks. IWCMC, s. 797–802, July, DOI: 10.1145/1143549.1143709 CR - [8] Alahakoon, T., Tripathi, R., Kourtellis, N., Simha, R., Lamnitchi, A. 2011. K-path centrality: a new centrality measure in social networks. SNS '11: Proceedings of the 4th Workshop on Social Network Systems, s. 1–6, April, DOI: 10.1145/1989656.1989657 CR - [9] Ding Y., Yan E., Frazho A., Caverlee J. 2009. PageRank for ranking authors in co‐citation networks” , Journal of the American Society for Information Science and Technology Volume60, Issue11 Pages 2229-2243 November, DOI: 10.1002/asi.21171 CR - [10] Jagadishwari, V. and Chakrabarty, S. 2020. Link Prediction using Influencer nodes of a Social Network. 2020 Second International Conference on Inventive Research in Computing Applications (ICIRCA), Coimbatore, India, s. 927-930, DOI: 10.1109/ICIRCA48905.2020.9183315. CR - [11] Agryzkov, T., Tortosa, L., Vicent, JF., Wilson, R. 2019. A centrality measure for urban networks based on the eigenvector centrality concept. Environment and Planning B: Urban Analytics and City Science, 46(4) s. 668-689, DOI: 10.1177/2399808317724444 CR - [12] Öztemiz, F., KARCI, A. 2020. Akademik Yazarların Yayınları Arasındaki İlişkinin Sosyal Ağ Benzerlik Yöntemleri İle Tespit Edilmesi. Uludağ University Journal of The Faculty of Engineering, Cilt, 25. Sayı, 1. s. 591-608, DOI: 10.17482/uumfd.533476 CR - [13] Needham, M., Hadler, A.E. 2019. Graph Algorithms: Practical Examples in Apache Spark and Neo4j. O'Reilly, May CR - [14] Pagerank Algorithm. 2020. https://neo4j.com/docs/graph-algorithms/current/algorithms/page-rank/, (Erişim Tarihi: 24.12.2020) CR - [15] Sariyüce, A.E., Kaya, K., Saule, E. And Çatalyürek, Ü.V. 2013. Incremental algorithms for closeness centrality. 2013 IEEE International Conference on Big Data, Silicon Valley, CA, s. 487-492, DOI: 10.1109/BigData.2013.6691611. CR - [16] Bonacich, P. 2007. Some unique properties of eigenvector centrality. Elsevier, Social Networks Cilt, 29. Sayı, 4. October, s. 555-564, DOI: 10.1016/j.socnet.2007.04.002 CR - [17] Degree Centrality. 2020. https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/degree-centrality/ (Erişim Tarihi: 24.12.2020) CR - [18] Karci, A. 2020. New Algorithms for Minimum Dominating Set in Any Graphs. Anatolian Science, Cilt, 5. Sayı, 2. s. 62-70 UR - https://doi.org/10.21205/deufmd.2022247014 L1 - https://dergipark.org.tr/tr/download/article-file/1467337 ER -