Publications related to Flooding And Diameter In General Weighted Random Graphs

Recovering Static and Time-Varying Communities Using Persistent Edges

This article focuses on spectral methods for recovering communities in temporal networks. In the case of fixed communities, spectral clustering on the simple time-aggregated graph (i.e., the weighted graph formed by the sum of the interactions over all tem ...

Ieee Computer Soc2024

Equivariant Neural Architectures for Representing and Generating Graphs

Clément Arthur Yvon Vignac

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entitie ...

EPFL2023

A tutorial on graph models for scheduling round-robin sports tournaments

Dominique de Werra

Many sports leagues organize their competitions as round-robin tournaments. This tournament design has a rich mathematical structure that has been studied in the literature over the years. We review some of the main properties and fundamental scheduling me ...

WILEY2023

Distributed Graph Learning With Smooth Data Priors

Pascal Frossard, Mireille El Gheche, Isabela Cunha Maia Nobre

Graph learning is often a necessary step in processing or representing structured data, when the underlying graph is not given explicitly. Graph learning is generally performed centrally with a full knowledge of the graph signals, namely the data that live ...

IEEE2022

On the robustness of the metric dimension of grid graphs to adding a single edge

Patrick Thiran, Gergely Odor, Satvik Mehul Mashkaria

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

2022

The power of adaptivity in source identification with time queries on the path

Patrick Thiran, Gergely Odor, Victor Cyril L Lecomte

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph

G=(V,E)

, an unknown source node

v^* \in V

is drawn uniformly at random, ...

2022

Sequential metric dimension for random graphs

Patrick Thiran, Gergely Odor

In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...

2021

Non-Exponential Variations for Classical Results in First Passage Percolation

Jacques Saliba

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges. We start by describing the asymptotic behavior of the diameter and the f ...

EPFL2020

Community-Aware Graph Signal Processing: Modularity Defines New Ways of Processing Graph Signals

Dimitri Nestor Alice Van De Ville, Thomas William Arthur Bolton, Raphaël Pierre Liégeois

The emerging field of graph signal processing (GSP) allows one to transpose classical signal processing operations (e.g., filtering) to signals on graphs. The GSP framework is generally built upon the graph Laplacian, which plays a crucial role in studying ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Simple Realizability of Complete Abstract Topological Graphs Simplified

Jan Kyncl

An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...

SPRINGER2020

Flooding And Diameter In General Weighted Random Graphs

Graph Chatbot

Chat with Graph Search

Recovering Static and Time-Varying Communities Using Persistent Edges

Equivariant Neural Architectures for Representing and Generating Graphs

A tutorial on graph models for scheduling round-robin sports tournaments

Distributed Graph Learning With Smooth Data Priors

On the robustness of the metric dimension of grid graphs to adding a single edge

The power of adaptivity in source identification with time queries on the path

Sequential metric dimension for random graphs

Non-Exponential Variations for Classical Results in First Passage Percolation

Community-Aware Graph Signal Processing: Modularity Defines New Ways of Processing Graph Signals

Simple Realizability of Complete Abstract Topological Graphs Simplified

On the robustness of the metric dimension of grid graphs to adding a single edge

Equivariant Neural Architectures for Representing and Generating Graphs

Simple Realizability of Complete Abstract Topological Graphs Simplified

Recovering Static and Time-Varying Communities Using Persistent Edges

Community-Aware Graph Signal Processing: Modularity Defines New Ways of Processing Graph Signals

Sequential metric dimension for random graphs

The power of adaptivity in source identification with time queries on the path

Distributed Graph Learning With Smooth Data Priors

A tutorial on graph models for scheduling round-robin sports tournaments

Non-Exponential Variations for Classical Results in First Passage Percolation