The first paper is a joint work with Alessio Conte, Tiziano De Matteis, Daniele De Sensi, Roberto Grossi, and Luca Versari, with title “D2K: Scalable Community Detection in Massive Networks via Small-Diameter k-Plexes”.

This paper studies k-plexes, a well known pseudo-clique model for network communities. In a k-plex, each node can miss at most k-1 links. Our goal is to detect large communities in today’s real-world graphs which can have hundreds of millions of edges. While many have tried, this task has been elusive so far due to its computationally challenging nature: k-plexes and other pseudo-cliques are harder to find and more numerous than cliques, a well known hard problem. We present D2K, which is the first algorithm able to find large k-plexes of very large graphs in just a few minutes. The good performance of our algorithm follows from a combination of graph-theoretical concepts, careful algorithm engineering and a high-performance implementation. In particular, we exploit the low degeneracy of real-world graphs, and the fact that large enough k-plexes have diameter 2. We validate a sequential and a parallel/distributed implementation of D2K on real graphs with up to half a billion edges.

The second paper is a joint work with Alessio Conte, Gaspare Ferraro, Roberto Grossi, Kunihiko Sadakane, and Takeaki Uno with title “Node Similarity with q -Grams for Real-World Labeled Networks”

We study node similarity in labeled networks, using the label sequences found in paths of bounded length q leading to the nodes. (This recalls the q-grams employed in document resemblance, based on the Jaccard distance.) When applied to networks, the challenge is two-fold: the number of q-grams generated from labeled paths grows exponentially with q, and their frequency should be taken into account: this leads to a variation of the Jaccard index known as Bray-Curtis index for multisets. We describe nSimGram, a suite of fast algorithms for node similarity with q-grams, based on a novel blend of color coding, probabilistic counting, sketches, and string algorithms, where the universe of elements to sample is exponential. We provide experimental evidence that our measure is effective and our running times scale to deal with large real-world networks.

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.

Given a connected graph G of m edges and n vertices, we consider the basic problem of listing all the choices of k vertex-disjoint st-paths, for any two input vertices s,t of G and a positive integer k. Our algorithms take O(m) time per solution, using O(m) space and requiring O(F_k(G)) setup time, where F_k(G) = O(m min{k, n^{2/3} log n, sqrt{m} log n} ) is the cost of running a max-flow algorithm on~G to compute a flow of size k. The proposed techniques are simple and apply to other related listing problems as discussed in the paper.

The paper has been a joint work with Alessio Conte, Roberto Grossi, Takeaki Uno and Luca Versari. Below the abstract.

An independent set is a set of nodes in a graph such that no two of them are adjacent. It is maximal if there is no node outside the independent set that may join it. Listing maximal independent sets in graphs can be applied, for example, to sample nodes belonging to different communities or clusters in network analysis and document clustering. The problem has a rich history as it is related to maximal cliques, dominance sets, minimum vertex covers and 3-colorings in graphs. We are interested in reducing the delay, which is the worst-case time between any two consecutively output solutions, and the memory footprint, which is the additional working space behind the read-only input graph.

A preliminar version appeared at COMPLEX NETWORK 2016, while the final version is now published on Journal Online Social Networks and Media. Here is the abstract:

A unique feature of cryptocurrencies such as Bitcoin is that the blockchain containing all the economic transactions is publicly available. This makes it possible to obtain insights in the behaviour of the users through an analysis of the topological properties of the users graph which is derived from the Bitcoin transaction graph through clustering heuristics. In a previous work, we have analysed the users graph and discovered that the graph is not a small world, due to the presence of outliers in the in-degree frequency distribution of the nodes and of a high diameter, in spite of a small average distance between the nodes of the graph. In this paper, we explain our findings, showing that these structural properties of the network are due to peculiar unusual patterns in the users graph. As a further remark, we argue that these patterns are probably due to artificial users behaviours and not strictly related to normal economic interactions.

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