In this paper we investigate the structural properties of betweenness cen-trality and determine some cases in which betweenness reaches its extremal values. Special attention is paid to Star(G), the set of vertices adjacent to all other vertices in a graph and we prove several results about the betweenness of the elements of this set. We introduce the new concept of total betweenness and relate it to group betweenness. We prove a necessary and sufficient condition for the two measures to coincide. Next we consider cutsets and cutvertices and we find a lower bound for their betweenness; in particular for a cutvertex this lower bound is the cutting number. Finally we apply the previous results to trees, proving an alternative formula for betweenness based on cutvertex properties.

Grassi, R., Scapellato, R., Stefani, S., & Torriero, A. (2009). Betweenness Centrality: Extremal Values and Structural Properties. In A. Naimzada, S. Stefani, & A. Torriero (a cura di), Networks, Topology and Dynamics. Theory and Applications to Economics and Social Systems (pp. 161-176). Heidelberg : Springer.

Betweenness centrality: Extremal values and structural properties

GRASSI, ROSANNA;STEFANI, SILVANA;
2009

Abstract

In this paper we investigate the structural properties of betweenness cen-trality and determine some cases in which betweenness reaches its extremal values. Special attention is paid to Star(G), the set of vertices adjacent to all other vertices in a graph and we prove several results about the betweenness of the elements of this set. We introduce the new concept of total betweenness and relate it to group betweenness. We prove a necessary and sufficient condition for the two measures to coincide. Next we consider cutsets and cutvertices and we find a lower bound for their betweenness; in particular for a cutvertex this lower bound is the cutting number. Finally we apply the previous results to trees, proving an alternative formula for betweenness based on cutvertex properties.
No
Scientifica
Capitolo o saggio
Graph, betweenness centrality, geodesic, cutvertex, cutset
English
Networks, Topology and Dynamics. Theory and Applications to Economics and Social Systems
978-3-540-68407-7
Grassi, R., Scapellato, R., Stefani, S., & Torriero, A. (2009). Betweenness Centrality: Extremal Values and Structural Properties. In A. Naimzada, S. Stefani, & A. Torriero (a cura di), Networks, Topology and Dynamics. Theory and Applications to Economics and Social Systems (pp. 161-176). Heidelberg : Springer.
Grassi, R; Scapellato, R; Stefani, S; Torriero, A
File in questo prodotto:
File Dimensione Formato  
Betweenness_Centrality_prima_di_copertina.pdf

accesso aperto

Dimensione 1.26 MB
Formato Adobe PDF
1.26 MB Adobe PDF Visualizza/Apri
Betweenness_Centrality_Indice.pdf

accesso aperto

Dimensione 83.14 kB
Formato Adobe PDF
83.14 kB 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: http://hdl.handle.net/10281/4100
Citazioni
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 10
Social impact