Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım

Abstract

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.

Keywords

• Merkezlilik algoritmaları
• Çizge teorisi
• Etkili düğüm
• Temel kesme

A New Approach to Determining Effective Nodes in Linked Graphs

Abstract

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.

Keywords

• Centrality algorithm
• Graph theory
• Effective node
• Fundamental cut-set

References

1. [1] Seker, S.E. 2015. Çizge Teorisi(Graph Theory). YBS Ansiklopedi, v.2. s. 17-29,
2. [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.
3. [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
4. [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
5. [5] Kintali, S. 2008. Betweenness Centrality : Algorithms and Lower Bounds, arxiv.org/abs/0809.1906v2, 19 Oct
6. [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.
7. [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
8. [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

9. [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
10. [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.
11. [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
12. [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
13. [13] Needham, M., Hadler, A.E. 2019. Graph Algorithms: Practical Examples in Apache Spark and Neo4j. O'Reilly, May
14. [14] Pagerank Algorithm. 2020. https://neo4j.com/docs/graph-algorithms/current/algorithms/page-rank/, (Erişim Tarihi: 24.12.2020)
15. [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.
16. [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
17. [17] Degree Centrality. 2020. https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/degree-centrality/ (Erişim Tarihi: 24.12.2020)
18. [18] Karci, A. 2020. New Algorithms for Minimum Dominating Set in Any Graphs. Anatolian Science, Cilt, 5. Sayı, 2. s. 62-70