Closed and Maximal Subgraph Mining in Internally and Externally Weighted Graph Databases

We formalize a problem of closed and maximal pattern discovery in internally and externally weighted graph databases. We introduce two weights, internal weights and external weights, which represent utility and significance of each edge in the graph, and importance and reliability of the graph itself, respectively. In our formulation, graphs with the two sets of weights describe the target data to be mined precisely. As an extension of traditional sub graph miners, we develop a mining algorithm called "wgMiner" for discovering all closed and maximal patterns in the weighted graph databases. With wgMiner, experiments demonstrate the effectiveness of our formulation in pattern mining from communication networks.