Estimating Fiedler Value on Large Networks Based on Random Walk Observations

In this paper, we describe an iterative scheme which is able to estimate the Fiedler value of a network when the topology is initially unknown. The only available information is the one obtained through a random walk process over the network. Our algorithm is based on the Rayleigh quotient optimizat...

Full description

Saved in:
Bibliographic Details
Main Authors: Reiffers-Masson, Alexandre, Chonavel, Thierry, Hayel, Yezekael
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Conferences
Fiedler value
Iterative algorithms
Network topology
random walk based observations
Signal processing
Signal processing algorithms
stochastic approximation
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we describe an iterative scheme which is able to estimate the Fiedler value of a network when the topology is initially unknown. The only available information is the one obtained through a random walk process over the network. Our algorithm is based on the Rayleigh quotient optimization problem and the theory of stochastic approximation. We explain the different tools used to construct our algorithm and we describe our iterative scheme. Finally, we illustrate its performance through a numerical study.
ISSN:2379-190X
DOI:10.1109/ICASSP39728.2021.9413713