G-Tries: an efficient data-structure for counting subgraphs
CRACS & INESC-Porto LA / DCC-FCUP, Universidade do Porto –
Complex networks are ubiquitous in real-world systems. In order to understand their design principles, the concept of network motifs emerged. These are recurrent overrepresented patterns of interconnections that can be seen as building blocks of networks. Algorithmically, discovering these motifs is a hard problem, which limits their practical applicability.
I will give an overview of the state of the art in algorithms for finding these patterns. I will then present a novel data structure, g-tries, 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 also briefly introduce a sampling methodology capable of trading accuracy for even better execution times, and give some notes on the scalability of the methods, showing that they are suitable for a parallel computation.
Finally, I will show an extensive empirical evaluation of the developed algorithms on a set of diversified complex networks, showing that g-tries can outperform all previously existing competitor algorithms.
Date: 2011-Dec-02 Time: 14:30:00 Room: 336
For more information:
Workshop “Metabolism and mathematical models: Two for a tango” – 2nd Edition
Title: Workshop Metabolism and mathematical models: Two for a tango – 2nd Edition
Dates: October 25-26, 2022
Location: This workshop will be held in a virtual way
The topic of this workshop is metabolism in general, with a special focus, although not exclusive, on parasitology. Besides an exploration of the biological, biochemical and biomedical aspects, the workshop will also aim at presenting some of the mathematical modelling, algorithmic theory and software development that have become crucial to explore such aspects.
This workshop is being organised in the context of two projects, both with the Inria European Team Erable. One of the projects involves a partnership with the University of São Paulo (USP), in São Paulo, Brazil, more specifically the Institute of Mathematics and Statistics (IME) and the Institute of Biomedical Sciences – Inria Associated Team Capoeira – and the other involves the Inesc-ID/IST in Portugal, ETH in Zürich and EMBL in Heidelberg – H2020 Twinning Project Olissipo.
The workshop is open to all members of these two projects but also, importantly, to the community in general.
The program and more details are available here.