Nearly Exact Mining of Frequent Trees in Large Networks
Abstract
Mining frequent patterns in a single network (graph) poses a number of challenges. Already only to match one path pattern to a network (upto subgraph isomorphism) is NP-complete. Matching algorithms that exist, become intractable 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 (2^ k ). 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.
Cite
Text
Kibriya and Ramon. "Nearly Exact Mining of Frequent Trees in Large Networks." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012. doi:10.1007/978-3-642-33460-3_33Markdown
[Kibriya and Ramon. "Nearly Exact Mining of Frequent Trees in Large Networks." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012.](https://mlanthology.org/ecmlpkdd/2012/kibriya2012ecmlpkdd-nearly/) doi:10.1007/978-3-642-33460-3_33BibTeX
@inproceedings{kibriya2012ecmlpkdd-nearly,
title = {{Nearly Exact Mining of Frequent Trees in Large Networks}},
author = {Kibriya, Ashraf M. and Ramon, Jan},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2012},
pages = {426-441},
doi = {10.1007/978-3-642-33460-3_33},
url = {https://mlanthology.org/ecmlpkdd/2012/kibriya2012ecmlpkdd-nearly/}
}