Graph-Based Node Finding in Big Complex Contextual Social Graphs
Graph pattern matching is to find the subgraphs matching the given pattern graphs. In complex contextual social networks, considering the constraints of social contexts like the social relationships, the social trust, and the social positions, users are interested in the top-K matches of a specific...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/7909826 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832550970171588608 |
|---|---|
| author | Keshou Wu Guanfeng Liu Junwen Lu |
| author_facet | Keshou Wu Guanfeng Liu Junwen Lu |
| author_sort | Keshou Wu |
| collection | DOAJ |
| description | Graph pattern matching is to find the subgraphs matching the given pattern graphs. In complex contextual social networks, considering the constraints of social contexts like the social relationships, the social trust, and the social positions, users are interested in the top-K matches of a specific node (denoted as the designated node) based on a pattern graph, rather than the entire set of graph matching. This inspires the conText-Aware Graph pattern-based top-K designated node matching (TAG-K) problem, which is NP-complete. Targeting this challenging problem, we propose a recurrent neural network- (RNN-) based Monte Carlo Tree Search algorithm (RN-MCTS), which automatically balances exploring new possible matches and extending existing matches. The RNN encodes the subgraph and maps it to a policy which is used to guide the MCTS. The experimental results demonstrate that our proposed algorithm outperforms the state-of-the-art methods in terms of both efficiency and effectiveness. |
| format | Article |
| id | doaj-art-4e554d954d1442309828de5208b4c2bd |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-4e554d954d1442309828de5208b4c2bd2025-02-03T06:05:16ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/79098267909826Graph-Based Node Finding in Big Complex Contextual Social GraphsKeshou Wu0Guanfeng Liu1Junwen Lu2Engineering Research Center for Software Testing and Evaluation of Fujian Province, Xiamen University of Technology, Xiamen, ChinaDepartment of Computing, Macquarie University, NSW 2109, AustraliaEngineering Research Center for Software Testing and Evaluation of Fujian Province, Xiamen University of Technology, Xiamen, ChinaGraph pattern matching is to find the subgraphs matching the given pattern graphs. In complex contextual social networks, considering the constraints of social contexts like the social relationships, the social trust, and the social positions, users are interested in the top-K matches of a specific node (denoted as the designated node) based on a pattern graph, rather than the entire set of graph matching. This inspires the conText-Aware Graph pattern-based top-K designated node matching (TAG-K) problem, which is NP-complete. Targeting this challenging problem, we propose a recurrent neural network- (RNN-) based Monte Carlo Tree Search algorithm (RN-MCTS), which automatically balances exploring new possible matches and extending existing matches. The RNN encodes the subgraph and maps it to a policy which is used to guide the MCTS. The experimental results demonstrate that our proposed algorithm outperforms the state-of-the-art methods in terms of both efficiency and effectiveness.http://dx.doi.org/10.1155/2020/7909826 |
| spellingShingle | Keshou Wu Guanfeng Liu Junwen Lu Graph-Based Node Finding in Big Complex Contextual Social Graphs Complexity |
| title | Graph-Based Node Finding in Big Complex Contextual Social Graphs |
| title_full | Graph-Based Node Finding in Big Complex Contextual Social Graphs |
| title_fullStr | Graph-Based Node Finding in Big Complex Contextual Social Graphs |
| title_full_unstemmed | Graph-Based Node Finding in Big Complex Contextual Social Graphs |
| title_short | Graph-Based Node Finding in Big Complex Contextual Social Graphs |
| title_sort | graph based node finding in big complex contextual social graphs |
| url | http://dx.doi.org/10.1155/2020/7909826 |
| work_keys_str_mv | AT keshouwu graphbasednodefindinginbigcomplexcontextualsocialgraphs AT guanfengliu graphbasednodefindinginbigcomplexcontextualsocialgraphs AT junwenlu graphbasednodefindinginbigcomplexcontextualsocialgraphs |