Graph Mining: het efficient en exhaustief genereren van grafen

Abstract

Abstract

Vele zaken uit onze dagelijkse wereld kunnen voorgesteld worden met behulp van grafen. Denk hierbij bijvoorbeeld aan moleculen, sociale netwerken, 3D-modellen, processen, . . . Soms kan het interessant zijn om in een verzameling van zulke structuren op zoek te gaan naar terugkerende patronen, zodat we bijvoorbeeld objecten makkelijker kunnen classi'ceren, gemeenschappelijke eigenschappen ontdekken, . . . Een manier om dit aan te pakken is om de objecten onder de vorm van grafen in een databank op te slaan en op zoek te gaan naar patronen die frequent voorkomen. Deze procedure noemen we graph mining.

Bij graph mining komen problemen kijken bij het genereren van mogelijke kandidaatgrafen: er kunnen dubbels gegenereerd worden. Hiertoe onderzoeken we graafisomorfisme en bestuderen we enumeratieprocedures die dit vermijden. Verder bestuderen we de notie van graafgrammatica's om klassen van grafen te beschrijven die we willen genereren (bvb. voor kandidaten).