Category: List of Bases 2009 Throughout the year RESEARCH IN CONDENSED MATTER PHYSICS

Title:

JOINT ICTP/SISSA STATISTICAL PHYSICS SEMINAR: "Statistical Mechanics of sub-graph identification problems"

Start Time:

12:30

Location:

Lecture Room D - SISSA Main Building

Speaker(s):

Serena BRADDE ((S.I.S.S.A. - Trieste) )

Description:

Network analysis, inference and optimization represent methodological challenges which play a central role in large scale data analysis. Their practical relevance arises from the huge quantity of empirical data that is being made available in many fields of science, biology and economics in first place. In this talk we shall discuss some new statistical physics approaches to basic network optimization problems that come from sub-graph identification.
Firstly we show how to approach the so called sub-graph isomorphism problem, one of the most fundamental NP-hard problems in graph theory. We display three applications: maximum clique identification, graph alignment and network motif counting. Secondly we discuss how to generalize the cavity method to deal with the problem of searching for sub-network which are subject to topological constraints. The specific case of bounded depth Spanning trees is discussed in some detail, together with a novel application to high dimensional data clustering.