Graph Partitioning via Recurrent Multivalued Neural Networks

 

Abstract

In this work, the well-known Graph Partitioning (GP) problem for undirected weighted graphs has been studied from two points of view: maximizing (MaxCut) or minimizing (MinCut) the cost of the cut induced in the graph by the partition. An unified model, based on a neural technique for optimization problems, has been applied to these two concrete problems. A detailed description of the model is presented, and the technique to minimize an energy function, that measures the goodness of solutions, is fully described. Some techniques to escape from local optima are presented as well. It has proved to be a very competitive and efficient algorithm, in terms of quality of solutions and computational time, when compared to the state-of-the-art methods. Some simulation results are presented in this paper, to show the comparative efficiency of the methods.

Citation

Please, cite this work as:

[CL05] E. M. Casermeiro and D. López-Rodríguez. “Graph Partitioning via Recurrent Multivalued Neural Networks”. In: Computational Intelligence and Bioinspired Systems, 8th International Work-Conference on Artificial Neural Networks, IWANN 2005, Vilanova i la Geltrú, Barcelona, Spain, June 8-10, 2005, Proceedings. Ed. by J. Cabestany, A. Prieto and F. S. Hernández. Vol. 3512. Lecture Notes in Computer Science. Vilanova i la Geltru: Springer, 2005, pp. 1149-1156. DOI: 10.1007/11494669_141. URL: https://doi.org/10.1007/11494669_141.

BibTeX

@InProceedings{Casermeiro2005a,
     author = {Enrique Mérida Casermeiro and Domingo López-Rodríguez},
     booktitle = {Computational Intelligence and Bioinspired Systems, 8th International Work-Conference on Artificial Neural Networks, {IWANN} 2005, Vilanova i la Geltrú, Barcelona, Spain, June 8-10, 2005, Proceedings},
     title = {Graph Partitioning via Recurrent Multivalued Neural Networks},
     year = {2005},
     address = {Vilanova i la Geltru},
     editor = {Joan Cabestany and Alberto Prieto and Francisco Sandoval Hernández},
     pages = {1149–1156},
     publisher = {Springer},
     series = {Lecture Notes in Computer Science},
     volume = {3512},
     abstract = {In this work, the well-known Graph Partitioning (GP) problem for undirected weighted graphs has been studied from two points of view: maximizing (MaxCut) or minimizing (MinCut) the cost of the cut induced in the graph by the partition. An unified model, based on a neural technique for optimization problems, has been applied to these two concrete problems. A detailed description of the model is presented, and the technique to minimize an energy function, that measures the goodness of solutions, is fully described. Some techniques to escape from local optima are presented as well. It has proved to be a very competitive and efficient algorithm, in terms of quality of solutions and computational time, when compared to the state-of-the-art methods. Some simulation results are presented in this paper, to show the comparative efficiency of the methods. © Springer-Verlag Berlin Heidelberg 2005.},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/conf/iwann/CasermeiroL05.bib},
     document_type = {Conference Paper},
     doi = {10.1007/11494669_141},
     journal = {Lecture Notes in Computer Science},
     keywords = {Algorithms; Computational methods; Computer simulation; Graph theory; Optimization; Problem solving, Computational time; Graph partitioning; Optimization problems, Neural networks},
     source = {Scopus},
     timestamp = {Tue, 14 May 2019 10:00:51 +0200},
     url = {https://doi.org/10.1007/11494669_141},
}

Bibliometric data

The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.

9

CITATIONS

9 Total citations

0 Recent citations

n/a Field Citation Ratio

n/a Relative Citation Ratio

• Citations
• CrossRef - Citation Indexes: 7
• Scopus - Citation Indexes: 10

• Captures
• Mendeley - Readers: 7

-

see details

Cites

The following graph plots the number of cites received by this work from its publication, on a yearly basis.

Papers citing this work

The following is a non-exhaustive list of papers that cite this work:

[1] M. S. Ansari. “A Voltage-Mode Nonlinear-Synapse Neural Circuit for Bi-partitioning of Graphs”. In: Proceedings of the International Conference on Recent Cognizance in Wireless Communication & Image Processing. Springer India, 2016, p. 151–157. ISBN: 9788132226383. DOI: 10.1007/978-81-322-2638-3_17. URL: http://dx.doi.org/10.1007/978-81-322-2638-3_17.

[2] D. López-Rodríguez and E. Mérida-Casermeiro. “Shortest Common Superstring Problem with Discrete Neural Networks”. In: Adaptive and Natural Computing Algorithms. Springer Berlin Heidelberg, 2009, p. 62–71. ISBN: 9783642049217. DOI: 10.1007/978-3-642-04921-7_7. URL: http://dx.doi.org/10.1007/978-3-642-04921-7_7.

[3] D. López-Rodríguez, E. Mérida-Casermeiro, J. M. Ortíz-de-Lazcano-Lobato, et al. “K-Pages Graph Drawing with Multivalued Neural Networks”. In: Artificial Neural Networks – ICANN 2007. Springer Berlin Heidelberg, 2007, p. 816–825. ISBN: 9783540746959. DOI: 10.1007/978-3-540-74695-9_84. URL: http://dx.doi.org/10.1007/978-3-540-74695-9_84.

[4] R. Luque, D. López-Rodríguez, E. Mérida-Casermeiro, et al. “Video Object Segmentation with Multivalued Neural Networks”. In: 2008 Eighth International Conference on Hybrid Intelligent Systems. IEEE, Sep. 2008, p. 613–618. DOI: 10.1109/his.2008.130. URL: http://dx.doi.org/10.1109/his.2008.130.

[5] E. Mérida-Casermeiro and D. López-Rodríguez. “Drawing Graphs in Parallel Lines with Artificial Neural Networks”. In: 2008 Eighth International Conference on Hybrid Intelligent Systems. IEEE, Sep. 2008, p. 667–671. DOI: 10.1109/his.2008.89. URL: http://dx.doi.org/10.1109/his.2008.89.

[6] E. Mérida-Casermeiro, D. López-Rodríguez, and J. Ortiz-de-Lazcano-Lobato. “An Approach to Artificial Concept Learning Based on Human Concept Learning by Using Artificial Neural Networks”. In: Advancing Artificial Intelligence through Biological Process Applications. IGI Global, 2009, p. 130–145. DOI: 10.4018/978-1-59904-996-0.ch008. URL: http://dx.doi.org/10.4018/978-1-59904-996-0.ch008.

[7] E. Mérida-Casermeiro, D. López-Rodríguez, and J. M. Ortiz-de-Lazcano-Lobato. “MREM, Discrete Recurrent Network for Optimization”. In: Encyclopedia of Artificial Intelligence. IGI Global, 2009, p. 1112–1120. DOI: 10.4018/978-1-59904-849-9.ch163. URL: http://dx.doi.org/10.4018/978-1-59904-849-9.ch163.