Networks and graphs between geometry and statistics

09.07.2014, 14:00 Uhr  –  Universität Potsdam, Am Neuen Palais 10, Haus 09, Raum 1.12
Institutskolloquium

Ulrike von Luxburg (Hamburg)

• 14:00 Ulrike von Luxburg (Universität Hamburg):
  Complex network science: the quest for understanding the internet, facebook and the brain
• 15:00 Coffee break
• 15:30 Ulrike von Luxburg (Universität Hamburg):
  The geometry of unweighted k-nearest neighbour graphs

Abstracts:
Ulrike von Luxburg (Universität Hamburg): Complex network science: the quest for understanding the internet, facebook and the brain
The field of complex network science studies properties of "natural networks" such as the worldwide web, social networks like facebook, biological networks like protein-interaction networks or the brain. The rationale is that understanding the structure of these networks helps to understand the way they function: how fast can information spread over the network, how vulnerable is a network to adversarial behavior, how much influence is concentrated on a couple of important vertices or edges, does the network consist of many small communities, and so on. In my talk I am going to describe the current state of the art and some of the methods used in that field - you will find that there are many interesting open questions for various kinds of mathematics (such as graph theory, geometry, statistics, optimization, numerics).

Ulrike von Luxburg (Universität Hamburg): The geometry of unweighted k-nearest neighbour graphs
Consider the following game. It is you against me. You pick a secret density on R^d and sample n points from it. Then you build the k-nearest neighbor graph based on this sample: vertices are the sample points, and you connect two points by an edge if they are among the k nearest neighbors of each other. Now you give the adjacency matrix of the graph to me, but nothing else (neither the point coordinates, nor any information about the distances between the points). My task is to find out as much as possible about the secret density that you had chosen in the beginning.
In my talk I will discuss which properties of the density and the geometry of the underlying data that I can recover from the adjacency matrix. On an even higher level, I will relate my findings to questions about ordinal data analysis - with many open questions somewhere between geometry, topology and statistics.