Narmina Baghirova
narmina.baghirova@unifr.ch
+41 26 300 9353
https://orcid.org/000000024702673X

Diploma Assistant / Assistant paid with thirdparty funding,
Department of Informatics
PER 21 bu. C310
Bd de Pérolles 90
1700 FribourgPER 21, C310
Biography
Short bio:
I completed my bachelor’s degree program in Mathematics at the University of Primorska, Koper, Slovenia. Further, I obtained a master’s degree in Mathematical Sciences from the same institution. Moreover, I have done an exchange semester at Universidad del Pais Vasco in Spain and Eötvös Lorand University in Hungary.
Currently, I am pursuing a PhD under the supervision of Prof. Bernard Ries at the University of Fribourg.
My research interests are:
 Algorithmic Graph Theory
 Computational Complexity
 Structural Graph Theory
 Combinatorial Optimization
What my PhD thesis is about
We investigate the problem of finding kcommunity structures in graphs. A kcommunity structure is a partition of the vertex set of a graph into k “communities”, where each community is an induced subgraph such that each vertex has proportionally as many neighbours in its own community as in any other. One of the motivations behind is the following. Any social network such as Facebook or Instagram can be modeled as a graph, where vertices represent members of the social network and edges represent the relations between the members. Intuitively, whenever we are interested in finding an induced subgraph in such a model such that each vertex has more “relations” inside of the subgraph rather than outside, we are looking for a “community”.
There are only few known results about the existence of kcommunities in a graph and the complexity of finding one. The notion of community structure is closely related to the notion of PDS (proportionally dense subgraph). When k=2, finding a 2community in a graph is equivalent to partitioning the graph into 2 PDS. In addition, another related problem we currently work on is the Max PDS problem. The goal is to determine the size of a maximum (with respect to the number of vertices) PDS. Our goal is to obtain new results in this direction.
PhD advisors: Prof. Bernard Ries and Dr. David Schindl.
Research and publications

Publications
4 publications
Finding kcommunity structures in special graph classes
Baghirova, N. and Dallard, C. and Ries, B. and Schindl, D. , Research Square (2023)  Other