Tegenwoordig verschijnt data meer en in meer in de vorm van grafen.
Inzicht krijgen in de structuur van een graaf kan een belangrijke rol spelen voor data gebruikers bij het nemen van beslissingen. Een belangrijke onderzoeksvraag is: Hoe kunnen we op een efficiënte manier een informatief (verrassend) deel van de gehele graaf tonen aan de data gebruiker?. We zijn typisch geïnteresseerd zijn in het tonen van een subgraaf van de gehele graaf. Prominente voorbeelden van zulke patronen zijn sterk verbonden gemeenschappen van
individuen in een sociaal netwerk, of het frequent voorkomen van een molecule
in een biologisch proteïne interactie network.
Dit onderzoek stelt een aantal algoritmes voor om connecterende bomen en connecterende cycli te vinden tussen een aantal opgegeven vertices in een graaf. Niet alle connecterende subgrafen zijn even interessant voor de gebruiker. De interessantheid is fundamenteel subjectief: wat voor de ene gebruiker interessant is, is niet noodzakelijk interessant voor iemand anders. Onze algoritmes houden rekening met dit aspect.
We differentiëren tussen verschillende gebruikers op basis van hun voorkennis over de structuur van de graaf. Het tweede deel van het onderzoek is gewijd aan het probabilistisch modelleren van een graaf, gegeven een bepaalde voorkennis op de structuur van de graaf. | |