Hyperbolic pseudo-betweenness -- initial proposition

Speaker(s)

Dorota Celińska-Kopczyńska

Affiliation

Instytut Informatyki, UW

Date

Dec. 19, 2019, 10:15 a.m.

Room

room 4050

Seminar

Seminar Games, Mechanisms, and Social Networks

---

Centrality measures identify nodes that play an important role within the network. Betweenness centrality is interpreted roughly as the fraction of all shortest paths in the network between two nodes that contain the given node. The node is more important, the more shortest paths go through it. The calculation of the shortest paths between all pairs of nodes on a graph is needed to compute scores for betweenness centrality. As a result, all known propositions are reasonably computationally expensive. However, after embedding a network into the hyperbolic plane using the Discrete Hyperbolic Random Graph model, we can reinterpret the definition of the centrality measure, obtaining the hyperbolic "pseudo-betweenness". It is well known that tree-like graphs admit good algorithmic properties. In particular, our hyperbolic pseudo-betweenness measures can be computed in time O(n R^O(1)), where R is the radius of our tessellation; R is small (logarithmic in n). We compare our hyperbolic pseudo-betweenness measures with the standard betweenness and other centrality measures.

---