{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T12:09:43Z","timestamp":1767182983946,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T00:00:00Z","timestamp":1556841600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004085","name":"Ministry of Education, Science and Technology","doi-asserted-by":"publisher","award":["2018R1A2A2A05023669"],"award-info":[{"award-number":["2018R1A2A2A05023669"]}],"id":[{"id":"10.13039\/501100004085","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Intell"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s10489-019-01479-4","type":"journal-article","created":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T02:20:39Z","timestamp":1556850039000},"page":"3731-3748","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["EM-FGS: Graph sparsification via faster semi-metric edges pruning"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8795-2762","authenticated-orcid":false,"given":"Dolgorsuren","family":"Batjargal","sequence":"first","affiliation":[]},{"given":"Kifayat Ullah","family":"Khan","sequence":"additional","affiliation":[]},{"given":"Young-Koo","family":"Lee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,5,3]]},"reference":[{"key":"1479_CR1","doi-asserted-by":"crossref","unstructured":"Ahn KJ, Guha S, McGregor A (2012) Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems. ACM, pp 5\u201314","DOI":"10.1145\/2213556.2213560"},{"issue":"9","key":"1479_CR2","doi-asserted-by":"publisher","first-page":"672","DOI":"10.14778\/2947618.2947623","volume":"9","author":"V Kalavri","year":"2016","unstructured":"Kalavri V, Simas T, Logothetis D (2016) The shortest path is not always a straight line: leveraging semi-metricity in graph analysis. Proc VLDB Endowment 9(9):672\u2013683","journal-title":"Proc VLDB Endowment"},{"issue":"4","key":"1479_CR3","doi-asserted-by":"publisher","first-page":"046110","DOI":"10.1103\/PhysRevE.78.046110","volume":"78","author":"A Lancichinetti","year":"2008","unstructured":"Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110","journal-title":"Phys Rev E"},{"key":"1479_CR4","unstructured":"Aggarwal CC, Wang H (2010) A survey of clustering algorithms for graph data. In Managing and mining graph data. Springer, Boston, pp 275\u2013301"},{"key":"1479_CR5","unstructured":"Sadhanala V, Wang Y-X, Tibshirani R (2016) Graph sparsification approaches for laplacian smoothing. In: Artificial Intelligence and Statistics, pp 1250\u20131259"},{"issue":"1","key":"1479_CR6","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"Andrew McGregor","year":"2014","unstructured":"McGregor Andrew (2014) Graph stream algorithms: a survey. ACM SIGMOD Rec 43(1):9\u201320","journal-title":"ACM SIGMOD Rec"},{"key":"1479_CR7","doi-asserted-by":"crossref","unstructured":"Bencz\u00far AA, Karger DR (1996) Approximating st minimum cuts in \u00d5 (n 2) time. In: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, pp 47\u201355","DOI":"10.1145\/237814.237827"},{"issue":"4","key":"1479_CR8","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1137\/08074489X","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman DA, Teng S-H (2011) Spectral sparsification of graphs. SIAM J Comput 40(4):981\u20131025","journal-title":"SIAM J Comput"},{"issue":"8","key":"1479_CR9","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/2492007.2492029","volume":"56","author":"J Batson","year":"2013","unstructured":"Batson J, Spielman DA, Srivastava N, Teng S-H (2013) Spectral sparsification of graphs: theory and algorithms. Commun ACM 56(8):87\u201394","journal-title":"Commun ACM"},{"key":"1479_CR10","unstructured":"Lee YT, Sun H (2015) Constructing linear-sized spectral sparsification in almost-linear time. In: IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS).IEEE , pp 250\u2013269"},{"issue":"6","key":"1479_CR11","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman DA, Srivastava N (2011) Graph sparsification by effective resistances. SIAM J Comput 40(6):1913\u20131926","journal-title":"SIAM J Comput"},{"issue":"1","key":"1479_CR12","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer I, Das G, Dobkin D, Joseph D, Soares J (1993) On sparse spanners of weighted graphs. Discret Comput Geom 9(1):81\u2013100","journal-title":"Discret Comput Geom"},{"issue":"1","key":"1479_CR13","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg D, Sch\u00e4ffer AA (1989) Graph spanners. J Graph Theory 13(1):99\u2013116","journal-title":"J Graph Theory"},{"issue":"4","key":"1479_CR14","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S Baswana","year":"2007","unstructured":"Baswana S, Sen S (2007) A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct Algorithm 30(4):532\u2013563","journal-title":"Random Struct Algorithm"},{"key":"1479_CR15","doi-asserted-by":"crossref","unstructured":"Roditty L, Zwick U (2004) On dynamic shortest paths problems. In: European Symposium on Algorithms. Springer, Berlin, pp 580\u2013591","DOI":"10.1007\/978-3-540-30140-0_52"},{"key":"1479_CR16","doi-asserted-by":"crossref","unstructured":"Ruan N, Jin R, Huang Y (2011) Distance preserving graph simplification. In: 2011 IEEE 11Th International Conference on Data Mining (ICDM). IEEE, pp 1200\u20131205","DOI":"10.1109\/ICDM.2011.57"},{"issue":"4","key":"1479_CR17","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1109\/TKDE.2013.43","volume":"26","author":"J Gao","year":"2014","unstructured":"Gao J, Zhou J, Yu JX, Wang T (2014) Shortest path computing in relational dbmss. IEEE Trans knowl Data Eng 26(4):997\u20131011","journal-title":"IEEE Trans knowl Data Eng"},{"key":"1479_CR18","unstructured":"Anderson DG, Gu M, Melgaard C (2014) An Efficient Algorithm for Unweighted Spectral Graph Sparsification. arXiv:\n                    http:\/\/arXiv.org\/abs\/1410.4273"},{"key":"1479_CR19","doi-asserted-by":"crossref","unstructured":"Lindner G, Staudt CL, Hamann Mx, Meyerhenke H, Wagner D (2015) Structure-preserving sparsification of social networks. In: IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE, pp 448\u2013454","DOI":"10.1145\/2808797.2809313"},{"key":"1479_CR20","doi-asserted-by":"crossref","unstructured":"Basuchowdhuri P, Sikdar S, Shreshtha S, Majumder S (2016) Detecting Community Structures in Social Networks by Graph Sparsification. In: Proceedings of the 3rd IKDD Conference on Data Science. ACM, pp 5","DOI":"10.1145\/2888451.2888479"},{"key":"1479_CR21","unstructured":"Zhao Peixiang. (2015) Gsparsify Graph Motif Based Sparsification for Graph Clustering. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, pp 373\u2013382"},{"key":"1479_CR22","doi-asserted-by":"crossref","unstructured":"Mathioudakis M, Bonchi F, Castillo C, Gionis A, Ukkonen A (2011) Sparsification of influence networks. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 529\u2013537","DOI":"10.1145\/2020408.2020492"},{"issue":"12","key":"1479_CR23","first-page":"37","volume":"132","author":"K Mallikarjuna","year":"2015","unstructured":"Mallikarjuna K, Prasad KS, Subramanyam MV (2015) Compression of Noisy Images based on Sparsification using Discrete Rajan Transform. Int J Comput Appl 132(12):37\u201343","journal-title":"Int J Comput Appl"},{"key":"1479_CR24","doi-asserted-by":"crossref","unstructured":"Maccioni A, Abadi DJ (2016) Scalable pattern matching over compressed graphs via dedensification. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp 1755\u20131764","DOI":"10.1145\/2939672.2939856"},{"key":"1479_CR25","doi-asserted-by":"crossref","unstructured":"Charikar M, Leighton Tx, Li S, Moitra A (2010) Vertex sparsifiers and abstract rounding algorithms. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, pp 265\u2013274","DOI":"10.1109\/FOCS.2010.32"},{"key":"1479_CR26","unstructured":"Ruan N, Jin R, Wang G, Huang K (2012) Network backbone discovery using edge clustering. arXiv:\n                    http:\/\/arXiv.org\/abs\/1202.1842"},{"key":"1479_CR27","doi-asserted-by":"crossref","unstructured":"Toivonen H, Mahler S, Zhou F (2010) A framework for path-oriented network simplification. In: International Symposium on Intelligent Data Analysis. Springer, Berlin, pp 220\u2013231","DOI":"10.1007\/978-3-642-13062-5_21"},{"key":"1479_CR28","doi-asserted-by":"crossref","unstructured":"Zhou F, Mahler S, Toivonen H (2012) Simplification of networks by edge pruning. In: Bisociative Knowledge Discovery. Springer, Berlin, pp 179\u2013198","DOI":"10.1007\/978-3-642-31830-6_13"},{"key":"1479_CR29","doi-asserted-by":"crossref","unstructured":"Parchas P, Papailiou N, Papadias D, Bonchi F (2018) Uncertain Graph Sparsification. IEEE Transactions on Knowledge and Data Engineering","DOI":"10.1109\/ICDE.2019.00265"},{"key":"1479_CR30","doi-asserted-by":"crossref","unstructured":"Feng Z (2016) Spectral graph sparsification in nearly-linear time leveraging efficient spectral perturbation analysis. In: Proceedings of the 53rd Annual Design Automation Conference. ACM, pp 57","DOI":"10.1145\/2897937.2898094"},{"key":"1479_CR31","unstructured":"Hancock ER (2017) Shape Simplification Through Graph Sparsification. In: Graph-Based Representations in Pattern Recognition: 11th IAPR-TC-15 International Workshop, GbRPR 2017, Anacapri, Italy, Proceedings. Springer, vol 10310, pp 13"},{"key":"1479_CR32","doi-asserted-by":"crossref","unstructured":"Abraham I, Durfee D, Koutis I, Krinninger S, Peng R (2016) On fully dynamic graph sparsifiers. In: IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, pp 335\u2013 344","DOI":"10.1109\/FOCS.2016.44"},{"issue":"2","key":"1479_CR33","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1017\/nws.2015.11","volume":"3","author":"T Simas","year":"2015","unstructured":"Simas T, Rocha LM (2015) Distance closures on complex networks. Netw Sci 3(2):227\u2013268","journal-title":"Netw Sci"},{"issue":"1","key":"1479_CR34","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/s10489-014-0637-7","volume":"42","author":"W Nawaz","year":"2015","unstructured":"Nawaz W, Khan K-U, Lee Y-K (2015) SPORE: Shortest path overlapped regions and confined traversals towards graph clustering. Appl Intell 42(1):208\u2013232","journal-title":"Appl Intell"},{"key":"1479_CR35","doi-asserted-by":"crossref","unstructured":"Akiba T, Iwata Y, Yoshida Y (2013) Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, pp 349\u2013360","DOI":"10.1145\/2463676.2465315"},{"issue":"8","key":"1479_CR36","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1016\/j.jcss.2007.08.006","volume":"74","author":"M Belkin","year":"2008","unstructured":"Belkin M, Niyogi P (2008) Towards a theoretical foundation for Laplacian-based manifold methods. J Comput Syst Sci 74(8):1289\u20131308","journal-title":"J Comput Syst Sci"},{"key":"1479_CR37","doi-asserted-by":"crossref","unstructured":"Gionis A, Rozenshtein P, Tatti N, Terzi E (2017) Community-aware network sparsification. In: Proceedings of the 2017 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, pp 426\u2013434","DOI":"10.1137\/1.9781611974973.48"},{"key":"1479_CR38","unstructured":"Feng Z (2018) Similarity-aware spectral sparsification by edge filtering. In 2018 55th ACM\/ESDA\/IEEE Design Automation Conference (DAC). IEEE, pp 1\u20136"},{"key":"1479_CR39","doi-asserted-by":"crossref","unstructured":"Zhao Z, Feng Z (2017) A spectral graph sparsification approach to scalable vectorless power grid integrity verification. In: Proceedings of the 54th Annual Design Automation Conference 2017. ACM, pp 68","DOI":"10.1145\/3061639.3062193"},{"key":"1479_CR40","doi-asserted-by":"crossref","unstructured":"Li K, Zha H, Su Y, Yan X (2018) Unsupervised neural categorization for scientific publications. In: Proceedings of the 2018 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, pp 37\u201345","DOI":"10.1137\/1.9781611975321.5"},{"key":"1479_CR41","doi-asserted-by":"crossref","unstructured":"Zhang C, Bi J, Xu S, Ramentol E, Fan G, Qiao B, Fujita H (2019) Multi-Imbalance: An open-source software for multi-class imbalance learning. Knowledge-Based Systems","DOI":"10.1016\/j.knosys.2019.03.001"},{"key":"1479_CR42","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.ins.2019.02.065","volume":"486","author":"H Fujita","year":"2019","unstructured":"Fujita H, Cimr D (2019) Computer Aided detection for fibrillations and flutters using deep convolutional neural network. Inf Sci 486:231\u2013239","journal-title":"Inf Sci"},{"key":"1479_CR43","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.eswa.2017.04.003","volume":"82","author":"C Zhang","year":"2017","unstructured":"Zhang C, Liu C, Zhang X, Almpanidis G (2017) An up-to-date comparison of state-of-the-art classification algorithms. Expert Syst Appl 82:128\u2013150","journal-title":"Expert Syst Appl"},{"key":"1479_CR44","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.neucom.2018.07.032","volume":"315","author":"H Yuan","year":"2018","unstructured":"Yuan H, Li J, Lai LL, Tang YY (2018) Graph-based multiple rank regression for image classification. Neurocomputing 315:394\u2013404","journal-title":"Neurocomputing"}],"container-title":["Applied Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-019-01479-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10489-019-01479-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-019-01479-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,1]],"date-time":"2020-05-01T23:24:34Z","timestamp":1588375474000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10489-019-01479-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,3]]},"references-count":44,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["1479"],"URL":"https:\/\/doi.org\/10.1007\/s10489-019-01479-4","relation":{},"ISSN":["0924-669X","1573-7497"],"issn-type":[{"type":"print","value":"0924-669X"},{"type":"electronic","value":"1573-7497"}],"subject":[],"published":{"date-parts":[[2019,5,3]]},"assertion":[{"value":"3 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}