Pedro Ribeiro (University of Porto)
One way of understanding the design principles of complex networks is to look at how they are organized at the subgraph level. In this talk I will describe how subgraphs can be seen as fundamental structural units and how they can provide a powerful and very flexible framework for characterizing and comparing networks. I will focus on two concepts geared around this idea, namely network motifs and graphlets/orbits. At the core of these methodologies lies the ability to search and count subgraph occurrences. This is a computationally hard problem and I will talk about the state of the art for this task, describing the g-trie data structure, designed to efficiently represent a collection of graphs and to search for them as induced subgraphs of another larger graph. I will explain how it takes advantage of common substructure and how symmetry breaking conditions can be used to avoid redundant computations. I will explain its general applicability, showcasing how it would work for undirected, directed and colored graphs, and will also briefly discuss sampling and parallel versions of g-trie based methods. I will also talk about several applications, including social and biological use cases, and how subgraphs might be very useful use when studying networks that evolve over time. Finally, I will briefly mention ongoing work of our research group in this area.