Dear All, 

Next Monday, November 7th, we will have with us Pedro Ribeiro, from
CRACS/INESCTEC and DCC/FC University of Porto, and also Miguel Araújo,
PhD student (and finalist) in the CMU|Portugal Program. They will give
the following two seminars in the context of the course in Complex
Networks. These seminars are open to the public and you are all invited.


= Subgraphs: the fundamental structural units of complex networks =

By Pedro Ribeiro (http://www.dcc.fc.up.pt/~pribeiro/)

Date: 2016-Nov-07   Time: 14:00
Room: Anfiteatro do Complexo Interdisciplinar (Alameda)

Abstract: Complex networks are ubiquitous in real-world systems. One
way to understand their design principles is to look at how they are
organized at the subgraph level, discovering small characteristic building
blocks. In this talk I will describe how subgraphs can provide a powerful
and very flexible framework for charactering and comparing networks,
focusing on two concepts geared around this idea, namely network motifs
and graphlets. At the core of these methodologies lies the ability to
search and count subgraphs. 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. I will also
briefly discuss sampling and parallel versions of g-trie based methods
and I will show some empirical results on a set of complex networks from
various domains. Finally, I will give examples of applications and I
will talk about ongoing work of our research group in this area.


= Communities and Anomalies in Large Edge-Labeled Graphs =

By Miguel Araújo (http://www.cs.cmu.edu/~maraujo/)

Date: 2016-Nov-07   Time: 15:10
Room: Anfiteatro do Complexo Interdisciplinar (Alameda)

Abstract: Anomalies and community identification in real-world graphs
is an important task in widespread domains, from recommender systems
to bank fraud detection.  While ongoing research is supplying tools
for the analysis of simple unlabeled data, finding patterns and
anomalies in large labeled datasets, such as time evolving networks,
is still a challenge. What do real communities in big datasets look
like? How is their structure affected by their size? How do they evolve,
grow and disappear? We start by exploring the shape and structure of
big communities in real networks and we will see how ”hyperbolic
communities” naturally emerge.  I will then describe a fast algorithm
for finding these structures in large datasets, before tackling the
problem of finding real communities on time-evolving networks.  I will
explain how, in general, Minimum Description Length approaches can be
used to find these structures and how the inclusion of side information
can lead to increased precision in tasks such as forecasting community
membership. I will show how we can predict which members are more
likely to join or remain in a community and how one can find common
community profiles. Finally, I am going to briefly describe on-going
work on how non-categorical labels, such as geographical coordinates,
can be leveraged for this task.


Best regards,

Alexandre Francisco
Francisco Santos