Pedro Ribeiro (University of Porto)

Event Date: Thursday May 11, 2017
Event Time: 02:00pm
Location: GHC 8102
Speaker: Pedro Ribeiro [INFO]

Title: Subgraphs: The Building Blocks Of Complex Networks

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.