Monday, May 14 2012, at 16h30 in Celestijnenlaan 200A (auditorium 00.225)
Mining Frequent Trees in Large Networks
by Ashraf Masood Kibriya (PhD student DTAI)
Mining frequent patterns in a single network (graph) poses a number of challenges. Matching one pattern to a network (up to subgraph isomorphism) is already NP-complete. Matching algorithms that exist, become untractable, even for reasonably small patterns, on networks which are large or have a high average degree. Based on recent advances in parameterized complexity theory, we propose a novel miner for rooted trees in networks. The miner, for a fixed parameter k (maximal pattern size), can mine all rooted trees with delay linear in the size of the network and only mildly exponential in the fixed parameter k (2k). This allows us to mine tractably, rooted trees, in large networks such as the WWW or social networks. We establish the practical applicability of our miner, by presenting an experimental evaluation on both synthetic and real-world data.