ELFT HÍRADÓ

[Bazsó Fülöp <bazso.fulop AT wigner.mta.hu>]

Tisztelt Kollegák,

március 20.-án 11 órakkor a 3-as épület tanácstermében Hannu Reittu 
előadást tart. Minden érdeklődőt szívesen látunk.

Üdvözlettel,

Bazsó Fülöp

Hannu Reittu (VTT Technical Research Centre of Finland):

On an approach to graph compression motivated by Szemerédi's regularity 
lemma and Rissanen's minimum description length principle

Abstract: Szemerédi's regularity lemma is a key result in graph theory. It 
suggest, roughly speaking, that any large enough graph can be 'compressed' 
by partitioning its vertices into a bounded number of sets in such a way 
that edges between set pairs are distributed in a very uniform fashion. 
This could point an interesting direction in study of real life networks. 
Namely, searching for such a compressions of networks. A problem here is 
what is the exact target? We discuss one approach that is based on 
Rissanen's  minimum description length (MDL) principle. It suggests that 
in such a fitting problem one should consider a trade-off between accuracy 
and complexity of modelling in such a way that the description length is 
minimized.  This could result in a well-founded approach in defining graph 
compression and replacing heuristics like the Akaike information criterion 
in such modelling tasks.


------------------------------------------------------------------
|  Bazso, Fulop                                                  |
|  senior research fellow                                        |
|  Department of Theory                                          |
|  Institute for Particle and Nuclear Physics                    |
|  Wigner Research Centre for Physics                            |
|  Hungarian Academy of Sciences                                 |
|  P.O. Box 49, Budapest, H-1525, Hungary                        |
|  Tel: 36 1 3922222 extension: 1238                             |
|  Fax: 36 1 3922742                                             |
|       36 1 3959151                                             |
|  E-mail: 
bazso.fulop AT wigner.mta.hu
                             |
------------------------------------------------------------------