Benzerlik Ölçülerine Dayalı Entropi ile Hipergraflarda Merkezilik Tespiti

Year 2023, , 407 - 419, 30.09.2023

İhsan Tuğal , Zeydin Pala

https://doi.org/10.24012/dumf.1241450

Abstract

Hipergarflar ve basit kompleksler, daha yüksek dereceli etkileşimleri modellemek için kullanılabilir. Graflar ikili etkileşimleri modellemek ve açıklamakla sınırlıdır. Bu çalışmada hipergraflarda merkezilik konusu incelendi. Bu çalışmada hipergraflardaki düğümlerin ve hiper kenarların entropisine dayalı yeni merkezilik ölçüm yöntemleri önerildi. Şimdiye kadar, merkezi düğümleri belirlemek için çeşitli perspektiflerden birçok hesaplama önerilmiştir, ancak hiçbiri merkezilik sorununa tam bir çözüm sağlamamaktadır. Çünkü merkeziliğe farklı bakış açıları var. Merkezilik problemlerinde çözüme ulaşmak için farklı modellerin denenmesi önemlidir. Belirsizliğin bir ölçüsü olan entropi, merkezilik ölçümlerinde yol göstericidir. Merkezilik içim ideal çözümler üretebilir. Karmaşık sistemlerde entropi farklı yöntemlerle ölçülebilir. Bu çalışmada düğümler için birleşim, kesişim ve jaccard benzerlik değerlerine göre entropi hesabı yapıldı. Benzerliğin ölçülme şekli, merkeziliğin türünü gösterir. Derece ve birleşim benzerlik değerleri kullanıldığında yerel merkezilikler tespit edildi. Kesişim ve jaccard benzerlikleri bize global merkezilikleri gösterdi. Geleneksel merkezilik yöntemleri de önerilen yöntemin sonuçlarıyla karşılaştırıldı. Yöntemin doğruluğu farklı hipergraf veri setleri ile test edildi. Hipergraflar da isteklerimize göre farklı benzerlik parametreleri ile verimli sonuçlar üretilebileceği gösterildi.

Keywords

merkezilik, entropi, hipergraf

Centrality with Entropy in Hypergraphs Based on Similarity Measures

Abstract

Hypergraphs and simplicial complexes can be used to model higher-order interactions. Graphs are limited to model and describe pairwise interactions. In this study, the issue of centrality in hypergraphs was studied. We introduce centrality measures based on the entropy of nodes and hyperedges in the hypergraphs. Until now, a lot of measures from various perspectives have been proposed to identify influential nodes, yet non provides a complete solution to the centrality problem. Because there are different perspectives on centrality. It is important to try different models to reach a solution in centrality problems. Entropy, which is a measure of uncertainty, is a guide in centrality measurements. It can produce ideal solutions for centrality. In complex systems, the entropy can be measured by different methods. In this study, the entropy calculation was made according to the union, intersection, and jaccard similarity values for nodes. The way that similarity is measured indicates the type of centrality. Local centralities were detected more precisely when the degree and union similarity values were used. The intersection and jaccard similarities showed us the global centralities. Traditional methods of centrality were also compared with the results of the proposed method. The accuracy of the method was tested with different hypergraph datasets. It has been shown that we can produce efficient results with different similarity parameters according to our wishes in hypergraphs.

Keywords

centrality, entropy, hypergraph

References

