Tomorrow's seminar

[CM]

JOINT ICTP/SISSA STATISTICAL PHYSICS SEMINAR




Tuesday, 28 April -    12:30 hrs.


Lecture Room 'D' - SISSA Main Building



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



"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.