Titulo Estágio
Heuristics for the k-plex problem
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
DEI-FCTUC / ECOS
Enquadramento
Given a simple undirected graph G=(V,E) and an integer k >= 1, a k-plex is a subset of nodes P contained in V such that any node i in P is adjacent to at least |P|-k nodes from P, that is, all nodes in P have degree at least |P|-k in the subgraph induced by P. The k-plex concept is a degree-based relaxation of the well-known notion of a clique. In effect, a 1-plex is a clique in which all nodes are fully connected to each other. Then, for growing values of k, the k-plex reduces de degree condition, allowing each node in P to miss up to k-1 connections to the other nodes in the set.
The k-plex problem is to find the largest cardinality k-plex in G. This problem was first introduced in (Seidman & Foster, 1978) and its main motivation was related with the fact that in many social and biological networks, to find a clique component can be much restrictive, particularly when we are dealing with false negative links (edges) in the network or other kind of missing links.
Objetivo
The student should develop an heuristic method based on iterated local search for the k-plex problem and conduct a number of computational tests in order to compare the performance of the algorithm with exact and approximate methods in the literature.
Plano de Trabalhos - Semestre 1
- Literature review: Notions of graphs and combinatorial optimization, heuristics and k-plex problems.
- Notions of neighborhood for the k-plex problem
- Design of basic local search for the k-plex problem
- Writing of the intermediate report
Plano de Trabalhos - Semestre 2
- Notions of perturbations for the k-plex problem
- Design of iterated local search for the k-plex problem
- Computational experiments
- Writing of the thesis
Condições
This MSc project is for students that would like to deepen his knowledge on algorithms and combinatorial optimization. The MSc student can use the computational resources from ECOS group for performing experiments. This project has no funding available.
Observações
References:
- Seidman, S.B., Foster, B.L., 1978. A graph theoretic generalization of the clique concept. Journal of Mathematical Sociology 6, 139–154.
Balasundaram, B., 2008. Cohesive subgroup model for graph-based text mining. In: 4th IEEE International Conference on Automation Science and Engineering - CASE 2008. pp. 989-994.
- Balasundaram, B., Butenko, S., Hicks, I.V., Sachdeva, S., 2006. Clique relaxations in social network analysis: the maximum k-plex problem. URL http://ie.tamu.edu/people/faculty/butenko/papers/kplex060127.pdf. Manuscript.
- Balasundaram, B., Butenko, S., Hicks, I.V., Sachdeva, S., 2008. Clique relaxations in social network analysis: The maximum k-plex problem. URL http://iem.okstate.edu/baski/files/kplex4web.pdf. Manuscript.
- Everett, M.G., Borgatti, S.P., 2000. Peripheries of cohesive subsets. Social Networks 21(4), 397-407.
- Grosso, A., Locatelli, M., Pullan, W., 2008. Simple ingredients leading to very efficient heuristics for the maximum clique problem. Journal of Heuristics 14, 587–612.
- Huber, W., Carey, V. J., Long, L., Falcon, S., Gentleman, R., 2007. Graphs in molecular biology. BMC bioinformatics 8(Suppl 6), S8.
Martins, P., 2010. Extended and discretized formulations for the maximum clique problem. Computers & Operations Research 37(7), 1348-1358.
- McClosky, B., Hicks, I.V., 2009. Combinatorial algorithms for the maximum k-plex problem. URL http://www.caam.rice.edu/∼bjm4/CombiOptPaper.pdf. Manuscript.
- Moser, H., Niedermeier, R., Sorge, M., 2009. Algorithms and experiments for clique relaxations - finding maximum s-plexes. In: Experimental Algorithms. Springer-Verlag, Berlin, Heidelberg. pp. 233-244.
- Mukherjee, M., Holder, L.B., 2004. Graph-based data mining on social networks URL http://www.cs.cmu.edu/~dunja/LinkKDD2004/Maitrayee-Mukherjee-LinkKDD-2004.pdf. Manuscript.
- Pattillo, J., Youssef, N., Butenko, S., 2012. On clique relaxation models in network analysis. European Journal of Operational Research 226(1), 9-18.
- Rothenberg, R. B., Potterat, J. J., Woodhouse, D. E., Muth, S. Q., Darrow, W. W., Klovdahl, A. S., 1998. Social network dynamics and HIV transmission. AIDS 12(12), 1529-1536.
- Rothenberg, R. B., et al., 2000. The Atlanta Urban Networks Study: a blueprint for endemic transmission. AIDS 14(14), 2191-2200.
- Trukhanov, S., Balasubramaniam, C., Balasundaram, B., Butenko, S., 2013. Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Computational Optimization and Applications 56(1), 1-18.
- Wu, B., Pei, X., 2007. A parallel algorithm for enumerating all the maximal k-plexes. In: Washio T., et al. (Eds.), PAKDD 2007 Workshop LNAI 4819. Springer-Verlag, Berlin, Heidelberg. pp. 476-483.
Orientador
Luís Paquete e Pedro Martins (ISCAC)
paquete@dei.uc.pt 📩