This paper introduces the notions of chained and semi-chained graphs. The chain of a graph, when existent, refines the notion of bipartivity and conveys important structural information. Also the notion of a center vertex vc is introduced. It is a vertex, whose sum of p powers of distances to all other vertices in the graph is minimal, where the distance between a pair of vertices { vc, v} is measured by the minimal number of edges that have to be traversed to go from vc to v. This concept extends the definition of closeness centrality. Applications in which the center node is important include information transmission and city planning. Algorithms for the identification of approximate central nodes are provided and computed examples are presented.

Chained graphs and some applications

Rodriguez G.;
2021

Abstract

This paper introduces the notions of chained and semi-chained graphs. The chain of a graph, when existent, refines the notion of bipartivity and conveys important structural information. Also the notion of a center vertex vc is introduced. It is a vertex, whose sum of p powers of distances to all other vertices in the graph is minimal, where the distance between a pair of vertices { vc, v} is measured by the minimal number of edges that have to be traversed to go from vc to v. This concept extends the definition of closeness centrality. Applications in which the center node is important include information transmission and city planning. Algorithms for the identification of approximate central nodes are provided and computed examples are presented.
multipartition; network analysis; chained graph; central node
File in questo prodotto:
File Dimensione Formato  
chain21.pdf

accesso aperto

Tipologia: versione editoriale
Dimensione 4.59 MB
Formato Adobe PDF
4.59 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/314473
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact