Networks

NETWORKS day

On Monday, June 16, the next and final NETWORKS Day will take place at the University Museum Utrecht. Because of this special occasion, the setup will be slightly different than usual. You are warmly invited to join this final edition of the Networks day.


Throughout the NETWORKS day, presentations will be delivered by Ferenc Bencs (CWI), Akrati Saxena (Leiden University) and Yasamin Nazari (Vrije Universiteit Amsterdam). The program begins at 13:00 AM and concludes with a buffet at the restaurant of "De Oude Hortus" in Utrecht. 

 

Programme

13.00 - 13.30 Coffee and welcome
13.30 - 14.20 Akrati Saxena (Leiden University)
14.20 - 14.50 Break
14.50 - 15.40 Yasamin Nazari (Vrije Universiteit Amsterdam)
15.40 - 16.10 Break
16.10 - 17.00 Ferenc Bencs (CWI)
17.00 - 20.00 Drinks and dinner

 

Abstracts

 

Akrati Saxena

Algorithmic Fairness in Social Network Analysis: FairSNA

In recent years, designing fairness-aware methods has received much attention in various domains, including machine learning, natural language processing, and information retrieval. However, understanding structural bias and inequalities in social networks and designing fairness-aware methods for various research problems in social network analysis (SNA) have not received much attention. 

This talk will explain how structural inequalities impact fairness of SNA methods, focusing on a case study of link prediction. I will first provide an overview of link prediction techniques and then explore how these methods can amplify existing biases. Next, I will discuss approaches to encounter structural biases for fair and diverse link prediction. I will cover one method in-depth for diverse link prediction using NodeSim network embedding method that efficiently captures the diverse neighborhood while keeping more similar nodes closer in the context of a given node. This will provide insights on how fairness can be incorporated in SNA. This discussion will offer insights into integrating fairness into SNA methodologies. Finally, I will briefly introduce algorithmic fairness in other SNA problems and highlight overall research interests of our lab.
   

Yasamin Nazari

Graph Distance Structures and their Algorithmic Applications

In recent years there has been a growing interest in studying graph theoretical structures used for designing efficient algorithms in various computational models, such as dynamic, parallel and distributed models.

In this talk, I focus on distance structures which are objects that preserve approximate distances in a graph, but tradeoff this approximation factor with space, query time, or the number of hops on the approximate shortest paths. I will also discuss how these structures can be utilized for faster shortest path computation in dynamic and parallel models. 

 

Ferenc Bencs

Two tales of sink-free orientations
In this talk we will investigate the (number of) sink-free orientations in a graph. It turns out this number is actually #P hard to compute for general graphs. Using the fact that any orientation can be checked whether it's sink-free using local information, quite efficient randomized algorithms were developed to approximate the number sink-free orientations. Very recently the first deterministic algorithm was introduced by Anand et. al. In this talk, we will further exploit its close relation to the Lovász Local lemma and improve on the best deterministic approximation algorithm for this number if the minimum degree of the graph is at least 3. 
As a different application, we will determine the rate of the reliability probability of random regular graphs, which is the probability that after a 1/2-percolation, the graph remains connected.
The results are based on joint works with Márton Borbényi, Péter Csikvári and Guus Regts.

 

 

Details

16 June 2024

Location

universiteitsmuseum-utrecht

 

University Museum Utrecht

Lange Nieuwstraat 106

3512 PN Utrecht

Website