Betweenness centrality profiles in trees

DOI10.1093/COMNET/CNX007MaRDI QIDQ4985069zbMATH OpenOpenAlexFDO

Authors Benjamin Fish, Rahul Kushwaha, Gy. Turán

Publication date 22 April 2021

Published in Journal of Complex Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.02334

zbMATH Keywords

betweenness centralitycentrality profilenetworkstrees

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Betweenness centrality of a vertex in a graph measures the fraction of shortest paths going through the vertex. This is a basic notion for determining the importance of a vertex in a network. The k-betweenness centrality of a vertex is defined similarly, but only considers shortest paths of length at most k. The sequence of k-betweenness centralities for all possible values of k forms the betweenness centrality profile of a vertex. We study properties of betweenness centrality profiles in trees. We show that for scale-free random trees, for fixed k, the expectation of k-betweenness centrality strictly decreases as the index of the vertex increases. We also analyze worst-case properties of profiles in terms of the distance of profiles from being monotone, and the number of times pairs of profiles can cross. This is related to whether k-betweenness centrality, for small values of k, may be used instead of having to consider all shortest paths. Bounds are given that are optimal in order of magnitude. We also present some experimental results for scale-free random trees.

Recommendations

• Betweenness centrality in random trees
• On the distribution of betweenness centrality in random trees
• Betweenness centrality in some classes of graphs
• Betweenness Centrality: Extremal Values and Structural Properties
• Notes on the betweenness centrality of a graph

Cited in

(10)

• On the distribution of betweenness centrality in random trees
• Model spaces of regularity structures for space-fractional SPDEs
• Betweenness centrality of an edge in tree-like components with finite size
• A breadth-first search with betweenness
• scientific article; zbMATH DE number 6096696 (Why is no real title available?)
• Betweenness Centrality: Extremal Values and Structural Properties
• scientific article; zbMATH DE number 6863841 (Why is no real title available?)
• Betweenness centrality in random trees
• Ranking trees based on global centrality measures
• Bounds and relations involving adjusted centrality of the vertices of a tree

This page was built for publication: Betweenness centrality profiles in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4985069)