16th NETWORKS Day

 

The programme is as follows:

 

9:00 – 9:30	Welcome and coffee
9:30 – 10:00	Opening session with a.o. Networkpages
10:00 – 10:30	Artem Tsikiridis (CWI)
10:30 –11:00	Coffee break
11:00 – 12:00	Clara Stegehuis (UT)
12:00 - 13:30	Lunch
13:30 - 14:30	Rui Castro (TU/e)
14:30 - 15:00	Coffee break
15:00 - 16:30	Anurag Bishnoi (TU Delft)
16:30 - 17.30	tour of the museum

 

Artem Tsikiridis (CWI)

 

Core-Selecting and Core-Competitive Mechanisms 

Core-selecting mechanisms, as introduced by Ausubel & Milgrom, have been known to possess good revenue guarantees and some of their variants have been used in practice especially for spectrum and other public sector auctions. Despite their popularity, it has also been demonstrated that these auctions are generally non-truthful. As a result, current research has focused either on identifying core-selecting mechanisms with minimal incentives to deviate from truth-telling, such as the family of Minimum-Revenue Core-Selecting (MRCS) rules, or on proposing truthful mechanisms whose revenue is competitive against core outcomes. The results we present contribute to both of these directions. We start with studying the core polytope in more depth and provide new properties and insights, related to the effects of unilateral deviations from a given profile. We then utilize these properties in two ways.  

 

Clara Stegehuis (UT)

 

Maximal cliques: theory vs practice

While many graph-based problems are in theory NP complete, for many such problems there exist algorithms that run extremely quickly on large-scale real-world networks. This shows a disparity between theory and practice: while some theoretical examples exist on which any algorithm can take extremely long, these graphs do usually not appear in real-world networks. Therefore, it is often possible to show that these problems can be solved efficiently on random graph with realistic network properties.

 

In this talk, we focus on algorithms that list all cliques in a graph. We show that this problem can take an exponential time even on many classes of random graphs with realistic network properties. However, here again a disparity between theory and practice arises: while we can show an exponential lower bound on the running time of this problem with a max-clique based algorithm, this lower bound is dominated by a linear term for all practical purposes.

 

Rui Castro (TU/e)

 

Detecting a (late) changepoint in the preferential attachment model

Motivated by the problem of detecting a change in the evolution of a network, we consider the preferential attachment random graph model with a time-dependent attachment function. We frame this as a hypothesis testing problem where the null hypothesis is a preferential attachment model with $n$ vertices and a constant affine attachment with parameter $\delta_0$, and the alternative hypothesis is a preferential attachment model where the affine attachment parameter changes from $\delta_0$ to $\delta_1$ at an unknown changepoint time $\tau_n$. For our analysis we focus on a scenario where one only sees the final network realization (and not its evolution), and the changepoint occurs “late”, namely $\tau_n = n − cn^\gamma$ with $c \geq 0$ and $\gamma\in(0,1)$. This corresponds to the relevant scenario where we aim to detect the changepoint shortly after it has happened. We present two asymptotically powerful tests that are able to distinguish between the null and alternative hypothesis when $\gamma>1/2$. The first test requires knowledge of $\delta_0$, while the second test is significantly more involved, and does not require the knowledge of $\delta_0$ while still achieving the same performance guarantees. Furthermore, we determine the asymptotic distribution of the test statistics, which allows us to easily calibrate the tests in practice. Finally, we conjecture that in the setting considered there are no powerful tests when $\gamma<1/2$. Our theoretical results are complemented with numerical evidence that illustrates the finite sample characteristics of the proposed procedures. (based on joint work with Gianmarco Bet, Kay Bogerd, and Remco van der Hofstad).

 

Anurag Bishnoi (TUD)

 

Blocking sets and minimal codes from expander graphs

Finite geometry has played an important role in giving constructions of various interesting families of graphs. In this talk, I will show that the other direction can be equally fruitful. By using explicit constant-degree expanders, and asymptotically good codes, we give an explicit construction of (asymptotically) optimal strong blocking sets in finite projective spaces. Our construction resolves one of the main open problems on (linear) minimal codes, as these codes have recently been shown to be equivalent to strong blocking sets.