InfMatch: Finding isomorphism subgraph on a big target graph based on the importance of vertex

Tinghuai Ma, Siyang Yu, Jie Cao, Yuan Tian and Mznah Al-Rodhann

Physica A: Statistical Mechanics and its Applications, 2019, vol. 527, issue C

Abstract: Subgraph matching is an important research topic in the area of graph theory and it has been applied in many areas in nowdays. Filtering and verification are two main processes of subgraph matching algorithms. However, there exists many invalid nodes in candidate matching set after initializing the candidate set for each query node, which may result in a quantity of redundant computation during the filtering period. Regarding the problem mentioned above, in this paper, we propose a subgraph matching algorithm based on node influence, denoted as InfMatch, to improve the performance of subgraph matching on a large target graph. Specially, we find the central node of query graph by calculating the global and local influence value of each query node, after which candidate matching nodes for each query node are found from the neighborhood region of the candidate nodes for the central node. Since the central node we choose connects tightly with other nodes, isolated nodes can′t be added into the candidate matching set for central node and thus a number of unqualified candidate vertices are pruned. To further prune the unqualified candidate nodes, we propose several filter strategies according to the characteristics of our method. What′s more, considering edge limitation, we improve the matching order selection strategy. Extensive experiments demonstrate that our method is more efficient.

Keywords: Influential node; Subgraph matching; Kshell (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437119307447
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:527:y:2019:i:c:s0378437119307447

DOI: 10.1016/j.physa.2019.121278

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().