CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Graph Neural Network for Minimum Dominating Set

by Gnana Jothi R.b., S. M. Meena Rani
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 56 - Number 1
Year of Publication: 2012
Authors: Gnana Jothi R.b., S. M. Meena Rani
10.5120/8854-2804

Gnana Jothi R.b., S. M. Meena Rani . Graph Neural Network for Minimum Dominating Set. International Journal of Computer Applications. 56, 1 ( October 2012), 12-16. DOI=10.5120/8854-2804

@article{ 10.5120/8854-2804,
author = { Gnana Jothi R.b., S. M. Meena Rani },
title = { Graph Neural Network for Minimum Dominating Set },
journal = { International Journal of Computer Applications },
issue_date = { October 2012 },
volume = { 56 },
number = { 1 },
month = { October },
year = { 2012 },
issn = { 0975-8887 },
pages = { 12-16 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume56/number1/8854-2804/ },
doi = { 10.5120/8854-2804 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:57:44.747913+05:30
%A Gnana Jothi R.b.
%A S. M. Meena Rani
%T Graph Neural Network for Minimum Dominating Set
%J International Journal of Computer Applications
%@ 0975-8887
%V 56
%N 1
%P 12-16
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The dominating set concept in graphs has been used in many applications. In large graphs finding the minimum dominating set is difficult. The minimum dominating set problem in graphs seek a set D of minimum number of vertices such that each vertex of the graph is either in D or adjacent to a vertex in D. In a graph on n nodes if there is a single node of degree n-1 then that single node forms a minimum dominating set. In the proposed work, a designed network called Graph Neural Network (GNN) is used to identify the node of degree N-1 in a graph having a single node of degree N-1 as it forms the minimum dominating set in the graph. . The network is simulated for graphs with nodes varying from 5 to 15. The state dimension of the input vectors are analyzed for better convergence. It has been found that the minimum dominating set was correctly identified from 80% to 90% of the graphs when the state dimension was 2 and 3. It has been observed that when the state dimension was 2, the convergence was fast as it requires minimum hidden neurons than other state dimensions. It has also been observed that when the state dimension was greater than 3, convergence requires hours of time and more number of hidden neurons. GNN was able to identify the minimum dominating set in a graph on n vertices which has a single node of degree n-1.

References
  1. Muratore, D. , Hagenbuchner, M. , Scarselli, F. , Tsoi, A. C. , 2010. Sentence extraction by graph neural network, Proceedings of the 20th International conference on Artificial neural networks, Springer-Verlag, Berlin, Heidelberg, ISBN: 3-642-15824-2 978-3-642-15824-7
  2. Frasconi, M. , Gori, M. , Sperduti, A. , 1998. A general framework for adaptive processing of Data Structures. IEEE Trans. Neural Networks, 9: 768-786. DOI: 10. 1109/72. 712151
  3. Sperduti, A. , Starita, A. , 1997. Supervised Neural networks for the classification of structures. IEEE Trans. Neural Networks, 8: 714-735. DOI: 10. 1109/72. 572108.
  4. Scarselli, F. , Yong, S. L. , Gori, M. Hagenbuchner, M. , Tsoi, A. C. , Maggini, M. , 2005. Graph Neural Networks for Ranking Web Pages, in : Proceedings of the 2005 IEEE/WIC/ACM Int. Conf. on Web Intelligence. DOI: 10. 1109/WI. 2005. 67
  5. Scarselli, F. , Gori, M. , Tsoi, A. C. , Hagenbuchner, M. , Monfardini, G. , 2009. The Graph neural network model. IEEE Trans. Neural Networks, 20: 61 - 78. DOI:10. 1109/TNN. 2008. 2005605
  6. Scarselli, F. , Gori, M. , Tsoi, A. C. , Hagenbuchner, M. , Monfardini, G. , 2009. Computational capabilities of Graph neural networks. IEEE Trans. Neural Networks, 20: 81 - 102. DOI:10. 1109/TNN. 2008. 2005141
  7. Pucci, A. , Gori, M. , Hagenbuchner, M. , Scarselli, F. , Tsoi, A. C. , 2006. Applications of Graph neural networks to large-scale recommender systems some results. Proceedings of International Multiconference on Computer Science and Information Technology pp: 189-195. www. proceedings2006. imcsit. org
  8. Uwents, W. , Monfardini, G. , Blockel, H. , Gori, M. , Scarselli, F. , 2010. Neural networks for relational learning: an experimental comparison, Machine learning, DOI:10. 1007/s10994-010-5196-5
  9. Hongmei, Zhenhuan Zhu, Erkki Makinen, 2009. A Neural network model to minimize the connected dominating set for self-configuration of wireless sensor networks. IEEE Trans. Neural Networks, 20: 973-982. DOI:10. 1109/TNN. 2009. 2015088
  10. Manfordini G. , Di Massa, V. , Scarselli, F. , Gori, M. , 2006, Graph neural network for object localization, Fifth International workshop of the initiative for the evaluation of XML retrieval. DOI 10. 1007/978-3-540-73888-6_43.
  11. Yong, S. L. , Hagenbuchner, M. , Tsoi, A. C. , Scarselli, F. , Gori, M. , 2007, Document mining using Graph neural network, Comparative evaluation of XML retrieval system, Lecture notes in Computer Science, 4518 : pp458 – 472.
  12. Gary Chartrand. , Ping Zhang 2006. Introduction to Graph theory, Tata McGraw-Hill, India, ISBN: 0-07-061608-6, pp. 361.
Index Terms

Computer Science
Information Sciences

Keywords

Minimum dominating set Graph neural network State dimension Feedforward neural network Recursive neural network

Powered by PhDFocusTM