I am very grateful to the Department of Computer Science in Pisa, which hosted me for the last four years and gave me the opportunity to grow in such a nice environment.

It has been a very nice event, full of interesting short presentations of past and current PhD students. As Luca and Alessio (which are respectively current and past PhD students) were not in Italy, I presented a short summary of our works about community detection.

There is a video and there are also the pictures

It has been a great conference. Below the abstract of our paper.

We investigate a decomposition technique for listing problems in graphs and set systems. It is based on the Cartesian product of some iterators, which list the solutions of simpler problems. Our ideas applies to several problems, and we illustrate one of them in depth, namely, listing all minimum spanning trees of a weighted graph G. Here iterators over the spanning trees for unweighted graphs can be obtained by a suitable modification of the listing algorithm by [Shioura et al., SICOMP 1997], and the decomposition of G is obtained by suitably partitioning its edges according to their weights. By combining these iterators in a Cartesian product scheme that employs Gray coding, we give the first algorithm which lists all minimum spanning trees of G in constant delay, where the delay is the time elapsed between any two consecutive outputs. Our solution requires polynomial preprocessing time and uses polynomial space.

Here below the abstract:

Bitcoin is a novel decentralized cryptocurrency system which has recently received a great attention from a wider audience. An interesting and unique feature of this system is that the complete list of all the transactions occurred from its inception is publicly available. This enables the investigation of funds movements to uncover interesting properties of the Bitcoin economy. In this paper we present a set of analyses of the user graph, i.e. the graph obtained by an heuristic clustering of the graph of Bitcoin transactions. Our analyses consider an up-to-date Bitcoin blockchain, as in December 2015, after the exponential explosion of the number of transactions occurred in the last two years. The set of analyses we defined includes, among others, the analysis of the time evolution of Bitcoin network, the verification of the “rich get richer” conjecture and the detection of the nodes which are critical for the network connectivity.

Here below the abstract:

Due to the sheer size of real-world networks, delay and space become quite relevant measures for the cost of enumeration in network analytics. This paper presents efficient algorithms for listing maximum cliques in networks, providing the first sublinear-space bounds with guaranteed delay per enumerated clique, thus comparing favorably with the known literature.

A connected road network with N nodes and L edges has K \leq L edges identified as one-way roads. In a feasible direction, these one-way roads are assigned a direction each, so that every node can reach any other [Robbins ’39]. Using O(L) preprocessing time and space usage, it is shown that all feasible directions can be found in O(K) amortized time each.
To do so, we give a new algorithm that lists all the strong orientations of an undirected connected graph with $m$ edges in O(m) amortized time each, using O(m) space.
The cost can be deamortized to obtain O(m) delay with O(m^2) preprocessing time and space.

Thanks to my coauthors: Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, and Luca Versari

The abstract follows.

We study enumeration problems for the acyclic orientations of an undirected graph with n nodes and m edges, where each edge must be assigned a direction so that the resulting directed graph is acyclic. When the acyclic orientations have single or multiple sources specified as input along with the graph, our algorithm is the first one to provide guaranteed bounds, giving new bounds with a delay of O(m n) time per solution and O(m+n) working space. When no sources are specified, our algorithm improves over previous work by reducing the delay from O(m n) to O(m) time, and is the first ones with linear delay.

Thanks to all my coauthors: Alessio Conte, Roberto Grossi, and Romeo Rizzi.

Here the abstract is.

The edge clique covering (ECC) problem deals with discovering a set of (possibly overlapping) cliques in a given network, such that each edge is part of at least one of these cliques.
We address the ECC problem from an alternative perspective reconsidering the quality of the cliques found, and proposing more structured criteria with respect to the traditional measures such as minimum number of cliques.
In the case of real-world networks, having millions of nodes, such as social networks, the possibility of getting a result is constrained to the running time, which should be linear or almost linear in the size of the network. Our algorithm for finding ECCs of large networks has linear-time performance in practice, as our experiments show on real-world networks whose number of nodes ranges from thousands to several millions.

Thanks to my coauthors Alessio Conte and Roberto Grossi.

Thanks to all the coauthors Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi and Henning Meyerhenke. This work is the result of a merge between our work (see here) and the work by Elisabetta and Henning. It’s a pleasure to start this new collaboration.

This is the abstract of the final paper.

Centrality indices are widely used analytic measures for the importance of nodes in a network.
Closeness centrality is very popular among these measures. For a single node v, it takes the sum of
the distances of v to all other nodes into account. The currently best algorithms in practical applications
for computing the closeness for all nodes exactly in unweighted graphs are based on breadth-first search (BFS) from every node. Thus, even for sparse graphs, these algorithms require quadratic running time in the worst case,
which is prohibitive for large networks.

In many relevant applications, however, it is unnecessary to compute closeness values for all nodes. Instead,
one requires only the k nodes with the highest closeness values in descending order.
Thus, we present a new algorithm for computing this top-k ranking in unweighted graphs. Following the rationale of previous work, our algorithm significantly reduces the number of traversed edges. It does so by computing upper bounds on the closeness and stopping the current BFS search when k nodes already have higher closeness than the bounds computed for the other nodes.

In our experiments with real-world and synthetic instances of various types, one of these new bounds is good for small-world graphs with low diameter (such as social networks), while
the other one excels for graphs with high diameter (such as road networks). Combining them
yields an algorithm that is faster than the state of the art for top-k computations for all test instances,
by a wide margin for high-diameter graphs.

Finally, we prove that the quadratic worst-case complexity cannot be improved on directed, disconnected graphs, under reasonable complexity assumptions.