PROXNET · Modelling Complex Networks Through Graph Editing Problems
Horizon 2020 — Marie Skłodowska-Curie Actions
- Duration
- 2018-02-01 → 2020-01-31
- EU contribution
- €208,400
- Participants
- 1
- Scheme
- MSCA-IF
Lines connect the coordinator with its partners.
Results in brief
Modelling Complex Networks Through Graph Editing Problems
The goal of the PROXNET project is to open a new way for analysing, modelling and managing complex networks, through graph editing problems. The reason why these networks are said to be complex is that they are loosely structured, due to the part of uncertainty and randomness they contain. On the other hand, the real-world context where they come from strongly constrains their organisation and gives them some specific structure. The difficulty in retrieving this structure is that it is altered by the noise resulting from the uncertainty and randomness that these networks contain. In the PROXNET project, we retrieve the hidden structures of complex networks thanks to graph editing problems, which consist in changing some adjacencies of the graph in order to obtain a desired property. We develop the algorithms necessary to solve graph editing problems on huge instances of graphs, we apply them to real-world datasets and use the results obtained in order to design new models of complex networks.
Data: CORDIS, © European Union
Project objective
The goal of the PROXNET project, which will be realised during the mobility of Christophe Crespelle in the Algorithms groupof Bergen, is to open a new way for analysing, modelling and managing complex networks, through graph editing problems.The reason why these networks are said to be complex is that they are loosely structured, due to the part of uncertainty andrandomness they contain. On the other hand, the real-world context where they come from strongly constrains theirorganisation and gives them some specific structure. The difficulty in retrieving this structure is that it is altered by the noiseresulting from the uncertainty and randomness that these networks contain. In the PROXNET project, we will retrieve thehidden structures of complex networks thanks to graph editing problems, which consist in changing some adjacencies of thegraph in order to obtain a desired property. We will develop the algorithms necessary to solve graph editing problemsrelevant to our approach on huge instances of graphs, we will apply them to real-world datasets and use the results obtainedin order to design new models of complex networks.One key theoretic challenge in this context is to optimally solve the editing problems considered, which are computationallydifficult (NP-hard). A very promising technique to do so is preprocessing. It consists in reducing the size of the instance byapplying some reduction rules, in such a way that the optimal solution on the reduced instance is the same as the one on theoriginal instance. The Algorithms group of the University of bergen is a world-wide leader on this topic which will constitutethe main training action of Christophe Crespelle during his mobility.
Original text from CORDIS.
Participants
- UNIVERSITETET I BERGEN · BergenCoordinatorNorway
Links
Data: CORDIS, © European Union