International audience
-
April 2022 (v1)Journal articleUploaded on: December 3, 2022
-
May 2022 (v1)Journal article
A novel reinforcement learning algorithm is introduced for multiarmed restless bandits with average reward, using the paradigms of Q-learning and Whittle index. Specifically, we leverage the structure of the Whittle index policy to reduce the search space of Q-learning, resulting in major computational gains. Rigorous convergence analysis is...
Uploaded on: December 3, 2022 -
March 2018 (v1)Journal article
Consider a single server system serving a multiclass population. Some popular scheduling policies for such system are the discriminatory processor sharing (DPS), discriminatory random order service (DROS), generalized processorsharing (GPS) and weighted fair queueing (WFQ). In this paper, we propose two classes of policies, namely MPS...
Uploaded on: December 4, 2022 -
April 8, 2019 (v1)Conference paper
We consider the large graphs as the object of study and deal with the problem of escape probability estimation. Generally, the required characteristic cannot be calculated analytically and even numerically due to the complexity and large size of the investigation object. The purpose of this paper is to offer the effective method for estimating...
Uploaded on: December 4, 2022 -
October 6, 2022 (v1)Book
This book is a general introduction to the statistical analysis of networks, and can serve both as a research monograph and as a textbook. Numerous fundamental tools and concepts needed for the analysis of networks are presented, such as network modeling, community detection, graph-based semi-supervised learning and sampling in networks. The...
Uploaded on: February 22, 2023 -
June 2019 (v1)Journal article
We consider a novel model of stochastic replicator dynamics for potential games that converts to a Langevin equation on a sphere after a change of variables. This is distinct from the models of stochastic replicator dynamics studied earlier. In particular, it is ill-posed due to non-uniqueness of solutions, but is amenable to a natural...
Uploaded on: December 4, 2022 -
May 17, 2018 (v1)Conference paper
We study the relaxation time in the random walk with jumps. The random walk with jumps combines random walk based sampling with uniform node sampling and improves the performance of network analysis and learning tasks. We derive various conditions under which the relaxation time decreases with the introduction of jumps.
Uploaded on: December 4, 2022 -
December 10, 2019 (v1)Conference paper
Random geometric graphs are good examples of random graphs with a tendency to demonstrate community structure. Vertices of such a graph are represented by points in Euclid space $R^d$ , and edge appearance depends on the distance between the points. Random geometric graphs were extensively explored and many of their basic properties are...
Uploaded on: December 4, 2022 -
January 10, 2021 (v1)Conference paper
In this paper we consider a graph clustering problem with a given number of clusters and approximate desired sizes of the clusters. One possible motivation for such task could be the problem of databases or servers allocation within several given large computational clusters, where we want related objects to share the same cluster in order to...
Uploaded on: December 4, 2022 -
October 7, 2020 (v1)Conference paper
Nowadays, Semi-Supervised Learning (SSL) on citation graph data sets is a rapidly growing area of research. However, the recently proposed graph-based SSL algorithms use a default adjacency matrix with binary weights on edges (citations), that causes a loss of the nodes (papers) similarity information. In this work, therefore, we propose a...
Uploaded on: December 4, 2022 -
March 2018 (v1)Journal article
We consider the task of scheduling a crawler to retrieve from several sites their ephemeral content. This is content, such as news or posts at social network groups, for which a user typically loses interest after some days or hours. Thus development of a timely crawling policy for ephemeral information sources is very important. We first...
Uploaded on: December 4, 2022 -
November 23, 2020 (v1)Journal article
Random geometric graphs have become now a popular object of research. Defined rather simply, these graphs describe real networks much better than classical Erdős–Rényi graphs due to their ability to produce tightly connected communities. The $n$ vertices of a random geometric graph are points in $d$-dimensional Euclidean space, and two vertices...
Uploaded on: December 4, 2022 -
September 24, 2019 (v1)Conference paper
We revisit the Whittle index policy for scheduling web crawlers for ephemeral content proposed in Avrachenkov and Borkar, IEEE Trans. Control of Network Systems 5(1), 2016, and develop a reinforcement learning scheme for it based on LSPE(0). The scheme leverages the known structural properties of the Whittle index policy.
Uploaded on: December 4, 2022 -
July 6, 2019 (v1)Conference paper
In semi-supervised graph clustering setting, an expert provides cluster membership of few nodes. This little amount of information allows one to achieve high accuracy clustering using efficient computational procedures. Our main goal is to provide a theoretical justification why the graph-based semi-supervised learning works very well....
Uploaded on: December 4, 2022 -
October 18, 2019 (v1)Book section
We consider a coalition formation among players, in an $n$-player strategic game, over infinite horizon. At each time a randomly selected coalition makes a joint deviation, from a current action profile to a new action profile, which is strictly beneficial for all the players belonging to the coalition.Such deviations define a stochastic...
Uploaded on: December 4, 2022 -
December 17, 2018 (v1)Conference paper
Motivated by various applications from Internet congestion control to power control in smart grids and electric vehicle charging, we study Generalized Additive Increase Multiplicative Decrease (G-AIMD) dynamics under impulsive control in continuous time with the time average alpha-fairness criterion. We first show that the control under relaxed...
Uploaded on: December 4, 2022 -
December 2018 (v1)Journal article
Motivated by applications in telecommunications, computer science and physics, we consider a discrete-time Markov process with restart. At each step the process either with a positive probability restarts from a given distribution, or with the complementary probability continues according to a Markov transition kernel. The main contribution of...
Uploaded on: December 4, 2022 -
November 17, 2020 (v1)Conference paper
Due to high utility in many applications, from social networks to blockchain to power grids, deep learning on non-Euclidean objects such as graphs and manifolds, coined Geometric Deep Learning (GDL), continues to gain an ever increasing interest. We propose a new Lévy Flights Graph Convolutional Networks (LFGCN) method for semi-supervised...
Uploaded on: December 4, 2022 -
June 20, 2021 (v1)Conference paper
A novel framework called Graph Diffusion & PCA (GDPCA) is proposed in the context of semi-supervised learning on graph structured data. It combines a modified Principal Component Analysis with the classical supervised loss and Laplacian regularization, thus handling the case where the adjacency matrix is sparse and avoiding the curse of...
Uploaded on: December 3, 2022 -
March 15, 2021 (v1)Journal article
The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalization, which we call higher-order spectral clustering. It resembles in concept the classical spectral clustering method but uses for partitioning the eigenvector...
Uploaded on: December 4, 2022 -
May 18, 2020 (v1)Conference paper
For providing quick and accurate results, a search engine maintains a local snapshot of the entire web. And, to keep this local cache fresh, it employs a crawler for tracking changes across various web pages. However, finite bandwidth availability and server restrictions impose some constraints on the crawling frequency. Consequently, the ideal...
Uploaded on: December 4, 2022 -
December 12, 2017 (v1)Conference paper
We consider the Generalized Additive Increase Multiplicative Decrease (G-AIMD) dynamics for resource allocation with alpha fairness utility function. This dynamics has a number of important applications such as internet congestion control, charging electric vehicles, and smart grids. We prove indexability for the special case of MIMD model and...
Uploaded on: March 25, 2023 -
December 20, 2021 (v1)Conference paper
A search engine uses a web crawler to crawl the pages from the world wide web (WWW) and aims to maintain its local cache as fresh as possible. Unfortunately, the rates at which different pages change in WWW are highly nonuniform and also, unknown in many real-life scenarios. In addition, the finite available bandwidth and possible server...
Uploaded on: December 3, 2022 -
February 2022 (v1)Journal article
A search engine maintains local copies of different web pages to provide quick search results. This local cache is kept up-to-date by a web crawler that frequently visits these different pages to track changes in them. Ideally, the local copy should be updated as soon as a page changes on the web. However, finite bandwidth availability and...
Uploaded on: December 3, 2022