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

[statphys]

* *

*

JOINT ICTP/SISSA STATISTICAL PHYSICS SEMINAR
Tuesday, 28 April 2009   -    12:30 hrs
Lecture Room D
SISSA Main Building
Serena BRADDE
(S.I.S.S.A. - Trieste)
"Statistical Mechanics of sub-graph
identification problems"
Abstract
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.

*