Research Article
BibTex RIS Cite

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

Year 2022, Volume: 24 Issue: 70, 143 - 155, 17.01.2022
https://doi.org/10.21205/deufmd.2022247014

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.

References

  • [1] Seker, S.E. 2015. Çizge Teorisi(Graph Theory). YBS Ansiklopedi, v.2. s. 17-29,
  • [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] 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] 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] Kintali, S. 2008. Betweenness Centrality : Algorithms and Lower Bounds, arxiv.org/abs/0809.1906v2, 19 Oct
  • [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] 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] 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] 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] 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] 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] Ö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] Needham, M., Hadler, A.E. 2019. Graph Algorithms: Practical Examples in Apache Spark and Neo4j. O'Reilly, May
  • [14] Pagerank Algorithm. 2020. https://neo4j.com/docs/graph-algorithms/current/algorithms/page-rank/, (Erişim Tarihi: 24.12.2020)
  • [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] 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] Degree Centrality. 2020. https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/degree-centrality/ (Erişim Tarihi: 24.12.2020)
  • [18] Karci, A. 2020. New Algorithms for Minimum Dominating Set in Any Graphs. Anatolian Science, Cilt, 5. Sayı, 2. s. 62-70

A New Approach to Determining Effective Nodes in Linked Graphs

Year 2022, Volume: 24 Issue: 70, 143 - 155, 17.01.2022
https://doi.org/10.21205/deufmd.2022247014

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.

References

  • [1] Seker, S.E. 2015. Çizge Teorisi(Graph Theory). YBS Ansiklopedi, v.2. s. 17-29,
  • [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] 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] 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] Kintali, S. 2008. Betweenness Centrality : Algorithms and Lower Bounds, arxiv.org/abs/0809.1906v2, 19 Oct
  • [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] 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] 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] 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] 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] 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] Ö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] Needham, M., Hadler, A.E. 2019. Graph Algorithms: Practical Examples in Apache Spark and Neo4j. O'Reilly, May
  • [14] Pagerank Algorithm. 2020. https://neo4j.com/docs/graph-algorithms/current/algorithms/page-rank/, (Erişim Tarihi: 24.12.2020)
  • [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] 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] Degree Centrality. 2020. https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/degree-centrality/ (Erişim Tarihi: 24.12.2020)
  • [18] Karci, A. 2020. New Algorithms for Minimum Dominating Set in Any Graphs. Anatolian Science, Cilt, 5. Sayı, 2. s. 62-70
There are 18 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Research Article
Authors

Furkan Öztemiz 0000-0001-5425-3474

Ali Karci 0000-0002-8489-8617

Publication Date January 17, 2022
Published in Issue Year 2022 Volume: 24 Issue: 70

Cite

APA Öztemiz, F., & Karci, A. (2022). Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen Ve Mühendislik Dergisi, 24(70), 143-155. https://doi.org/10.21205/deufmd.2022247014
AMA Öztemiz F, Karci A. Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım. DEUFMD. January 2022;24(70):143-155. doi:10.21205/deufmd.2022247014
Chicago Öztemiz, Furkan, and Ali Karci. “Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım”. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen Ve Mühendislik Dergisi 24, no. 70 (January 2022): 143-55. https://doi.org/10.21205/deufmd.2022247014.
EndNote Öztemiz F, Karci A (January 1, 2022) Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi 24 70 143–155.
IEEE F. Öztemiz and A. Karci, “Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım”, DEUFMD, vol. 24, no. 70, pp. 143–155, 2022, doi: 10.21205/deufmd.2022247014.
ISNAD Öztemiz, Furkan - Karci, Ali. “Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım”. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi 24/70 (January 2022), 143-155. https://doi.org/10.21205/deufmd.2022247014.
JAMA Öztemiz F, Karci A. Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım. DEUFMD. 2022;24:143–155.
MLA Öztemiz, Furkan and Ali Karci. “Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım”. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen Ve Mühendislik Dergisi, vol. 24, no. 70, 2022, pp. 143-55, doi:10.21205/deufmd.2022247014.
Vancouver Öztemiz F, Karci A. Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım. DEUFMD. 2022;24(70):143-55.

Dokuz Eylül Üniversitesi, Mühendislik Fakültesi Dekanlığı Tınaztepe Yerleşkesi, Adatepe Mah. Doğuş Cad. No: 207-I / 35390 Buca-İZMİR.