UTCS Colloquia - Pedro Ribeiro/University of Porto - "G-Tries: an efficient data-structure for subgraph counting", ACES 4.304

Contact Name: 
Jenna Whitney
Date: 
Jul 6, 2011 3:00pm - 4:00pm

Type of Talk: UTCS Colloquia

Speaker/Affiliation: Pedro Ri

beiro

Talk Audience: UTCS Faculty and Graduate Students

Date/Time

: Wednesday, July 6, 2011, 3:00 p.m.

Location: ACES 4.304

Host

: Keshav Pingali

Talk Title: "G-Tries: an efficient data-structure for
subgraph counting"

Talk Abstract:
Complex networks are ubiquitous i

n real-world systems. In order to understand their design principles, the

concept of network motifs emerged. These are recurrent overrepresented patt

erns of interconnections that can be seen as building blocks of networks. A

lgorithmically, 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 no

vel data structure, g-tries, designed to efficiently represent a collecti

on 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 introduce a sampling methodology capable of trading accuracy fo

r even better execution times.

Finally, I will show an extensive empi

rical evaluation of the developed algorithms on a set of diversified comple

x networks, showing that g-tries can outperform all previously existing co

mpetitor algorithms.

(Joint work with Fernando Silva and Luís Lopes)

Speaker Bio:
Pedro Ribeiro has just recently completed his PhD in Co

mputer Science at the University of Porto, after having completed an under

graduate Computer Science course with top marks and a post-graduation in Ar

tificial Intelligence. His current main research interests are efficient se

quential and parallel algorithms for complex networks analysis. He has a st

rong background on algorithms and data structures, having been an active p

articipant in programming contests in the past and contributing presently a

s the author of dozens of programming problems for national and internation

al contests. The work presented in the talk was published in e-Science''200

9, WABI''2010, ACM-SAC''2010, Cluster''2010 and will appear in JPDC''201

1.