LGM: Mining Frequent Subgraphs from Linear Graphs

Details LGM: Mining Frequent Subgraphs from Linear Graphs LGM: Mining Frequent Subgraphs from Linear Graphs

2011-02-22

arxiv.org/abs/1102.4480v3

Computer Science

Data Structures and Algorithms

This paper is going to be published in proceedings of 15th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAK

Scientific paper

A linear graph is a graph whose vertices are totally ordered. Biological and linguistic sequences with interactions among symbols are naturally represented as linear graphs. Examples include protein contact maps, RNA secondary structures and predicate-argument structures. Our algorithm, linear graph miner (LGM), leverages the vertex order for efficient enumeration of frequent subgraphs. Based on the reverse search principle, the pattern space is systematically traversed without expensive duplication checking. Disconnected subgraph patterns are particularly important in linear graphs due to their sequential nature. Unlike conventional graph mining algorithms detecting connected patterns only, LGM can detect disconnected patterns as well. The utility and efficiency of LGM are demonstrated in experiments on protein contact maps.

Affiliated with

Also associated with

No associations

Rating

LGM: Mining Frequent Subgraphs from Linear Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with LGM: Mining Frequent Subgraphs from Linear Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and LGM: Mining Frequent Subgraphs from Linear Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-558997