Finding central nodes is a fundamental problem in network analysis. Betweenness centrality is a well-known measure which quantifies the importance of a node based on the fraction of shortest paths going though it. Due to the dynamic nature of many today’s networks, algorithms that quickly update centrality scores have become a necessity. For betweenness, several dynamic algorithms have been proposed over the years, targeting different update types (incremental- and decremental-only, fully-dynamic). In this paper we introduce a new dynamic algorithm for updating betweenness centrality after an edge insertion or an edge weight decrease. Our method is a combination of two independent contributions: a faster algorithm for updating pairwise distances as well as number of shortest paths, and a faster algorithm for updating dependencies. Whereas the worst-case running time of our algorithm is the same as recomputation, our techniques considerably reduce the number of operations performed by existing dynamic betweenness algorithms. Our experimental evaluation on a variety of real-world networks reveals that our approach is significantly faster than the current state-of-the-art dynamic algorithms, approximately by one order of magnitude on average.

Small-world networks have characteristically low pairwise shortest-path distances, causing distance-based layout methods to generate hairball drawings. Recent approaches thus aim at finding a sparser representation of the graph to amplify variations in pairwise distances. Since the effect of sparsification on the layout is difficult to describe analytically, the incorporated filtering parameters of these approaches typically have to be selected manually and individually for each input instance. We here propose the use of graph invariants to determine suitable parameters automatically. This allows us to perform adaptive filtering to obtain drawings in which the cluster structure is most prominent. The approach is based on an empirical relationship between input and output characteristics that is derived from real and synthetic networks.Experimental evaluation shows the effectiveness of our approach and suggests that it can be used by default to increase the robustness of force-directed layout methods.

We show that most algorithms from the literature on listing the triangles of a graph have a common abstraction. Our unifying framework highlights that these seemingly different algorithms are in fact instantiations of a single generic procedure, and even suggests some additional variants. More importantly, it yields parsimonious implementations that are in general more efficient than those described in the original works. In addition, we show that the running time of nearly every triangle listing variant is in (a(G)m), where a(G) is the arboricity of the graph and m the number of edges. So far this bound has been proven only for Chiba and Nishizeki's (SIAM J. Computing, 1985) triangle listing algorithm. Finally, algorithmic experimentation reveals that an improved implementation of this algorithm outperforms all subsequently proposed algorithms.