Updating and downdating techniques for optimizing network communicability

Francesca Arrigo, Michele Benzi

Research output: Contribution to journalArticle

18 Citations (Scopus)
5 Downloads (Pure)

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 as a 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.
Original languageEnglish
Pages (from-to)B25-B49
Number of pages25
JournalSIAM Journal on Scientific Computing
Volume38
Issue number1
DOIs
Publication statusPublished - 6 Jan 2016

Keywords

  • network analysis
  • eigenvector centrality
  • subgraph centrality
  • total communicability
  • edge centrality
  • free energy
  • natural connectivity

Fingerprint Dive into the research topics of 'Updating and downdating techniques for optimizing network communicability'. Together they form a unique fingerprint.

  • Cite this