Mining Patterns in Networks using Homomorphism

Details Mining Patterns in Networks using Homomorphism Mining Patterns in Networks using Homomorphism

2011-10-14

arxiv.org/abs/1110.3225v1

Computer Science

Data Structures and Algorithms

Scientific paper

In recent years many algorithms have been developed for finding patterns in graphs and networks. A disadvantage of these algorithms is that they use subgraph isomorphism to determine the support of a graph pattern; subgraph isomorphism is a well-known NP complete problem. In this paper, we propose an alternative approach which mines tree patterns in networks by using subgraph homomorphism. The advantage of homomorphism is that it can be computed in polynomial time, which allows us to develop an algorithm that mines tree patterns in arbitrary graphs in incremental polynomial time. Homomorphism however entails two problems not found when using isomorphism: (1) two patterns of different size can be equivalent; (2) patterns of unbounded size can be frequent. In this paper we formalize these problems and study solutions that easily fit within our algorithm.

Affiliated with

Also associated with

No associations

Rating

Mining Patterns in Networks using Homomorphism 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 Mining Patterns in Networks using Homomorphism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mining Patterns in Networks using Homomorphism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-523361