Narmina Baghirova
narmina.baghirova@unifr.ch
+41 26 300 9353
https://orcid.org/0000-0002-4702-673X
-
Diploma Assistant / Assistant paid with third-party 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 k-community structures in graphs. A k-community 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 k-communities 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 2-community 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 k-community structures in special graph classes
Baghirova, N. and Dallard, C. and Ries, B. and Schindl, D. , Research Square (2023) | Other