Maximizing Algebraic Connectivity in Interconnected Networks

Algebraic connectivity, the second eigenvalue of the Laplacian matrix, is a measure of node and link connectivity on networks. When studying interconnected networks it is useful to consider a multiplex model, where the component networks operate together with inter-layer links among them. In order t...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2015-10
Main Authors: Shakeri, Heman, Albin, Nathan, Faryad Darabi Sahneh, Poggi-Corradini, Pietro, Scoglio, Caterina
Format: Article
Language:English
Subjects:
Algebra
Budgeting
Budgets
Connectivity
Eigenvalues
Links
Multilayers
Multiplexing
Networks
Optimization
Weight
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Algebraic connectivity, the second eigenvalue of the Laplacian matrix, is a measure of node and link connectivity on networks. When studying interconnected networks it is useful to consider a multiplex model, where the component networks operate together with inter-layer links among them. In order to have a well-connected multilayer structure, it is necessary to optimally design these inter-layer links considering realistic constraints. In this work, we solve the problem of finding an optimal weight distribution for one-to-one inter-layer links under budget constraint. We show that for the special multiplex configurations with identical layers, the uniform weight distribution is always optimal. On the other hand, when the two layers are arbitrary, increasing the budget reveals the existence of two different regimes. Up to a certain threshold budget, the second eigenvalue of the supra-Laplacian is simple, the optimal weight distribution is uniform, and the Fiedler vector is constant on each layer. Increasing the budget past the threshold, the optimal weight distribution can be non-uniform. The interesting consequence of this result is that there is no need to solve the optimization problem when the available budget is less than the threshold, which can be easily found analytically.
ISSN:2331-8422
DOI:10.48550/arxiv.1510.06785