Derivation of the Topology Structure from Massive Graph Data

摘要

We have extended Basket Analysis[1] to transaction data having graph structures in our previous work[2]. However, the extension is applicable onlyto the cases where all nodes contained in a graph are mutually distinct. Though this is suitable for the analysis of graph structure such as browsing patterns among URLs, it can not mine frequent patterns where multiple nodes of the same kind appear in a graph (e.g., chemical molecule structure). We propose an extension of Apriori algorithm to mine this type of graph structure. We evaluate the performance of our method in terms of the required computation time for various factors.