Cohesive pattern mining in graphs

Datum: 3 september 2015

Locatie: UAntwerpen - Campus Middelheim - Lokaal G0.10 - Middelheimlaan 1 - 2020 Antwerpen

Tijdstip: 15 uur

Organisatie / co-organisatie: Departement Wiskunde-Informatica

Promovendus: Tayena Hendrickx

Promotor: Bart Goethals

Korte beschrijving: Doctoraatsverdediging Tayena Hendrickx - Departement Wiskunde-Informatica, Faculteit Wetenschappen



Abstract

Technologische ontwikkelingen van de laatste decennia maken het genereren en opslaan van grote hoeveelheden data steeds goedkoper en makkelijker. Onderzoekscentra, overheden, bedrijven, en zelfs individuen zijn in het bezit van gigabytes, terabytes, petabytes of zelfs exabytes aan gegevens die opgeslagen zitten in databanken. De uitdaging is om deze data te analyseren om zo nieuwe en/of verborgen informatie te vergaren, dat vervolgens gebruikt kan worden voor allerhande doeleinden. Het systematisch analyseren van dergelijke grote hoeveelheden data, en het omzetten in bruikbare kennis, is echter een niet-triviale taak.

Het proces dat instaat om ruwe gegevens om te zetten naar bruikbare informatie, om de gebruiker aldus meer inzicht te geven in de data, is het zogenaamde Knowledge Discovery in Databases (KDD) proces. Eén van de stappen in dit proces is data mining. Data mining is het onderzoeksdomein dat zich bezig houdt met het ontwikkelen van processen om systematisch en geautomatiseerd grote hoeveelheden data te doorzoeken, met als doel, voorheen onbekende patronen en verbanden te onttrekken.

In dit onderzoek concentreren wij ons op het zoeken naar interessante patronen in graaf datasets die bestaan uit één enkelvoudige graaf of een verzameling van meerdere grafen. Een graaf is een geordend paar G (V, E), samengesteld uit een eindige verzameling van knopen V(G) en een eindige verzameling van bogen E(G). In dit proefschrift beschouwen we ongerichte, gelabelde grafen, i.e. grafen waarbij elke knoop voorzien is van één enkel label en waarbij de bogen geen oriëntatie hebben. Daarenboven moet elke graaf geconnecteerd zijn, i.e. dat elke knoop bereikt kan worden vanuit elke andere knoop, via een pad bestaande uit bogen van de graaf.

Traditionele methoden voor het vinden van patronen in graaf data focussen zich op zogenaamde frequente deelgrafen. Dit zijn structuren in de graaf waarbij de knopen, met welbepaalde labels, vaak met elkaar verbonden zijn op exact dezelfde manier. Hoewel algoritmen, voor het detecteren van frequente deelgrafen, patronen vinden die in heel wat applicaties bruikbaar zijn, missen ze toch andere interessante patronen.

Bovendien hebben de deelgraaf algoritmen ook af te rekenen met het deelgraaf-isomorfisme probleem, wat de complexiteit van de algoritmen niet ten goede komt. Om deze redenen stappen wij, in dit onderzoek, af van de vaste structuur en focussen wij ons op het vinden van interessante itemsets in grafen. Een itemset bestaat hierbij uit een verzameling van items, i.e. knooppunt labels, die vaak dicht bij elkaar verschijnen in de graaf.

Deze samenhangende patronen geven echter geen informatie over de mogelijke verbanden en interacties tussen de verschillende knopen in de graaf. Om die reden introduceren we in dit onderzoek ook een methode voor het zoeken van associatie regels, gebaseerd op de gevonden samenhangende patronen.