Real-world Graph Analysis: Techniques for Static, Dynamic and Temporal Communities

Graphs are widely used in various fields of computer science. They have also found application in unrelated areas, leading to a diverse range of problems. These problems can be modeled as relationships between entities in various contexts, such as social networks, protein interactions in cells, and route maps. Therefore it is logical to analyze these data structures with diverse approaches, whether they are numerical or structural, global or local, approximate or exact. In particular, the concept of community plays an important role in local structural analysis, as it is able to highlight the composition of the underlying graph while providing insights into what the organization and importance of the nodes in a network look like. This thesis pursues the goal of extracting knowledge from different kinds of graphs, including static, dynamic, and temporal graphs, with a particular focus on their community substructures. To tackle this task we use combinatorial algorithms that can list all the communities in a graph according to different formalizations, such as cliques, k-graphlets, and k-cores. Listing (or enumeration) algorithms indeed give the full set of communities in any graph, in contrast to more algebraic techniques that exploit matrix multiplication, eigenvalues, etc. to obtain an exact or approximate count of certain types of communities, an approach that can be faster in terms of running time, but that does not suit our need for the complete list of subgraphs to perform subsequent analyses. We first develop new algorithms to enumerate subgraphs, using traditional and novel techniques such as push-out amortization, and CPU cache analysis to boost their efficiency. We then extend these concepts to the analysis of real-world graphs across diverse domains, ranging from social networks to autonomous systems modeled as temporal graphs. In this field, there is currently no widely accepted adaptation, even for straightforward subgraphs like k-cores, and the available data is expanding both in terms of quantity and scale. As a result, our findings advance the state of the art both from a theoretical and a practical perspective and can be used in a static or dynamic setting to further speed up and refine graph analysis techniques.