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.

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.

These are shorten versions of the original books by Runestone Interactive. This version has been modified by me for the lectures of Laboratorio di Algoritmi at Informatica Umanistica, University of Pisa. I modified the original version according to GNU Free Documentation License, Version 1.3. I am redistributing the new material under the same License. The original Forward, Prefaces, and Contributor List can be accessed at the end of the table of contents.

Check out the table of contents for basic programming or the one for algorithms and data structures.

Benefits of this book:
– You can experiment with activecode examples right in the book
– You can do your homework right in the textbook.
– Interactive questions make sure that you are on track and help you focus.
– Codelens helps you develop a mental model of how Python works.

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.

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.