Betweenness is a well-known centrality measure that ranks the nodes according to their participation in the shortest paths of a network. In several scenarios, having a high betweenness can have a positive impact on the node itself. Hence, in this paper we consider the problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. In particular, we study the problem of maximizing the betweenness score of a given node - Maximum Betweenness Improvement (MBI) - and that of maximizing the ranking of a given node - Maximum Ranking Improvement (MRI). We show that MBI cannot be approximated in polynomial-time within a factor 1-1/(2e) and that MRI does not admit any polynomial-time constant factor approximation algorithm, both unless P=NP. We then propose a simple greedy approximation algorithm for MBI with an almost tight approximation ratio and we test its performance on several real-world networks. We experimentally show that our algorithm highly increases both the betweenness score and the ranking of a given node ant that it outperforms several competitive baselines. To speed up the computation of our greedy algorithm, we also propose a new dynamic algorithm for updating the betweenness of one node after an edge insertion, which might be of independent interest. Using the dynamic algorithm, we are now able to compute an approximation of MBI on networks with up to 105 edges in most cases in a matter of seconds or a few minutes.
Complex networks are increasingly used to model various real-world phenomena. Realistic generative network models simplify complex network research regarding data sharing, reproducibility, and scalability studies. Random hyperbolic graphs (RHGs) are a very promising family of geometric graphs with unit-disk neighborhood in the hyperbolic plane. Previous work provided empirical and theoretical evidence that this generative graph model creates networks with many realistic features. In this work we provide a new generation algorithm for RHGs. We prove its time complexity to be O((n^(3/2)+m) log n) with high probability and confirm this running time experimentally. While a recent theoretical result suggests the generation of RHGs in expected linear time, it has not been put to practice so far. Thus, our implementation is currently the only one running in subquadratic time; it is at least two orders of magnitude faster than a previous implementation -- the latter allows more general neighborhoods than the unit disk, but uses the vanilla generation process. Networks with billions of edges can now be generated in a few minutes. The acceleration stems primarily from the reduction of pairwise distance computations through a polar quadtree, which we adapt to hyperbolic space for this purpose and which can be of independent interest. Due to this acceleration, one can analyze for the first time massive (\ie with billions of edges) generated RHGs in practice. Our empirical analysis shows that RHGs are indeed similar to real-world networks with respect to many (but not all) considered network properties, for example a power-law degree distribution.
It is known that the problem of deciding $k$-colorability of a graph exhibits an easy-hard-easy pattern, with the maximal complexity being either at $k=\chi-1$ or $k=\chi$, where $\chi$ is the chromatic number of the graph. However, the behavior around the complexity peak is poorly understood. In this paper, we use list coloring to model coloring with a fractional number of colors between $\chi-1$ and $\chi$. We present a comprehensive computational study on the complexity of graph coloring in this critical range. According to our findings, an easy-hard-easy pattern can be observed on a finer scale between $\chi-1$ and $\chi$ as well. The highest complexity found this way can be higher than for any integer value of $k$. It turns out that the complexity follows a periodic 3-dimensional pattern; understanding these patterns is very important for benchmarking purposes. Our results also answer the previously open question whether coloring with $\chi-1$ or with $\chi$ colors is harder: this depends on the location of the maximal fractional complexity.
Betweenness Centrality (BC) is a widely used metrics of the relevance of a node in a network. The fastest-know algorithm for the evaluation of BC on unweighted graphs builds a tree representing information about the shortest-paths for each vertex to calculate its contribution to the BC score. Actually, for specific vertices, the shortest-path trees of neighboring nodes could be leveraged to reduce the computational burden but existing BC algorithms do not exploit that information and carry out redundant computations. We propose a new algorithm, called dynamic merging of frontiers (DMF) which makes use of such information to derive the BC score of degree-2 vertices by re-using the results of the sub-trees of the neighbors. We implemented our idea in parallel fashion exploiting Graphics Processing Units (GPU). Compared to state-of-the-art implementations, our approach achieves a linear improvement in the number of degree-2 vertices and an average improvement of 4x over a variety of real-world graphs.