Network Theory

Working Group Network Theory

Presentation

Topic: Theory that can be used to study networks.

Audience: The reading group Network Theory is intended for researchers in mathematics and computer science interested in networks, but anyone can attend online.

Practical details: The sessions are held every third Wednesday from 10:30 am to 11:30 pm (Central European Summer Time), in the premises of the Lincs and online. To receive the invitations, register to the mailing list. Videos, slides and notebooks of previous sessions are on the website.

Coordinator: François Durand (fradurand@gmail.com).

Description:

In the reading group Network Theory, members present works from the scientific or technical literature to the other members. Our field of interest covers all theoretical aspects that can be used by researchers dealing with networks (graphs, telecommunication networks, social networks, power grids, etc). This includes general theoretical tools that are not specific to networks.

In the past sessions, we covered topics such as:

• Algorithmics: Ukkonen algorithm, efficient partitionning (1, 2), learning regular sets (Angluin’s algorithm), edit distances, algorithms for random permutations, weakest failure detector, numerical evaluation of multiple integrals, sorting under partial information.
• Analytic combinatorics: Birth-and-death processes, Mellin transform (1, 2), random walks, typical subgraphs of random graphs, Laplace’s method, exact digraph enumeration, enumerating bipartite graphs with degree constraints, Gaussian limit laws and generating series.
• Game theory: mechanism design (1, 2), Poisson games, voting in networks, multi-winner voting rules, reputation systems, no-show paradox, emerging collective behaviors, cake cutting, tournament solutions.
• Graph theory: stable matchings, PageRank, stream graphs theory.
• Information theory: “A mathematical theory of communication” – Shannon’s seminal paper (1, 2, 3), algebra for quantum information, an information-theoretic perspective on tf-idf measures, mutual information neural estimation, entropy as a topological operad derivation.
• Linear algebra: non-negative matrix factorization, probabilistic algorithms for matrix decompositions.
• Machine learning: deep neural networks, recurrent neural networks, sequence-to-sequence learning, knowledge graph embeddings, cascade-correlation learning, tropical geometry of DNNs (1, 2), K-nearest neighbors, transformer models, deep Q-Learning, supervised learning of rare categories, suport-vector networks, zap stochastic approximation and reinforcement learning, ensemble methods, the projection method for community detection.
• Networks architecture: C-RAN, chaos engineering, MIMO, wireless communications.
• Optimization: convex optimization, Bayesian optimization, submodular functions.
• Probability theory: random walks on graphs, Bayesian networks, hidden Markov models (1, 2), multi-armed bandits (1, 2), exponential families, Poisson approximations of sums of Bernoulli random variables.
• Quantum computing and networks: introduction to quantum computing (1, 2), quantum internet, quantum cryptography, quantum networks for 5-year old network researchers, Quirk.
• Queueing theory: M/G/1 queue, queuing or not queuing in large systems, fluid limits in queuing networks, fixed points for the ./GI/1 queue, decentralised medium access algorithm, network calculus.
• Security and privacy: differential privacy, Tamarin Prover.
• Statistics: false discovery rate, confidence intervals.
• Stochastic geometry: Replica mean field models, minimal spanning trees on random points, contact process on point processes (1, 2), mean field theory, Poisson-Voronoi tessellation, random line and hyperplane processes, unimodular random graphs, joint communication and sensing.

As a speaker:

• You may present a paper, a set of papers, a book chapter, or prepare a short introduction course to a given topic.
• You do not need to be a specialist of what you present.
• Please do not present your own work.