Predstavitev programske skupine:
Analiza podatkov in
kombinatorična optimizacija

Raziskovalni program

Z razvrščanjem v skupine, analizo omrežij in algoritmi teorije grafov se ukvarjamo že več let. Zadnja leta smo začeli posebno pozornost posvečati velikim podatkovjem (na desettisoče enot) in hitrim (subkvadratnim) algoritmom za njih analizo. Za nazoren in razumljiv prikaz dobljenih rezultatov nameravamo razviti ustrezne oblike prikaza v trirazsežnem prostoru oprte na jezik za opis prostorskih konstrukcij VRML (Virtual Reality Modeling Language).

Za nekatere probleme ne obstajajo učinkoviti točni algoritmi. Zato bomo za posamezne izmed njih poskusili razviti zelo hitre približne algoritme, ki temeljijo na hevristikah. Taki problemi so na primer: bločno modeliranje v obsežnih omrežjih, nivojski prikaz acikličnih omrežij in problem barvanja točk grafa.

Pri analizi velikih podatkovij in omrežij je pogosto ugodno, če jih znamo razbiti na več manjših, lažje obvladljivih kosov. Posebno pozornost nameravamo posvetiti problemom razčlembe omrežij na podomrežja iz izbranih družin (poti, drevesa, ravninski grafi, kubični grafi, ...). Pričakujemo, da nam bo na tej osnovi uspeli zgraditi tudi posamezne učinkovite algoritme.

Pri operacionalizaciji pristopov k analizi podatkovij in omrežij imajo velik pomen mere različnosti. Nadaljevati nameravamo naše raziskave prijemov, kako z ustreznimi transformacijami izboljšati kakovost posameznih mer različnosti.

Programska skupina

Projekti

MZT

• J2-6191 : Različnosti, razvrstitve in analiza omrežij. Vladimir Batagelj, 1994 - 1997/06
• J1-8697 : Aproksimacijski algoritmi na skupini delovnih postaj. Janez Žerovnik,
• J2-7516 : Kombinatorika in algoritmi z aplikacijami. (0.831 FTE) Janez Žerovnik, - 1998/12
• J1-8532 : Optimizacija in mere različnosti v analizi podatkov. (1.726 FTE) Vladimir Batagelj, 1997/07 - 2000/06
• J2-1015 : Hevristike - teorija in aplikacije. Janez Žerovnik, 1999 - 2001

Mednarodno sodelovanje

• ALIS link no. 27: John Shawe-Taylor, Royal Holloway, University of London, ANGLIJA. Probabilistic Algorithms and Combinatorial Optimisation, Janez Žerovnik, 1995-98.
• Program PROTEUS: Ecole Normale Superieuere de Lyon, Francija. Inherent parallelism of some graph theoretical algorithms, Janez Žerovnik, 1995-96.
• Program PROTEUS, project 980/20, Ecole Normale Superieuere de Lyon, Francija. GOAL Frequences - Graphes et Optimisations pour l'Allocation de Frequences, Janez Žerovnik, 1998-99, 2000.
• Univ. di Trento, Italija. Machine learning methods for parameter tuning in randomized heuristics, Janez Žerovnik, 1999-2002.
• Esprit project 28953: ISO-3D - Multi Modal Interpretation of Symbolic Objects with 3D Representations. 1998/11 - 2000/10.
• Predlog (D. White): Group Dynamics, Cultural Capital and Social Networks: Internationally Collaborative Longitudinal Studies.
• Pobuda Mapping The Global Web.
• Janez Žerovnik, daljši obiski:
  • gost (EC - PECO programme, contract no. ERB-CIPA-CT-92-2188) na Royal Holloway College, University of London (18.4.1993 - 1.10.1993)
  • gost ("bourse de haut niveau", Francija) v Laboratoire d'Informatique du Parallelisme, Ecole Normale Superieuere de Lyon, (1.4.1997 - 17.9.1997)

Dosežki

• V sistemih za podporo odločanja se vsebolj poskuša uporabljati podatke zbrane v, pogosto zelo obsežnih in raznolikih, podatkovnih bazah. Eden od ciljev projekta je razvoj učinkovitih postopkov za povzemanje vsebine baz v odgovore na zastavljena vprašanja in nazoren prikaz odgovorov. Na tej problematiki sodelujemo v evropskem projektu ISO-3D.
• Analiza (velikih) omrežij, kjer sodelujemo s:
  • skupino za analizo socialnih omrežij prof. A. Ferligoj na FDV, Ljubljana: mentorstvo A. Mrvarja, sodelovanje na problemih;
  • prof. D. Whiteom (Irvine, USA) na razvoju postopkov analize genealogij, temelječe na prestavitvi p-graf;
  • prof. P. Doreianom (Pittsburgh, USA) na razvoju postopkov za posplošeno bločno modeliranje.
• Pajek; delavnica na Sunbelt'98.
• Nagrade na tekmovanjih iz risanja grafov ( GD95, GD96, GD97, GD98 ) ob vsakoletni konferenci Graph Drawing.
• V. Batagelj in A. Ferligoj, 1998, poletni podiplomski tečaj iz analize omrežij na Srednje-evropski univerzi v Budimpešti