Speaker:

Pedro Ribeiro

Date:

Thu May 11, 2017 @ 02:00pm EDT

Date:

Thu May 11, 2017

Time:

02:00pm EDT

Location:

GHC 8102

Title:

Subgraphs: the building blocks of complex networks

---

Talk Info:

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.