- This event has passed.
Lecture day on the occasion of visit Ravi Kumar
Apr 15, 2019, 10:00 - 14:30
Summary
Ravi Kumar (Google) will visit the Netherlands, April 15-18. There will be a lecture day to mark this visit. Held at Eurandom on Monday April 15th.
Sponsor
Speakers
| Luca Avena | Leiden University |
| Remco van der Hofstad | TU Eindhoven |
| Julia Komjathy | TU Eindhoven |
| Ravi Kumar |
Program
More information
For questions please contact Nelly Litvak
Abstracts
Luca Avena
Network data-sets: randomized decomposition through forests and some related tools
I will discuss some probabilistic tools and related randomized algorithms to explore the architecture of a data set stored in a network structure (an arbitrary weighted finite graph).
The core idea is to decompose the network in a randomized multiscale fashion by using certain spanning rooted forests.
These objects are related to fundamental algebraic and probabilistic structures of a given weighted graph (or of the associated adjacency matrix).
The applications I will present include:1) a procedure for downsampling sets of well-distributed nodes/vertices 2) coarse-graining or reduction schemes 3) pyramidal wavelets-like algorithms to process signals on graphs.
(joint work with Fabienne Castell, Alexandre Gaudilliere and Clothilde Melot)
Remco van der Hofstad
Relating structure and function of complex networks
Many phenomena in the real world can be phrased in terms of networks. Examples include the World-Wide Web, social interactions and Internet, but also the interaction patterns between proteins, food webs and citation networks. Many large-scale networks have, despite their diversity in backgrounds, surprisingly much in common. Many of these networks are small worlds, in the sense that one requires few links to hop between pairs of vertices. Also the variability of the number of connections between elements tends to be enormous, which is related to the scale-free phenomenon.
We are interested in the relations between the structure of complex networks and their functionality. Complex networks are generally modeled by random graphs, while their functionality is described in terms of stochastic processes living on them (such as information diffusion), or algorithms acting on them (such as PageRank). There obviously are strong relations between the structure of networks, such as their degree or community structures, and the behavior of stochastic processes and algorithms on them.
In this lecture, we describe a few real-world networks and some of their empirical properties, as well as some of the simple models for them. We then give examples of how the degree distribution determines graph distances in some random graph models, and the behavior of stochastic processes such as percolation and rumor spread. We also discuss the behavior of two algorithms, PageRank and assortativity. We speculate on how models can be improved to better describe real-world networks, and on how this can change their functionality. Time permitting, we discuss the real-world example of citation networks.
Julia Komjathy
Short weighted distances in scale-free spatial random graphs
In the talk we describe the connection between two network models, and study distances in both models: hyperbolic random graphs (HRG), and geometric inhomogeneous random graphs (GIRG). In HRGs, n=Θ(eR/2) vertices are sampled independently from the hyperbolic disk with radius R and two vertices are connected either when they are within hyperbolic distance R, or independently with a probability depending on the hyperbolic distance. In GIRGs, each vertex is given an independent weight and location from an underlying measured metric space and Zd, respectively, and two vertices are connected independently with a probability that is a function of their distance and weights. We describe a transformation that maps HRGs to a specific GIRG.
In the second part of the talk, we assign i.i.d. weights to the edges of the random graphs and study the weighted distance between two uniformly chosen vertices.
In particular, we study the case when the parameters are so that the degree distribution in the graph follows a power law with exponent τ∈(2,3) (infinite variance), and the edge-weight distribution is such that it produces an explosive age-dependent branching process with power-law offspring distribution. We show that in both models, typical distances within the giant component converge in distribution as the number of vertices tends to infinity, in particular, they do not tend to infinity with the size of the network.
This simplified model can explain why some videos, memes, etc can spread very quickly on the internet.
Ravi Kumar
Random Walks and Network Properties
A random walk is a natural way to explore a network. We will study the use of uniform random walks to estimate various properties such as the size of the network, average degree, number of triangles, etc.
Less obvious random walks can also be designed to do other tasks such as uniformly generating a node or counting network motifs. However, our perspective is that one has to be careful in using random walks for applications.
Practical Information
● Venue
Eurandom, Mathematics and Computer Science Department, TU Eindhoven,
De Groene Loper 5, 5612 AE EINDHOVEN, The Netherlands
Eurandom is located on the campus of Eindhoven University of Technology, in the MetaForum building, 4th floor (more about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.
● Conference facilities
Conference room, MetaForum Building “MF 11 & 12”.
The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants giving an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.
● Conference Secretariat
Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.
● Cancellation
Should you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.
● Contact
Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl