{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T06:57:44Z","timestamp":1760597864948,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,2,14]],"date-time":"2019-02-14T00:00:00Z","timestamp":1550102400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No. 61472169, 61502215"],"award-info":[{"award-number":["No. 61472169, 61502215"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science Research Normal Fund of Liaoning Province Education Department","award":["No. L2015193"],"award-info":[{"award-number":["No. L2015193"]}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["No.2016YFC0801406"],"award-info":[{"award-number":["No.2016YFC0801406"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Scientific Research Fund of Liaoning province Education Department","award":["No. LYB201617"],"award-info":[{"award-number":["No. LYB201617"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/info10020061","type":"journal-article","created":{"date-parts":[[2019,2,14]],"date-time":"2019-02-14T11:54:13Z","timestamp":1550145253000},"page":"61","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Dynamic Top-K Interesting Subgraph Query on Large-Scale Labeled Graphs"],"prefix":"10.3390","volume":"10","author":[{"given":"Xiaohuan","family":"Shan","sequence":"first","affiliation":[{"name":"School of Information, Liaoning University, Shenyang, 110036, China"}]},{"given":"Chunjie","family":"Jia","sequence":"additional","affiliation":[{"name":"School of Information, Liaoning University, Shenyang, 110036, China"}]},{"given":"Linlin","family":"Ding","sequence":"additional","affiliation":[{"name":"School of Information, Liaoning University, Shenyang, 110036, China"}]},{"given":"Xingyan","family":"Ding","sequence":"additional","affiliation":[{"name":"School of Information, Liaoning University, Shenyang, 110036, China"}]},{"given":"Baoyan","family":"Song","sequence":"additional","affiliation":[{"name":"School of Information, Liaoning University, Shenyang, 110036, China"}]}],"member":"1968","published-online":{"date-parts":[[2019,2,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1186\/s12859-017-1525-z","article-title":"Comparison of tissue\/disease specific integrated networks using directed graphlet signatures","volume":"18","author":"Sonmez","year":"2017","journal-title":"Bmc Bioinf."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1109\/TNNLS.2016.2515080","article-title":"Graph Theory-Based Pinning Synchronization of Stochastic Complex Dynamical Networks","volume":"28","author":"Li","year":"2017","journal-title":"IEEE Trans. Neural Netw. Learn Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s11704-015-4515-1","article-title":"Big Graph Search: Challenges and Techniques","volume":"10","author":"Ma","year":"2016","journal-title":"Front. Comput. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1109\/TBDATA.2016.2625307","article-title":"Exploiting Efficient Densest Subgraph Discovering Methods for Big Data","volume":"3","author":"Wu","year":"2017","journal-title":"IEEE Trans. Big Data."},{"key":"ref_5","first-page":"52","article-title":"An algorithm for subgraph matching based on adaptive structural summary of labeled directed graph data","volume":"40","author":"Zhang","year":"2017","journal-title":"Chin. J. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"133","DOI":"10.14778\/2535568.2448946","article-title":"An in-depth comparison of subgraph isomorphism algorithms in graph databases","volume":"6","author":"Lee","year":"2012","journal-title":"Proc. VLDB Endowment"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1238","DOI":"10.14778\/2809974.2809985","article-title":"Taming Subgraph Isomorphism for RDF Query Processing","volume":"8","author":"Kim","year":"2015","journal-title":"Proc. VLDB Endowment"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"364","DOI":"10.14778\/1453856.1453899","article-title":"Taming verification hardness: An efficient algorithm for testing subgraph isomorphism","volume":"1","author":"Shang","year":"2008","journal-title":"Proc. VLDB Endowment"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Yan, X., He, B., Zhu, F., and Han, J. (2010, January 1\u20136). Top-K aggregation queries over large networks. Proceedings of the IEEE International Conference on Data Engineering, California, CA, USA.","DOI":"10.1109\/ICDE.2010.5447863"},{"key":"ref_10","unstructured":"Gupta, M., Gao, J., Yan, X., and Cam, H. (April, January 31). Top-K interesting subgraph discovery in information networks. Proceedings of the International Conference on Data Engineering, Chicago, IL, USA."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.14778\/2536258.2536263","article-title":"Diversified top-k graph pattern matching","volume":"6","author":"Fan","year":"2013","journal-title":"Proc. VLDB Endowment"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1007\/s11704-016-5485-7","article-title":"iGraph: An incremental data processing system for dynamic graph","volume":"10","author":"Ju","year":"2016","journal-title":"Front. Comput. Sci."},{"key":"ref_13","first-page":"289","article-title":"Sliding Window-Based Fault Detection From High-Dimensional Data Streams","volume":"47","author":"Zhang","year":"2017","journal-title":"IEEE Trans. Syst. Man Cybern. Syst."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.14778\/2904483.2904490","article-title":"Skype: Top-k spatial-keyword publish\/subscribe over sliding window","volume":"9","author":"Wang","year":"2016","journal-title":"Proc. VLDB Endowment"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","article-title":"An Algorithm for Subgraph Isomorphism","volume":"23","author":"Ullmann","year":"1976","journal-title":"J. ACM"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub)graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"788","DOI":"10.14778\/2311906.2311907","article-title":"Efficient subgraph matching on billion node graphs","volume":"5","author":"Sun","year":"2012","journal-title":"Proc. VLDB Endowment"},{"key":"ref_18","unstructured":"Han, W.S., Lee, J., and Lee, J.H. (2013, January 22\u201327). TurboISO: Towards ultrafast and robust subgraph isomorphism search in large graph databases. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, NY, USA."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"617","DOI":"10.14778\/2735479.2735493","article-title":"Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs","volume":"8","author":"Ren","year":"2015","journal-title":"Proc. VLDB Endowment"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., and Zhang, W. (July, January 26). Efficient Subgraph Matching by Postponing Cartesian Products. Proceedings of the 2016 International Conference on Management of Data, San Francisco, CA, USA.","DOI":"10.1145\/2882903.2915236"},{"key":"ref_21","unstructured":"Holder, L.B., Cook, D.J., and Djoko, S. (August, January 31). Substructure discovery in the SUBDUE system. Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, Seattle, WA, USA."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"807","DOI":"10.14778\/3402707.3402720","article-title":"Mining Top-K large structural patterns in a massive network","volume":"4","author":"Zhu","year":"2011","journal-title":"Proc. VLDB Endowment"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"340","DOI":"10.14778\/1920841.1920887","article-title":"On graph query optimization in large networks","volume":"3","author":"Zhao","year":"2010","journal-title":"Proc. VLDB Endowment"},{"key":"ref_24","unstructured":"He, H., and Singh, A.K. (2010, January 6\u201311). Query language and access methods for graph databases. Proceedings of the Acm Sigmod International Conference on Management of Data, Indianapolis, IN, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1007\/s10618-010-0185-7","article-title":"Mining top-k frequent itemsets through progressive sampling","volume":"21","author":"Pietracaprina","year":"2010","journal-title":"Data Min. Knowl. Discovery"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Wu, C.W., Shie, B.E., Tseng, V.S., and Yu, P.S. (2012, January 12\u201316). Mining top-k high utility itemsets. Proceedings of the 18th ACM International Conference on Knowledge Discovery and Data Mining, Beijing, China.","DOI":"10.1145\/2339530.2339546"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Yang, Z., Fu, W.C., and Liu, R. (July, January 26). Diversified Top-k Subgraph Querying in a Large Graph. Proceedings of the 2016 International Conference on Management of Data, San Francisco, CA, USA.","DOI":"10.1145\/2882903.2915216"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1007\/s11704-015-4196-9","article-title":"Top-k probabilistic prevalent co-location mining in spatially uncertain data sets","volume":"10","author":"Wang","year":"2016","journal-title":"Front. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1007\/s11704-014-3230-7","article-title":"Discovering top-k patterns with differential privacy-an accurate approach","volume":"8","author":"Zhang","year":"2014","journal-title":"Front. Comput. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/s11704-015-5222-7","article-title":"Optimizing top-k retrieval: submodularity analysis and search strategies","volume":"10","author":"Sha","year":"2016","journal-title":"Front. Comput. Sci."},{"key":"ref_31","first-page":"663","article-title":"Survey on Dynamic Graph Pattern Matching Technologies","volume":"29","author":"Xu","year":"2018","journal-title":"J. Softw."},{"key":"ref_32","first-page":"2381","article-title":"An Incremental Processing Algorithm about Disjoint Query Based on Sliding Window over Data Stream","volume":"40","author":"Wang","year":"2017","journal-title":"Chin. J. Comput."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1360\/jos170740","article-title":"Sliding Window Based Method for Processing Continuous J-A Queries on Data Streams","volume":"17","author":"Wang","year":"2006","journal-title":"J. Softw."},{"key":"ref_34","unstructured":"Khan, A., Wu, Y., Aggarwal, C.C., and Yan, X. (2013, January 26\u201330). NeMa: Fast graph search with label similarity. Proceedings of the International Conference on Very Large Data Bases, Riva del Garda, Italy."},{"key":"ref_35","unstructured":"Sun, Y.Z., Yu, Y.T., and Han, J.W. (July, January 29). Ranking-Based clustering of heterogeneous information networks with star network schema. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., and Faloutsos, C. (2004, January 22\u201324). R-MAT: A recursive model for graph mining. Proceedings of the Fourth SIAM International Conference on Data Mining, Lake Buena Vista, FL, USA.","DOI":"10.1137\/1.9781611972740.43"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/10\/2\/61\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:32:13Z","timestamp":1760185933000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/10\/2\/61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,14]]},"references-count":36,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,2]]}},"alternative-id":["info10020061"],"URL":"https:\/\/doi.org\/10.3390\/info10020061","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2019,2,14]]}}}