Zoeken naar veel voorkomende patronen in grote netwerken

De hoeveelheid data die dagelijks gegenereerd en opgeslagen wordt is de afgelopen decennia sterk toegenomen. Enkel al in 2013 werd er volgens sommige schattingen bijna 28TB aan data per seconde gegenereerd. Verder wordt er aangenomen dat dit tegen 2018 zal toenemen tot 50TB per seconde. Deze hoeveelheden maken het quasi onmogelijk om op manuele wijze bruikbare informatie uit deze data te extraheren. Data mining methodes spitsen zich toe op het automatisch onttrekken van informatie uit grote volumes aan data gebruik makende van technieken ontleend uit statistiek, artificiële intelligentie en databases. Eén van de fundamentele taken uit data mining is frequent pattern mining of het zoeken naar frequent voorkomende patronen in de data. In het verleden werd de data veelal beschreven door een set van onafhankelijke tupels. In de praktijk, daarentegen, is data vaak meer gestructureerd en meer complex, met verschillende onderlinge afhankelijkheden. Deze data representeren als onafhankelijke tupels leidt vaak tot een significant verlies aan belangrijke informatie. Om deze data in al zijn complexiteit te kunnen onderzoeken, werd er gezocht naar meer expressieve representaties, zoals grafen. Deze bezitten de juiste balans tussen expressiviteit en efficiëntie voor het minen van data met (onderlinge) afhankelijkheden. In deze thesis hebben we methodes ontwikkeld voor het toepassen van frequent pattern mining op grote enkelvoudige grafen (netwerken).

Het zoeken van patronen in een groot enkelvoudig netwerk is computationeel zeer uitdagend. De voornaamste uitdaging hierbij is het berekenen van de matching operator die gebruikt wordt bij het zoeken van overeenkomsten tussen een patroon en een netwerk. Voor de meeste matching operatoren (bv. subgrafe (homo/iso/homeo)-morfismes) is dit NP-volledig. Het subgrafe isomorfisme is een vaak gebruikte matching operator waarbij de knopen van het patroon 1-op-1 overeenstemmen met knopen in het netwerk (in tegenstelling tot de subgrafe homomorfisme matching operator, waarbij meerdere knopen van het patroon kunnen overeenstemmen met één knoop van het netwerk). Voor het subgrafe isomorfisme worden de klassieke matching algoritmes al snel onhandelbaar, zelfs in geval van kleine patronen op grote netwerken of netwerken met een hoge gemiddelde graad. Recent onderzoek naar theoretische complexiteitstheorie heeft echter geleid tot algoritmes die de subgrafe isomorfisme operator berekenbaar maakt wanneer bepaalde parameters van het probleem begrensd worden. Zulke theoretische resultaten worden vaak als onpraktisch beschouwd. In deze thesis, echter, tonen we aan dat dit niet het geval hoeft te zijn mits de nodige intelligente optimalisaties en nauwkeurige implementatie.

In deze thesis presenteren we eerst een nieuwe miner voor het minen van frequent rooted trees in grote netwerken, gebaseerd op de resultaten uit de geparametriseerde complexiteitstheorie. De miner zoekt patronen met een vertraging die slechts mild exponentieel is in de grootte van het patroon en lineair in de grootte van het netwerk. We demonstreren de toepasbaarheid van de miner met een grondige experimentele evaluatie op zowel synthetische data als reële data en we tonen aan dat we patronen kunnen minen met een grootte tot 17.

Daarna breiden we de resultaten uit tot een meer algemene klasse van grafen: deze van bounded treewidth (BTW) grafen. BTW is een belangrijke klasse van grafen die niet enkel in theorie maar ook in praktijk interessant is: vele grafen hebben namelijk een kleine treewidth. Eveneens gebaseerd op de resultaten uit de geparametriseerde complexiteitstheorie ontwikkelen we een miner voor het minen van frequente BTW grafe patronen in grote netwerken en tonen we aan dat we in de praktijk patronen met een kleine treewidth kunnen minen met een grootte tot 13. Daarnaast observeren we dat in de praktijk de meerderheid van de netwerkenlabels hebben. We buiten deze eigenschap uit om de complexiteitsgrens van onze matching operator verder te reduceren. We tonen aan dat, mits de aanwezigheid van labels, we onze resultaten verder kunnen verbeteren en patronen tot een grootte van 23 kunnen minen.