The week's pick
Random Articles
Reseach Article
Graph Neural Network for Minimum Dominating Set
| 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
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
- 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
- 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
- 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.
- 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
- 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
- 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
- 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
- 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
- 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
- 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.
- 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.
- Gary Chartrand. , Ping Zhang 2006. Introduction to Graph theory, Tata McGraw-Hill, India, ISBN: 0-07-061608-6, pp. 361.
Index Terms
Keywords