Mining weighted subgraphs in a single large graph

Weighted single large graphs are often used to simulate complex systems, and thus mining frequent subgraphs in a weighted large graph is an important issue that has attracted the attention of many researchers. Within the studies on the mining of frequent subgraphs, the Graph Mining (GraMi) algorithm is considered as a state-of-the-art algorithm. However, this algorithm can only be implemented on graph datasets which have node labels and edge labels, without weights, and this means that the importance of all objects in a large graph is the same. In this paper, we propose a frequent subgraph algorithm on a weighted large graph, called Weighted Graph Mining (WeGraMi), which is based on two effective strategies to mining weighted subgraphs. Firstly, we apply a new strategy to calculate the weight of all mined subgraphs, which is based on the weights of the nodes in that subgraph. Secondly, we apply a search space pruning strategy based on the existing weights; if a frequent subgraph cannot satisfy the given weighting threshold, that subgraph will be pruned, which can reduce the processing time and storage space needed. With both directed and undirected graph datasets, our experimental results show that the runtime as well as the memory requirements of our algorithm are significantly better than those of GraMi. (C) 2019 Elsevier Inc. All rights reserved.