Search for content and authors
 

Hyperbolic geometry and real life networks

Dorota Celińska 1,  Eryk Kopczyński 2

1. University of Warsaw, Faculty of Economic Sciences, 44/50, Długa St., Warsaw 00-241, Poland
2. University of Warsaw, Faculty of Mathematics, Informatics and Mechanics (MIMUW), Warsaw 02-097, Poland

Abstract

Drawing graphs as nodes connected by links is visually compelling but computationally difficult [1]. In hyperbolic plane, the amount of space in distance d from the given point is exponential in d. Recently it was shown that hyperbolic geometry is intrinsic in many real world networks, and especially useful while modeling large scale-free networks based on similarity and popularity [2]. An efficient embedding algorithm has been recently shown [3]. Unfortunately, this algorithm does not deal with weighted networks, and may not give visually appealing results. Furthermore, no powerful tools exist to visualize such embeddings of graphs. In this article, we present and discuss the goodness of fit of the hyperbolic embeddings of selected networks. RogueViz, a novel tool, based on the Open Source game HyperRogue, is used to map the network and navigate the hyperbolic graph.

  •  Trees embedded in hyperbolic plane
Hyperbolic trees employ hyperbolic space, which intrinsically has ``more room'' than Euclidean space.  The result usually reduces visual clutter and helps focus. We present two visualizations of trees embedded in hyperbolic plane: an evolution tree of life on Earth (Tree of Life web project) with 94309 nodes, and an infinite tree of Collatz Conjecture. In the visualization of Collatz Conjecture, the descendants of each number are the possible numbers which precede it (e.g. 8 could be immediately preceded by 5 or 16).

  • Programming languages in GitHub
We present aa visualization of a weighted network of programming lanugages used by the registered users of GitHub repository hosting service as of December 2016. GitHub is currently the largest software repository hosting service devoted to Open Source software that incorporates social media functionalities to writing and assessing source code. Since the complete download of GitHub data is impossible, our dataset is combined from three sources: GHTorrent project, GitHub Archive project, and our own dataset obtained by web-scrapping GitHub. The resulting dataset contains information about the activity of 10,620,313 users in 42,636,285 repositories.

  • Games discussed on r/roguelikes

We present a visualization of the games discussed in r/roguelikes, constructed upon the posts and comments from Jul 6, 2016 to Mar 11, 2017 which have been downloaded via the Reddit API. For each Reddit user and each game the number of posts/comments where the given user has mentioned the given game is counted. If a user U mentions game A na times and game B nb times, the games A and B attract themselves with force nanb/fU, where fu is chosen so that the total contribution of user U is proportional to the square root of his total number of mentions.

The algorithm we use to embed the networks is based on simulated annealing. Our findings suggest that modeling social networks embedded in hyperbolic plane can improve knowledge about the latent communities. Vertices sharing similar properties tend to be mapped close together. The Poincare model enables sort of ``fish-eye'' view at the whole network, comfortable for quick investigation of popularity of nodes. Analyses of log-likelihood reveal that hyperbolic embeddings predict noticeably better the existence of edges in the networks compared to the predictions made by their Euclidean counterparts.

  1. [1] Munzner, T. 1998. Exploring large graphs in 3d hyperbolic space. IEEE Computer Graphics and Applications 18(4):18–23.
  2. [2] Papadopoulos, F.; Kitsak, M.; Serrano, M. A.; Boguna, M.; and Krioukov, D. 2012. Popularity versus Similarity in Growing Networks. Nature 489:537–540.
  3. [3] Blasius, T.; Friedrich, T.; Krohmer, A.; and Laue, S. 2016. Efficient embedding of scale-free graphs in the hyperbolic plane. In European Symposium on Algorithms (ESA), 16:1–16:18.

 

Legal notice
  • Legal notice:

    Copyright (c) Pielaszek Research, all rights reserved.
    The above materials, including auxiliary resources, are subject to Publisher's copyright and the Author(s) intellectual rights. Without limiting Author(s) rights under respective Copyright Transfer Agreement, no part of the above documents may be reproduced without the express written permission of Pielaszek Research, the Publisher. Express permission from the Author(s) is required to use the above materials for academic purposes, such as lectures or scientific presentations.
    In every case, proper references including Author(s) name(s) and URL of this webpage: https://science24.com/paper/32833 must be provided.

 

Presentation: Poster at Econophysics Colloquium 2017, Symposium A, by Dorota Celińska
See On-line Journal of Econophysics Colloquium 2017

Submitted: 2017-04-11 23:39
Revised:   2017-04-12 08:01