Prediction nullity of graph using data mining: Prediction nullity of graph using data mining

Mehdi Alaeiyan; Karrar Khudhair Obayes; Mohammadhadi Alaeiyan

Authors

Mehdi Alaeiyan School of Mathematics, Iran University of Science and Technolgy, Narmak, Tehran 16846, Iran.
Karrar Khudhair Obayes School of Mathematics, Iran University of Science and Technology, Narmak, Tehran 16846, Iran.
Mohammadhadi Alaeiyan Faculty of Computer Engineering, K. N. Toosi University of Technology, Seyed Khandan, Shariati Ave, 16317-14191 Tehran, Iran.

Keywords:

Nullity of a graph, Machine learning, Graph, Eigenvalue

Abstract

Nullity computation is widely used to determine the stability of a chemical molecule. Mainly, a molecule is presented as a graph, and the graph nullity value clarifies the strength of the molecule. Some formulas for specific graphs help us compute the nullity value, but it is challenging to remember the formula of each particular graph. However, another formula for calculating the nullity value is based on the graph rank. Nevertheless, processing time would be increased by the growth of the number of vertices of graphs. This paper suggests machine learning methods for computing the nullity value of a given graph. We leveraged random graph generation methods to collect many graph instances. Then, the experimental results on the collected dataset offer accuracy of 97.0878% for binary classification and 94.56% for value prediction.

References

D.M. Cvetkovic, “Applications of graph spectra: An introduction to the literature," Application Graph Spectra, vol. 13, no. 21, pp. 7-31, 2009.

Z. Ahmad, Z.S. Mufti, M.F. Nadeem, H. Shaker and H. M. A. Siddiqui, “Theoretical study of energy, inertia and nullity of phenylene and anthracene," Open Chemistry, vol. 19, no. 1, pp. 541-547, 2021.

M.T. Chu, “A note on the homotopy method for linear algebraic eigenvalue problems," Linear Algebra and its Applications, vol. 105, pp. 225-236, 1988.

I.S. Dhillon, B.N. Parlett and C. Vömel, “The design and implementation of the MRRR algorithm," ACM Transactions on Mathematical Software (TOMS), vol. 32, no. 4, pp. 533-560, 2006.

L. Wang, “Nullity of a graph in terms of path cover number," Linear and Multilinear Algebra, vol. 69, no. 10, pp. 1902-1908, 2021.

J. Von Zur Gathen and J. Gerhard, “Modern computer algebra," Cambridge university press, 2013.

R. Naresh and U. Sharma, “Nullity of corona of a path with Smith graphs," European Journal of Pure and Applied Mathematics, vol. 10, no. 5, pp. 1050-1057, 2017.

A. E. Brouwer, “Some simple graph spectra," Eindhoven, 2021.

D. Han and J. Zhang, “A comparison of two algorithms for predicting the condition number," in Sixth International Conference on Machine Learning and Applications (ICMLA 2007), 2007.

T. Xuezhong and B. Liu, "On the nullity of unicyclic graphs," Linear Algebra and its Applications, vol. 408, pp. 212-220, 2005.

S. Hu, T. Xuezhong and B. Liu, “On the nullity of bicyclic graphs," Linear Algebra and its Applications, vol. 429, pp. 1387-1391, 2008.

B. Cheng and B. Liu, “On the nullity of tricyclic graphs," Linear algebra and its applications, vol. 434, pp. 1799-1810, 2011.

Y.Z. Fan and K.S. Qian, “On the nullity of bipartite graphs," Linear algebra and its applications, vol. 430, pp. 2943-2949, 2009.

G. Omidi, “On the nullity of bipartite graphs," Graphs and Combinatorics, vol. 25, no. 1, pp. 111-114, 2009.

D.M. Cvetkovic and I. M. Gutman, “The algebraic multiplicity of the number zero in the spectrum of a bipartite graph," Matematicki vesnik, vol. 9, no. 56, pp. 141-150, 1972.

J.M. Guo, W. Yan and Y.-N. Yeh, “On the nullity and the matching number of unicyclic graphs," Linear Algebra and its Applications, vol. 431, no. 8, pp. 1293- 1301, 2009.

L. Wang and D. Wong, “Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank," Discrete Applied Mathematics, vol. 166, pp. 276-281, 2014.

X. Ma, D. Wong and F. Tian, “Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices," Discrete Applied Mathematics, vol. 215, pp. 171-176, 2016.

H. Ma and X. Liu, “A Characterization of Graphs with Rank No More Than 5," Applied Mathematics, vol. 8, no. 1, pp. 26-34, 2017.

B. Cheng and B. Liu, “On the nullity of graphs," The Electronic Journal of Linear Algebra, vol. 16, pp. 60-67, 2007.

G.J. Chang, L.H. Huang and H.G. Yeh, “A characterization of graphs with rank 4," Linear Algebra and its Applications, vol. 434, no. 8, pp. 1793-1798, 2011.

G.J. Chang, L.H. Huang and H.-G. Yeh, “A characterization of graphs with rank 5," Linear Algebra and its Applications, vol. 436, no. 11, pp. 4241-4250, 2012.

D.M. Cvetkovic, B. DOOB and H. SACHS, “Spectra of graphs. Theory and application," Academic Press, vol. 87, pp. 1-368, 1980.

Y.Z. Song, X.Q. Song and M. Zhang, “An upper bound for the nullity of a bipartite graph in terms of its maximum degree," Linear and Multilinear Algebra, vol. 64, no. 6, pp. 1107-1112, 2016.

I.H. Witten, E. Frank, M. A. Hall and C. J. Pal, “Data Mining: Practical machine learning tools and techniques," Morgan Kaufmann, 2016.

MATLAB, version 9.12.0 (R2022a), Natick, Massachusetts: The MathWorks Inc., 2022.

Prediction nullity of graph using data mining