Updating and downdating techniques for optimizing network communicability
From MaRDI portal
Publication:3460271
DOI10.1137/140991923zbMATH Open1328.05174arXiv1410.5303OpenAlexW2964046693MaRDI QIDQ3460271FDOQ3460271
Authors: Francesca Arrigo, Michele Benzi 
Publication date: 7 January 2016
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: The total communicability of a network (or graph) is defined as the sum of the entries in the exponential of the adjacency matrix of the network, possibly normalized by the number of nodes. This quantity offers a good measure of how easily information spreads across the network, and can be useful in the design of networks having certain desirable properties. The total communicability can be computed quickly even for large networks using techniques based on the Lanczos algorithm. In this work we introduce some heuristics that can be used to add, delete, or rewire a limited number of edges in a given sparse network so that the modified network has a large total communicability. To this end, we introduce new edge centrality measures which can be used to guide in the selection of edges to be added or removed. Moreover, we show experimentally that the total communicability provides an effective and easily computable measure of how "well-connected" a sparse network is.
Full work available at URL: https://arxiv.org/abs/1410.5303
Recommendations
- Communication in complex networks
- Edge modification criteria for enhancing the communicability of digraphs
- Some bounds for total communicability of graphs
- Sensitivity of Matrix Function Based Network Communicability Measures: Computational Methods and A Priori Bounds
- Network properties revealed through matrix functions
network analysisfree energyeigenvector centralityedge centralitysubgraph centralitynatural connectivitytotal communicability
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Connectivity (05C40) Matrix exponential and similar functions of matrices (15A16) Numerical computation of matrix exponential and similar matrix functions (65F60)
Cites Work
- The University of Florida sparse matrix collection
- Functions of Matrices
- Network analysis via partial spectral factorization and Gauss quadrature
- Title not available (Why is that?)
- Emergence of Scaling in Random Networks
- Title not available (Why is that?)
- A new status index derived from sociometric analysis
- Collective dynamics of `small-world' networks
- Networks. An introduction.
- Title not available (Why is that?)
- Expander graphs and their applications
- Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
- Matrices, moments and quadrature with applications
- Quadrature rule-based bounds for functions of adjacency matrices
- Network analysis. Methodological foundations.
- Robustness of random graphs based on graph spectra
- Expansion of random graphs: new proofs, new results
- Implementation of a restarted Krylov subspace method for the evaluation of matrix functions
- Complex networks. Structure, robustness and function.
- Optimization Strategies for the Vulnerability Analysis of the Electric Power Grid
- On the limiting behavior of parameter-dependent network centrality measures
- Communicability graph and community structures in complex networks
- Bounds for the entries of matrix functions with applications to preconditioning
Cited In (21)
- Network properties revealed through matrix functions
- The e-MoM approach for approximating matrix functionals
- Title not available (Why is that?)
- Matrix functions in network analysis
- Gaussianization of the spectra of graphs and networks. Theory and applications
- A new method optimizing the subgraph centrality of large networks
- Vector estimates for \(f(A)\mathbf b\) via extrapolation
- Edge importance in a network via line graphs and the matrix exponential
- Lower and upper bounds on graph communicabilities
- Edge modification criteria for enhancing the communicability of digraphs
- Low-rank updates of matrix functions
- Communicability angle and the spatial efficiency of networks
- Sensitivity of Matrix Function Based Network Communicability Measures: Computational Methods and A Priori Bounds
- Some bounds for total communicability of graphs
- On the radius of centrality in evolving communication networks
- Communication in complex networks
- Node and Layer Eigenvector Centralities for Multiplex Networks
- Exploring the “Middle Earth” of network spectra via a Gaussian matrix function
- Accounting for the role of long walks on networks via a new matrix function
- Tuned communicability metrics in networks. The case of alternative routes for urban traffic
- Enhancing multiplex global efficiency
Uses Software
This page was built for publication: Updating and downdating techniques for optimizing network communicability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460271)
