Abstract
This paper presents our ongoing work on the Vertex Separator Problem (VSP), and its application to knowledge discovery in graphs representing real data. The classic VSP is modeled as an integer linear program. We propose several variants to adapt this model to graphs with various properties. To evaluate the relevance of our approach on real data, we created two graphs of different size from the IMDb database. The model was applied to the separation of these graphs. The results demonstrate how the model is able to semantically separate graphs into clusters.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Information courtesy of IMDb (http://www.imdb.com). Used with permission.
References
Balas, E., de Souza, C.: The vertex separator problem: a polyhedral investigation. Math. Program. 103(3), 583–608 (2005)
Benlic, U., Hao, J.K.: Breakout local search for the vertex separator problem. In: IJCAI (2013)
Bui, T.N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inf. Process. Lett. 42(3), 153–159 (1992)
Davis, T.A.: Direct Methods for Sparse Linear Systems, vol. 2. SIAM, Philadelphia (2006)
Didi Biha, M., Meurs, M.J.: An exact algorithm for solving the vertex separator problem. J. Glob. Optim. 49(3), 425–434 (2011)
Fu, B., Oprisan, S.A., Xu, L.: Multi-directional width-bounded geometric separator and protein folding. Int. J. Comput. Geom. Appl. 18(05), 389–413 (2008)
Fukuyama, J.: NP-completeness of the planar separator problems. J. Graph Algorithms Appl. 10(2), 317–328 (2006)
Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W.H. Freeman, New York (2002)
Hager, W.W., Hungerford, J.T.: Continuous quadratic programming formulations of optimization problems on graphs. Eur. J. Oper. Res. 240(2), 328–337 (2015)
Kanevsky, A.: Finding all minimum size separating vertex sets in a graph. Coordinated Science Laboratory Report no. ACT-93 (UJLU-ENG 88–2233) (1988)
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)
Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27–64 (2007)
Schuchard, M., Geddes, J., Thompson, C., Hopper, N.: Routing around decoys. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, pp. 85–96. ACM (2012)
de Souza, C., Balas, E.: The vertex separator problem: algorithms and computations. Math. Program. 103(3), 609–631 (2005)
Ullman, J.D.: Computational Aspects of VLSI. Computer Science Press, Rockville (1984)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Sarfati, M., Queudot, M., Mancel, C., Meurs, MJ. (2017). Knowledge Discovery in Graphs Through Vertex Separation. In: Mouhoub, M., Langlais, P. (eds) Advances in Artificial Intelligence. Canadian AI 2017. Lecture Notes in Computer Science(), vol 10233. Springer, Cham. https://doi.org/10.1007/978-3-319-57351-9_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-57351-9_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-57350-2
Online ISBN: 978-3-319-57351-9
eBook Packages: Computer ScienceComputer Science (R0)