EFFICIENT LARGE SCALE FREQUENT SUBGRAPH MINING USING MAPREDUCE

Abstract

Graph based data representations are getting popular in areas like bioinformatics, social networks, web data mining, etc. Over the years many algorithms have been created for analysis on graph data. One such challenging task in this field is Frequent Subgraph Mining (FSM). Extracting frequent subgraphs from a huge set of graphs is a fundamental task in numerous information mining applications. There are existing frequent subgraph mining algorithms for unweighted graphs but they do not take into consideration the strength of relationships within the graph. In weighted graphs, some edges/vertices have more importance than others. In areas such as mobile communication networks, social networks, etc. weighted graphs are more useful. More relevant and specific subgraphs are generated through weighted frequent subgraph mining. There has been only some little work done in the field of frequent subgraph mining on weighted graphs. Also most of the current techniques are memory-based and are not scalable. This work uses an existing distributed approach for Frequent Subgraph Mining using iterative MapReduce based framework and applies different weighing schemes over the current approach. This work uses two different weighing schemes, Average Total Weighing (ATW) scheme and Affinity Weighing (AW) scheme, and compares both approaches.