• [1] F. Battiston et al., “Networks beyond pairwise interactions: Structure and dynamics,” Phys. Rep., vol. 874, pp. 1–92, Aug. 2020.
• [2] S. G. Aksoy, C. Joslyn, C. Ortiz Marrero, B. Praggastis, and E. Purvine, “Hypernetwork science via high-order hypergraph walks,” EPJ Data Sci., vol. 9, no. 1, p. 16, Dec. 2020.
• [3] K. Bouafia and B. Molnár, “Hypergraph Application on Business Process Performance,” Information, vol. 12, no. 9, p. 370, Sep. 2021.
• [4] E. Busseniers, “General Centrality in a hypergraph,” arxiv, Mar. 2014.
• [5] W. Zhou and L. Nakhleh, “Properties of metabolic graphs: biological organization or representation artifacts?,” BMC Bioinformatics, vol. 12, no. 1, p. 132, Dec. 2011.
• [6] İ. Değirmenci, “Entropy measures and the maximum entropy principle,” Hacettepe University, 2011.
• [7] A. Ullah, B. Wang, J. Sheng, J. Long, N. Khan, and Z. Sun, “Identifying vital nodes from local and global perspectives in complex networks,” Expert Syst. Appl., vol. 186, p. 115778, Dec. 2021.
• [8] S. Feng et al., “Hypergraph models of biological networks to identify genes critical to pathogenic viral response,” BMC Bioinformatics, vol. 22, no. 1, p. 287, Dec. 2021.
• [9] D. Zhou, J. Huang, and B. Schölkopf, “Learning with hypergraphs: Clustering, classification, and embedding,” in Advances in Neural Information Processing Systems, 2007.
• [10] P. Bonacich, A. Cody Holdren, and M. Johnston, “Hyper-edges and multidimensional centrality,” Soc. Networks, vol. 26, no. 3, pp. 189–203, Jul. 2004.
• [11] S. Bai, F. Zhang, and P. H. S. Torr, “Hypergraph Convolution and Hypergraph Attention,” Jan. 2019.
• [12] E. Ramadan, A. Tarafdar, and A. Pothen, “A hypergraph model for the yeast protein complex network,” in 18th International Parallel and Distributed Processing Symposium, 2004. Proceedings., 2004, pp. 189–196.
• [13] J. Rafferty et al., “Ranking sets of morbidities using hypergraph centrality,” J. Biomed. Inform., vol. 122, 2021.
• [14] A. R. Benson, “Three Hypergraph Eigenvector Centralities,” SIAM J. Math. Data Sci., vol. 1, no. 2, 2019.
• [15] C. Cui, X. Li, C. Zhang, W. Guan, and M. Wang, “Temporal-Relational hypergraph tri-Attention networks for stock trend prediction,” Pattern Recognit., vol. 143, p. 109759, Nov. 2023.
• [16] J. Wang et al., “Dynamic weighted hypergraph convolutional network for brain functional connectome analysis,” Med. Image Anal., vol. 87, p. 102828, Jul. 2023.
• [17] S. Klamt, U.-U. Haus, and F. Theis, “Hypergraphs and Cellular Networks,” PLoS Comput. Biol., vol. 5, no. 5, p. e1000385, May 2009.
• [18] Y. Yang, J. Pei, and A. Al-Barakati, “Measuring in-network node similarity based on neighborhoods: a unified parametric approach,” Knowl. Inf. Syst., vol. 53, no. 1, pp. 43–70, Oct. 2017.
• [19] S. Li, J. Huang, Z. Zhang, J. Liu, T. Huang, and H. Chen, “Similarity-based future common neighbors model for link prediction in complex networks,” Sci. Rep., vol. 8, no. 1, p. 17014, Dec. 2018.
• [20] İ. Tuğal, M. Kaya, and T. Tuncer, “Link prediction in disease and drug networks,” in 6-th International Conference of Advanced Computer Systems and Networks: Design and Application (ACSN 2013), 2013, pp. 46–50.
• [21] C. E. Shannon, “A Mathematical Theory of Communication,” Bell Syst. Tech. J., 1948.
• [22] İ. Tuğal and A. Karcı, “Comparisons of Karcı and Shannon entropies and their effects on centrality of social networks,” Phys. A Stat. Mech. its Appl., vol. 523, pp. 352–363, 2019.
• [23] Y. Song and Y. Deng, “Entropic Explanation of Power Set,” Int. J. Comput. Commun. Control, vol. 16, no. 4, Aug. 2021.
• [24] C. Hark and A. Karcı, “Karcı summarization: A simple and effective approach for automatic text summarization using Karcı entropy,” Inf. Process. Manag., vol. 57, no. 3, p. 102187, May 2020.
• [25] Y. Deng, “Deng entropy,” Chaos, Solitons and Fractals, vol. 91, pp. 549–553, 2016.
• [26] V. Chellappan, K. M. Sivalingam, and K. Krithivasan, “A Centrality Entropy Maximization Problem in Shortest Path Routing Networks,” Comput. Networks, vol. 104, pp. 1–15, Jul. 2016.
• [27] Z. Qiu, T. Fan, M. Li, and L. Lü, “Identifying vital nodes by Achlioptas process,” New J. Phys., vol. 23, no. 3, p. 033036, Mar. 2021.
• [28] C. Hark, T. Uçkan, E. Seyyarer, and A. Karcı, “An Unsupervised Approach Based on Node Centralization for Text Summarization,” Bitlis Eren Univ. J. Sci., vol. 8, no. 3, pp. 1109–1118, Sep. 2019.
• [29] L. C. Freeman, “Centrality in social networks conceptual clarification,” Soc. Networks, vol. 1, no. 3, pp. 215–239, 1978.
• [30] L. C. Freeman, “A Set of Measures of Centrality Based on Betweenness,” Sociometry, vol. 40, no. 1, p. 35, Mar. 1977.
• [31] P. Bonacich, “Some unique properties of eigenvector centrality,” Soc. Networks, vol. 29, no. 4, pp. 555–564, 2007.
• [32] S. Brin and L. Page, “The anatomy of a large-scale hypertextual Web search engine,” Comput. Networks ISDN Syst., vol. 30, no. 1–7, pp. 107–117, Apr. 1998.
• [33] J. P. Scott, Social Network Analysis: A Handbook. 2000.
• [34] E. Estrada, The Structure of Complex Networks, vol. 45, no. 2. 2011.
• [35] P. Hu, W. Fan, and S. Mei, “Identifying node importance in complex networks,” Phys. A Stat. Mech. its Appl., vol. 429, pp. 169–176, 2015.
• [36] Z. W. Liang and J. P. Li, “Identifying and ranking influential spreaders in complex networks,” in 2014 11th International Computer Conference on Wavelet Active Media Technology and Information Processing, ICCWAMTIP 2014, 2014, pp. 393–396.
• [37] S. Wang, Y. Du, and Y. Deng, “A new measure of identifying influential nodes: Efficiency centrality,” Commun. Nonlinear Sci. Numer. Simul., vol. 47, pp. 151–163, 2017.
• [38] Y. Yu, B. Zhou, L. Chen, T. Gao, and J. Liu, “Identifying Important Nodes in Complex Networks Based on Node Propagation Entropy,” Entropy, vol. 24, no. 2, p. 275, Feb. 2022.
• [39] S. P. Borgatti, M. G. Everett, and L. C. Freeman, “UCINET 6 For Windows: Software for Social Network Analysis, Analytic Technologies, Harvard, MA.,” Anal. Technol., 2002.
• [40] M. Zitnik, R. Sosi, S. Maheshwari, and J. Leskovec, “BioSNAP Datasets: Stanford Biomedical Network Dataset Collection,” 2018. [Online]. Available: https://snap.stanford.edu/biodata/datasets/10015/10015-ChG-TargetDecagon.html.
• [41] E. J. Power, M. L. Chin, and M. M. Haq, “Breast Cancer Incidence and Risk Reduction in the Hispanic Population,” Cureus, Feb. 2018.
• [42] Y. Liu, B. Wei, Y. Du, F. Xiao, and Y. Deng, “Identifying influential spreaders by weight degree centrality in complex networks,” Chaos, Solitons & Fractals, vol. 86, pp. 1–7, May 2016.
• [43] T. Bian and Y. Deng, “A new evidential methodology of identifying influential nodes in complex networks,” Chaos, Solitons and Fractals, vol. 103, pp. 101–110, 2017.