Hyperbolic pseudo-betweenness -- initial proposition

Prelegent(ci)

Dorota Celińska-Kopczyńska

Afiliacja

Instytut Informatyki, UW

Termin

19 grudnia 2019 10:15

Pokój

p. 4050

Seminarium

Seminarium „Gry, mechanizmy i sieci społeczne”

---

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.

---