Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled Graphs
A labeled graph is a special structure with node identification capability, which is often used in information networks, biological networks, and other fields. The subgraph query is widely used as an important means of graph data analysis. As the size of the labeled graph increases and changes dynam...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-02-01
|
| Series: | Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2078-2489/10/2/61 |
| _version_ | 1818503616812548096 |
|---|---|
| author | Xiaohuan Shan Chunjie Jia Linlin Ding Xingyan Ding Baoyan Song |
| author_facet | Xiaohuan Shan Chunjie Jia Linlin Ding Xingyan Ding Baoyan Song |
| author_sort | Xiaohuan Shan |
| collection | DOAJ |
| description | A labeled graph is a special structure with node identification capability, which is often used in information networks, biological networks, and other fields. The subgraph query is widely used as an important means of graph data analysis. As the size of the labeled graph increases and changes dynamically, users tend to focus on the high-match results that are of interest to them, and they want to take advantage of the relationship and number of results to get the results of the query quickly. For this reason, we consider the individual needs of users and propose a dynamic Top-K interesting subgraph query. This method establishes a novel graph topology feature index (GTSF index) including a node topology feature index (NTF index) and an edge feature index (EF index), which can effectively prune and filter the invalid nodes and edges that do not meet the restricted condition. The multi-factor candidate set filtering strategy is proposed based on the GTSF index, which can be further pruned to obtain fewer candidate sets. Then, we propose a dynamic Top-K interesting subgraph query method based on the idea of the sliding window to realize the dynamic modification of the matching results of the subgraph in the dynamic evolution of the label graph, to ensure real-time and accurate results of the query. In addition, considering the factors, such as frequent Input/Output (I/O) and network communication overheads, the optimization mechanism of the graph changes and an incremental maintenance strategy for the index are proposed to reduce the huge cost of redundant operation and global updates. The experimental results show that the proposed method can effectively deal with a dynamic Top-K interesting subgraph query on a large-scale labeled graph, at the same time the optimization mechanism of graph changes and the incremental maintenance strategy of the index can effectively reduce the maintenance overheads. |
| first_indexed | 2024-12-10T21:26:19Z |
| format | Article |
| id | doaj.art-0ecfd4772f104f94b097ba979a388804 |
| institution | Directory Open Access Journal |
| issn | 2078-2489 |
| language | English |
| last_indexed | 2024-12-10T21:26:19Z |
| publishDate | 2019-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Information |
| spelling | doaj.art-0ecfd4772f104f94b097ba979a3888042022-12-22T01:32:58ZengMDPI AGInformation2078-24892019-02-011026110.3390/info10020061info10020061Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled GraphsXiaohuan Shan0Chunjie Jia1Linlin Ding2Xingyan Ding3Baoyan Song4School of Information, Liaoning University, Shenyang, 110036, ChinaSchool of Information, Liaoning University, Shenyang, 110036, ChinaSchool of Information, Liaoning University, Shenyang, 110036, ChinaSchool of Information, Liaoning University, Shenyang, 110036, ChinaSchool of Information, Liaoning University, Shenyang, 110036, ChinaA labeled graph is a special structure with node identification capability, which is often used in information networks, biological networks, and other fields. The subgraph query is widely used as an important means of graph data analysis. As the size of the labeled graph increases and changes dynamically, users tend to focus on the high-match results that are of interest to them, and they want to take advantage of the relationship and number of results to get the results of the query quickly. For this reason, we consider the individual needs of users and propose a dynamic Top-K interesting subgraph query. This method establishes a novel graph topology feature index (GTSF index) including a node topology feature index (NTF index) and an edge feature index (EF index), which can effectively prune and filter the invalid nodes and edges that do not meet the restricted condition. The multi-factor candidate set filtering strategy is proposed based on the GTSF index, which can be further pruned to obtain fewer candidate sets. Then, we propose a dynamic Top-K interesting subgraph query method based on the idea of the sliding window to realize the dynamic modification of the matching results of the subgraph in the dynamic evolution of the label graph, to ensure real-time and accurate results of the query. In addition, considering the factors, such as frequent Input/Output (I/O) and network communication overheads, the optimization mechanism of the graph changes and an incremental maintenance strategy for the index are proposed to reduce the huge cost of redundant operation and global updates. The experimental results show that the proposed method can effectively deal with a dynamic Top-K interesting subgraph query on a large-scale labeled graph, at the same time the optimization mechanism of graph changes and the incremental maintenance strategy of the index can effectively reduce the maintenance overheads.https://www.mdpi.com/2078-2489/10/2/61labeled graphdynamic Top-K queryinteresting subgraphsliding window |
| spellingShingle | Xiaohuan Shan Chunjie Jia Linlin Ding Xingyan Ding Baoyan Song Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled Graphs Information labeled graph dynamic Top-K query interesting subgraph sliding window |
| title | Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled Graphs |
| title_full | Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled Graphs |
| title_fullStr | Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled Graphs |
| title_full_unstemmed | Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled Graphs |
| title_short | Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled Graphs |
| title_sort | dynamic top k interesting subgraph query on large scale labeled graphs |
| topic | labeled graph dynamic Top-K query interesting subgraph sliding window |
| url | https://www.mdpi.com/2078-2489/10/2/61 |
| work_keys_str_mv | AT xiaohuanshan dynamictopkinterestingsubgraphqueryonlargescalelabeledgraphs AT chunjiejia dynamictopkinterestingsubgraphqueryonlargescalelabeledgraphs AT linlinding dynamictopkinterestingsubgraphqueryonlargescalelabeledgraphs AT xingyanding dynamictopkinterestingsubgraphqueryonlargescalelabeledgraphs AT baoyansong dynamictopkinterestingsubgraphqueryonlargescalelabeledgraphs |