{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T16:07:57Z","timestamp":1775146077835,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T00:00:00Z","timestamp":1750032000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T00:00:00Z","timestamp":1750032000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Open access funding provided by CSIRO Library Services"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cluster Comput"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Structural Hole (SH) theory states that the node which acts as a connecting link among otherwise disconnected communities gets positional advantages in the network. These nodes are called Structural Hole Spanners (SHS). Numerous solutions are proposed to discover SHSs; however, most of the solutions are only applicable to static networks. Since real-world networks are dynamic networks; consequently, in this study, we aim to discover SHSs in dynamic networks. We first propose an efficient Tracking-SHS algorithm for updating SHSs in dynamic networks. Our algorithm reuses the information obtained during the initial runs of the static algorithm and avoids the recomputations for the nodes unaffected by the updates. Besides, we also design a Graph Neural Network-based model, GNN-SHS, to discover SHSs in dynamic networks, aiming to reduce the computational cost while achieving high accuracy. We provide a theoretical analysis of the Tracking-SHS algorithm and prove that Tracking-SHS algorithm achieves 1.6 times of speedup compared with the static algorithm. We perform extensive experiments, and our results demonstrate that the Tracking-SHS algorithm attains a minimum of 3.24 times speedup over the static algorithm. Also, the proposed second model GNN-SHS is on an average 671.6 times faster than the Tracking-SHS algorithm.<\/jats:p>","DOI":"10.1007\/s10586-024-05043-9","type":"journal-article","created":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T12:11:31Z","timestamp":1750075891000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Tracking top-k structural hole spanners in dynamic networks"],"prefix":"10.1007","volume":"28","author":[{"given":"Diksha","family":"Goel","sequence":"first","affiliation":[]},{"given":"Hong","family":"Shen","sequence":"additional","affiliation":[]},{"given":"Hui","family":"Tian","sequence":"additional","affiliation":[]},{"given":"Mingyu","family":"Guo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,16]]},"reference":[{"key":"5043_CR1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2021.3057881","author":"J Guo","year":"2021","unstructured":"Guo, J., Liu, A., Ota, K., Dong, M., Deng, X., Xiong, N.: ITCN: an intelligent trust collaboration network system in IoT. IEEE Trans. Netw. Sci. Eng. (2021). https:\/\/doi.org\/10.1109\/TNSE.2021.3057881","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"issue":"2021","key":"5043_CR2","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.ins.2021.09.017","volume":"581","author":"N Binesh","year":"2021","unstructured":"Binesh, N., Ghatee, M.: Distance-aware optimization model for influential nodes identification in social networks with independent cascade diffusion. Inform. Sci. 581(2021), 88\u2013105 (2021). https:\/\/doi.org\/10.1016\/j.ins.2021.09.017","journal-title":"Inform. Sci."},{"key":"5043_CR3","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1145\/3278532.3278550","volume":"2018","author":"S Zannettou","year":"2018","unstructured":"Zannettou, S., Caulfield, T., Blackburn, J., De Cristofaro, E., Sirivianos, M., Stringhini, G., Suarez-Tangil, G.: On the origins of memes by means of fringe web communities. In Proc. Internet Measur. Conf. 2018, 188\u2013202 (2018). https:\/\/doi.org\/10.1145\/3278532.3278550","journal-title":"In Proc. Internet Measur. Conf."},{"key":"5043_CR4","first-page":"23","volume-title":"Structural Holes: The Social Structure of Competition","author":"RS Burt","year":"2009","unstructured":"Burt, R.S.: Structural Holes: The Social Structure of Competition, pp. 23\u2013100. Harvard University Press, Harvard (2009)"},{"issue":"1","key":"5043_CR5","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1023\/a:1010589300829","volume":"51","author":"ED Rinia","year":"2001","unstructured":"Rinia, E.D., Van Leeuwen, T., Bruins, E., Van Vuren, H., Van Raan, A.: Citation delay in interdisciplinary knowledge exchange. Scientometrics 51(1), 293\u2013309 (2001). https:\/\/doi.org\/10.1023\/a:1010589300829","journal-title":"Scientometrics"},{"key":"5043_CR6","doi-asserted-by":"publisher","unstructured":"Lou, T., Tang, J.: Mining structural hole spanners through information diffusion in social networks. In Proceedings of the 22nd international conference on World Wide Web. 825\u2013836. (2013) https:\/\/doi.org\/10.1145\/2488388.2488461","DOI":"10.1145\/2488388.2488461"},{"issue":"2021","key":"5043_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.ins.2020.07.040","volume":"544","author":"LF Lin","year":"2021","unstructured":"Lin, L.F., Li, Y.M.: An efficient approach to identify social disseminators for timely information diffusion. Inform. Sci. 544(2021), 78\u201396 (2021). https:\/\/doi.org\/10.1016\/j.ins.2020.07.040","journal-title":"Inform. Sci."},{"key":"5043_CR8","doi-asserted-by":"publisher","unstructured":"Amelkin, V., Singh, A.K.: Fighting opinion control in social networks via link recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 677\u2013685. https:\/\/doi.org\/10.1145\/3292500.3330960","DOI":"10.1145\/3292500.3330960"},{"issue":"2019","key":"5043_CR9","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.future.2018.11.023","volume":"94","author":"A Zareie","year":"2019","unstructured":"Zareie, A., Sheikhahmadi, A., Jalili, M.: Influential node ranking in social networks based on neighborhood diversity. Future Gener. Comput. Syst. 94(2019), 120\u2013129 (2019). https:\/\/doi.org\/10.1016\/j.future.2018.11.023","journal-title":"Future Gener. Comput. Syst."},{"issue":"2021","key":"5043_CR10","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1016\/j.ins.2021.09.012","volume":"580","author":"Y Zhenhua","year":"2021","unstructured":"Zhenhua, Y., Si, L., Wang, D., Li, Z.: Modeling and analysis of rumor propagation in social networks. Inform. Sci. 580(2021), 857\u2013873 (2021). https:\/\/doi.org\/10.1016\/j.ins.2021.09.012","journal-title":"Inform. Sci."},{"issue":"2021","key":"5043_CR11","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.ins.2020.10.057","volume":"551","author":"X Zhao","year":"2021","unstructured":"Zhao, X., Liang, J., Wang, J.: A community detection algorithm based on graph compression for large-scale social networks. Inform. Sci. 551(2021), 358\u2013372 (2021). https:\/\/doi.org\/10.1016\/j.ins.2020.10.057","journal-title":"Inform. Sci."},{"issue":"9","key":"5043_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3558001","volume":"55","author":"H Ahmad","year":"2023","unstructured":"Ahmad, H., Dharmadasa, I., Ullah, F., Babar, M.A.: A review on C3I systems\u2019 security: vulnerabilities, attacks, and countermeasures. Comput. Surv. 55(9), 1\u201338 (2023)","journal-title":"Comput. Surv."},{"issue":"1","key":"5043_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10588-006-7084-x","volume":"12","author":"SP Borgatti","year":"2006","unstructured":"Borgatti, S.P.: Identifying sets of key players in a social network. Comput. Math. Org. Theory 12(1), 21\u201334 (2006). https:\/\/doi.org\/10.1007\/s10588-006-7084-x","journal-title":"Comput. Math. Org. Theory"},{"issue":"6","key":"5043_CR14","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1121\/1.1906679","volume":"22","author":"A Bavelas","year":"1950","unstructured":"Bavelas, A.: Communication patterns in task-oriented groups. J. Acoustical Soc. Am. 22(6), 725\u2013730 (1950). https:\/\/doi.org\/10.1121\/1.1906679","journal-title":"J. Acoustical Soc. Am."},{"key":"5043_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.4159\/9780674029095","volume-title":"Structural Holes: The Social Structure of Competition","author":"R Burt","year":"1992","unstructured":"Burt, R.: Structural Holes: The Social Structure of Competition, pp. 23\u2013100. Harvard University Press, Harvard (1992)"},{"key":"5043_CR16","doi-asserted-by":"publisher","unstructured":"Rezvani, M., Liang, W., Xu, W., Liu, C.: Identifying top-k structural hole spanners in large-scale social networks. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. 263\u2013272. (2015) https:\/\/doi.org\/10.1145\/2806416.2806431","DOI":"10.1145\/2806416.2806431"},{"key":"5043_CR17","doi-asserted-by":"publisher","unstructured":"Gong, Q., Zhang, J., Wang, X., Chen, Y.: Identifying structural hole spanners in online social networks using machine learning. In Proceedings of the ACM SIGCOMM 2019 Conference Posters and Demos. 93\u201395. (2019) https:\/\/doi.org\/10.1145\/3342280.3342319","DOI":"10.1145\/3342280.3342319"},{"issue":"1","key":"5043_CR18","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1016\/j.jet.2007.01.006","volume":"137","author":"S Goyal","year":"2007","unstructured":"Goyal, S., Vega-Redondo, F.: Structural holes in social networks. J. Economic Theory 137(1), 460\u2013492 (2007). https:\/\/doi.org\/10.1016\/j.jet.2007.01.006","journal-title":"J. Economic Theory"},{"key":"5043_CR19","doi-asserted-by":"publisher","unstructured":"He, L., Lu, C.T., Ma, J., Cao, J., Shen, L., Yu, P.S.: Joint community and structural hole spanner detection via harmonic modularity. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 875\u2013884. (2016) https:\/\/doi.org\/10.1145\/2939672.2939807","DOI":"10.1145\/2939672.2939807"},{"issue":"5","key":"5043_CR20","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1109\/TKDE.2017.2651825","volume":"29","author":"Xu Wenzheng","year":"2017","unstructured":"Wenzheng, Xu., Rezvani, Mojtaba, Liang, Weifa, Yu, Jeffrey Xu, Liu, Chengfei: Efficient algorithms for the identification of Top-$$k$$ structural hole spanners in large social networks. IEEE Trans. Knowledge Data Eng. 29(5), 1017\u20131030 (2017). https:\/\/doi.org\/10.1109\/TKDE.2017.2651825","journal-title":"IEEE Trans. Knowledge Data Eng."},{"issue":"2019","key":"5043_CR21","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.ins.2019.07.072","volume":"505","author":"Xu Wenzheng","year":"2019","unstructured":"Wenzheng, Xu., Li, Tong, Liang, Weifa, Yu, Jeffrey Xu, Yang, Ning, Gao, Shaobing: Identifying structural hole spanners to maximally block information propagation. Inform. Sci. 505(2019), 100\u2013126 (2019). https:\/\/doi.org\/10.1016\/j.ins.2019.07.072","journal-title":"Inform. Sci."},{"key":"5043_CR22","doi-asserted-by":"publisher","unstructured":"Tang, J., Lou, T., Kleinberg, J.: Inferring social ties across heterogenous networks. In Proceedings of the fifth ACM international conference on Web search and data mining. 743\u2013752,(2012). https:\/\/doi.org\/10.1145\/2124295.2124382","DOI":"10.1145\/2124295.2124382"},{"key":"5043_CR23","unstructured":"Ding, L., Wang, J., Wei, W.: Method for detecting key nodes who occupy structural holes in social network sites. In Pacific Asia Conference On Information Systems (PACIS). Association For Information System (2016)"},{"key":"5043_CR24","unstructured":"Goel, D.: Enhancing Network Resilience through Machine Learning-powered Graph Combinatorial Optimization: Applications in Cyber Defense and Information Diffusion. arXiv preprint arXiv:2310.10667 (2023)"},{"issue":"1","key":"5043_CR25","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10115-013-0693-z","volume":"42","author":"Jaewon Yang","year":"2015","unstructured":"Yang, Jaewon, Leskovec, Jure: Defining and evaluating network communities based on ground-truth. Knowl. Inform. Syst. 42(1), 181\u2013213 (2015). https:\/\/doi.org\/10.1007\/s10115-013-0693-z","journal-title":"Knowl. Inform. Syst."},{"issue":"2020","key":"5043_CR26","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2020.103690","volume":"93","author":"C Gong","year":"2020","unstructured":"Gong, C., Yajun, D., Li, X., Chen, X., Li, X., Wang, Y., Zhou, Q.: Structural hole-based approach to control public opinion in a social network. Eng. Appl. Artif. Intel. 93(2020), 103690 (2020). https:\/\/doi.org\/10.1016\/j.engappai.2020.103690","journal-title":"Eng. Appl. Artif. Intel."},{"issue":"2020","key":"5043_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2020.105916","volume":"199","author":"Y Zhang","year":"2020","unstructured":"Zhang, Y., Hua, X., Yunfeng, X., Deng, J., Juan, G., Ma, R., Lai, J., Jiangtao, H., Xiaoshuai, Y., Hou, L., et al.: Finding structural hole spanners based on community forest model and diminishing marginal utility in large scale social networks. Knowl. Based Syst. 199(2020), 105916 (2020). https:\/\/doi.org\/10.1016\/j.knosys.2020.105916","journal-title":"Knowl. Based Syst."},{"issue":"2020","key":"5043_CR28","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.neucom.2020.05.039","volume":"410","author":"JX Luo","year":"2020","unstructured":"Luo, J.X., YaJun, D.: Detecting community structure and structural hole spanner simultaneously by using graph convolutional network based Auto-Encoder. Neurocomputing 410(2020), 138\u2013150 (2020). https:\/\/doi.org\/10.1016\/j.neucom.2020.05.039","journal-title":"Neurocomputing"},{"issue":"2024","key":"5043_CR29","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2024.123636","volume":"249","author":"D Goel","year":"2024","unstructured":"Goel, D., Shen, H., Tian, H., Guo, M.: Effective graph-neural-network based models for discovering structural hole spanners in large-scale and diverse networks. Exp. Syst. Appl. 249(2024), 123636 (2024)","journal-title":"Exp. Syst. Appl."},{"issue":"1","key":"5043_CR30","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/TNNLS.2020.2978386","volume":"32","author":"W Zonghan","year":"2020","unstructured":"Zonghan, W., Pan, S., Chen, F., Long, G., Zhang, C., Yu, S., Philip: A comprehensive survey on graph neural networks. IEEE Trans. Neural Netw. Learn. Syst. 32(1), 4\u201324 (2020). https:\/\/doi.org\/10.1109\/TNNLS.2020.2978386","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"5043_CR31","unstructured":"Veli\u010dkovi\u0107, Petar, C., Guillem ,C., Arantxa , R., Adriana, L., Pietro, B., Y.: Graph attention networks. International Conference on Learning Representations (ICLR) (2018)"},{"key":"5043_CR32","unstructured":"Kipf, Thomas\u00a0N., Welling, Max: Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR) (2017)"},{"issue":"5","key":"5043_CR33","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1109\/TKDE.2018.2849727","volume":"31","author":"P Cui","year":"2018","unstructured":"Cui, P., Wang, X., Pei, J., Zhu, W.: A survey on network embedding. IEEE Trans. Knowl. Data Eng. 31(5), 833\u2013852 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2021","key":"5043_CR34","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2021.108191","volume":"195","author":"C Aguilar-Fuster","year":"2021","unstructured":"Aguilar-Fuster, C., Rubio-Loyola, J.: A novel evaluation function for higher acceptance rates and more profitable metaheuristic-based online virtual network embedding. Comput. Netw. 195(2021), 108191 (2021)","journal-title":"Comput. Netw."},{"issue":"2","key":"5043_CR35","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1109\/TNET.2011.2170849","volume":"20","author":"TN Dinh","year":"2011","unstructured":"Dinh, T.N., Xuan, Y., Thai, M.T., Pardalos, P.M., Znati, T.: On new approaches of assessing network vulnerability: hardness and approximation. IEEE\/ACM Trans. Netw. 20(2), 609\u2013619 (2011)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"5043_CR36","unstructured":"Loukas, A.: What graph neural networks cannot learn: depth vs width. International Conference on Learning Representations (ICLR) (2020)"},{"issue":"4","key":"5043_CR37","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","volume":"33","author":"Wayne W Zachary","year":"1977","unstructured":"Zachary, Wayne W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33(4), 452\u2013473 (1977). https:\/\/doi.org\/10.1086\/jar.33.4.3629752","journal-title":"J. Anthropol. Res."},{"issue":"4","key":"5043_CR38","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/s00265-003-0651-y","volume":"54","author":"D Lusseau","year":"2003","unstructured":"Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E., Dawson, S.M.: The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54(4), 396\u2013405 (2003). https:\/\/doi.org\/10.1007\/s00265-003-0651-y","journal-title":"Behav. Ecol. Sociobiol."},{"issue":"12","key":"5043_CR39","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821\u20137826 (2002). https:\/\/doi.org\/10.1073\/pnas.122653799","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"1959","key":"5043_CR40","first-page":"290","volume":"6","author":"P Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P., R\u00e9nyi, A.: On Random Graphs I. Publ. Math. Debrecen 6(1959), 290\u2013297 (1959)","journal-title":"Publ. Math. Debrecen"},{"key":"5043_CR41","doi-asserted-by":"crossref","unstructured":"Li, Q., Han, Z., Wu, X.M.: Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference on artificial intelligence (2018)","DOI":"10.1609\/aaai.v32i1.11604"},{"key":"5043_CR42","doi-asserted-by":"crossref","unstructured":"Yang, L., Gu, J., Wang, C., Cao, X., Zhai, L., Jin, D. and Guo, Y.: Toward unsupervised graph neural network: Interactive clustering and embedding via optimal transport. In 2020 IEEE International Conference on Data Mining (ICDM). IEEE, 1358\u20131363 (2020)","DOI":"10.1109\/ICDM50108.2020.00177"}],"container-title":["Cluster Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-024-05043-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10586-024-05043-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-024-05043-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T19:16:10Z","timestamp":1763147770000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10586-024-05043-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,16]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["5043"],"URL":"https:\/\/doi.org\/10.1007\/s10586-024-05043-9","relation":{},"ISSN":["1386-7857","1573-7543"],"issn-type":[{"value":"1386-7857","type":"print"},{"value":"1573-7543","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,16]]},"assertion":[{"value":"4 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2025","order":6,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":7,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This article was originally published under the subscription model but it is now published under an Open Access license","order":8,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"363"}}