{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T04:18:44Z","timestamp":1771474724167,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T00:00:00Z","timestamp":1618704000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Sino-German Institutes of Social Computing"},{"name":"Key R&D Program of Jiangsu Province, China","award":["BE2018116"],"award-info":[{"award-number":["BE2018116"]}]},{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2018YFB 1004704"],"award-info":[{"award-number":["2018YFB 1004704"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61972196, 61672278, 61832008, 61832005, and 71772176"],"award-info":[{"award-number":["61972196, 61672278, 61832008, 61832005, and 71772176"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Collaborative Innovation Center of Novel Software Technology and Industrialization"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,8,31]]},"abstract":"<jats:p>\n            Katz centrality is a fundamental concept to measure the influence of a vertex in a social network. However, existing approaches to calculating Katz centrality in a large-scale network are unpractical and computationally expensive. In this article, we propose a novel method to estimate Katz centrality based on graph sampling techniques, which object to achieve comparable estimation accuracy of the state-of-the-arts with much lower computational complexity. Specifically, we develop a Horvitz\u2013Thompson estimate for Katz centrality by using a multi-round sampling approach and deriving an unbiased mean value estimator. We further propose\n            <jats:italic>SAKE<\/jats:italic>\n            , a\n            <jats:bold>\n              <jats:underline>S<\/jats:underline>\n            <\/jats:bold>\n            ampling-based\n            <jats:bold>\n              <jats:underline>A<\/jats:underline>\n            <\/jats:bold>\n            lgorithm for fast\n            <jats:bold>\n              <jats:underline>K<\/jats:underline>\n            <\/jats:bold>\n            atz centrality\n            <jats:bold>\n              <jats:underline>E<\/jats:underline>\n            <\/jats:bold>\n            stimation. We prove that the estimator calculated by\n            <jats:italic>SAKE<\/jats:italic>\n            is probabilistically guaranteed to be within an additive error from the exact value. Extensive evaluation experiments based on four real-world networks show that the proposed algorithm can estimate Katz centralities for partial vertices with low sampling rate, low computation time, and it works well in identifying high influence vertices in social networks.\n          <\/jats:p>","DOI":"10.1145\/3441646","type":"journal-article","created":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T16:05:45Z","timestamp":1618761945000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["SAKE"],"prefix":"10.1145","volume":"15","author":[{"given":"Mingkai","family":"Lin","sequence":"first","affiliation":[{"name":"Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9199-3655","authenticated-orcid":false,"given":"Wenzhong","family":"Li","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology and Sino-German Institutes of Social Computing, Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lynda J.","family":"Song","sequence":"additional","affiliation":[{"name":"University of Leeds, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cam-Tu","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoliang","family":"Wang","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanglu","family":"Lu","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology and Sino-German Institutes of Social Computing, Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2017. Livemocha network dataset \u2013 KONECT. Retrieved from http:\/\/konect.uni-koblenz.de\/networks\/livemocha.  2017. Livemocha network dataset \u2013 KONECT. Retrieved from http:\/\/konect.uni-koblenz.de\/networks\/livemocha."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 2nd Workshop on Information in Networks (WIN\u201910)","author":"Ahmed Nesreen K.","year":"2010","unstructured":"Nesreen K. Ahmed , Jennifer Neville , and Ramana Kompella . 2010 . Reconsidering the foundations of network sampling . In Proceedings of the 2nd Workshop on Information in Networks (WIN\u201910) . Nesreen K. Ahmed, Jennifer Neville, and Ramana Kompella. 2010. Reconsidering the foundations of network sampling. In Proceedings of the 2nd Workshop on Information in Networks (WIN\u201910)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601438"},{"key":"e_1_2_1_4_1","volume-title":"Dbpedia: A nucleus for a web of open data. In The Semantic Web","author":"Auer S\u00f6ren","year":"2007","unstructured":"S\u00f6ren Auer , Christian Bizer , Georgi Kobilarov , Jens Lehmann , Richard Cyganiak , and Zachary Ives . 2007 . Dbpedia: A nucleus for a web of open data. In The Semantic Web . Springer , 722--735. S\u00f6ren Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2007. Dbpedia: A nucleus for a web of open data. In The Semantic Web. Springer, 722--735."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnt007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2013.865686"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1972.9989806"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.05.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052608"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(03)00012-1"},{"key":"e_1_2_1_11_1","volume-title":"Statistical Analysis of Network Data: Methods and Models","author":"Kolaczyk Eric D.","unstructured":"Eric D. Kolaczyk . 2009. Statistical Analysis of Network Data: Methods and Models . Springer . Eric D. Kolaczyk. 2009. Statistical Analysis of Network Data: Methods and Models. Springer."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 27th International Conference on World Wide Web (WWW\u201918)","author":"Eden Talya","unstructured":"Talya Eden , Shweta Jain , Ali Pinar , Dana Ron , and C. Seshadhri . 2018. Provable and practical approximations for the degree distribution using sublinear graph samples . In Proceedings of the 27th International Conference on World Wide Web (WWW\u201918) . 449--458. Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri. 2018. Provable and practical approximations for the degree distribution using sublinear graph samples. In Proceedings of the 27th International Conference on World Wide Web (WWW\u201918). 449--458."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257976"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013470632383"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462078"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 22nd International Conference on World Wide Web (WWW\u201913)","author":"Stephen","unstructured":"Stephen J. Hardiman and Liran Katzir. 2013. Estimating clustering coefficients and size of social networks via random walk . In Proceedings of the 22nd International Conference on World Wide Web (WWW\u201913) . ACM, 539--550. Stephen J. Hardiman and Liran Katzir. 2013. Estimating clustering coefficients and size of social networks via random walk. In Proceedings of the 22nd International Conference on World Wide Web (WWW\u201913). ACM, 539--550."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-soc-060116-053556"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1952.10483446"},{"key":"e_1_2_1_20_1","volume-title":"Refining approximating betweenness centrality based on samplings. arXiv preprint arXiv:1608.04472","author":"Ji Shiyu","year":"2016","unstructured":"Shiyu Ji and Zenghui Yan . 2016. Refining approximating betweenness centrality based on samplings. arXiv preprint arXiv:1608.04472 ( 2016 ). Shiyu Ji and Zenghui Yan. 2016. Refining approximating betweenness centrality based on samplings. arXiv preprint arXiv:1608.04472 (2016)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.016102"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 17th International Conference on World Wide Web (WWW\u201908)","author":"Leskovec Jure","unstructured":"Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , and Michael W. Mahoney . 2008. Statistical properties of community structure in large social and information networks . In Proceedings of the 17th International Conference on World Wide Web (WWW\u201908) . ACM, 695--704. Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. 2008. Statistical properties of community structure in large social and information networks. In Proceedings of the 17th International Conference on World Wide Web (WWW\u201908). ACM, 695--704."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP\u201919)","author":"Lin Mingkai","year":"2019","unstructured":"Mingkai Lin , Wenzhong Li , Cam-tu Nguyen, Xiaoliang Wang , and Sanglu Lu . 2019 . Sampling based Katz centrality estimation for large-scale social networks . In Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP\u201919) . Springer, 584--598. Mingkai Lin, Wenzhong Li, Cam-tu Nguyen, Xiaoliang Wang, and Sanglu Lu. 2019. Sampling based Katz centrality estimation for large-scale social networks. In Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP\u201919). Springer, 584--598."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 17th International Conference on Knowledge Discovery and Data Mining (KDD\u201911)","author":"Arun","unstructured":"Arun S. Maiya and Tanya Y. Berger-Wolf. 2011. Benefits of bias: Towards better characterization of network sampling . In Proceedings of the 17th International Conference on Knowledge Discovery and Data Mining (KDD\u201911) . ACM, 105--113. Arun S. Maiya and Tanya Y. Berger-Wolf. 2011. Benefits of bias: Towards better characterization of network sampling. In Proceedings of the 17th International Conference on Knowledge Discovery and Data Mining (KDD\u201911). ACM, 105--113."},{"key":"e_1_2_1_28_1","first-page":"100","article-title":"Introduction to information retrieval","volume":"16","author":"Manning Christopher","year":"2010","unstructured":"Christopher Manning , Prabhakar Raghavan , and Hinrich Sch\u00fctze . 2010 . Introduction to information retrieval . Natural Language Engineering 16 , 1 (2010), 100 -- 103 . Christopher Manning, Prabhakar Raghavan, and Hinrich Sch\u00fctze. 2010. Introduction to information retrieval. Natural Language Engineering 16, 1 (2010), 100--103.","journal-title":"Natural Language Engineering"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigComp.2018.00107"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Conference on Parallel Processing and Applied Mathematics (PPAM\u201917)","author":"Nathan Eisha","unstructured":"Eisha Nathan and David A. Bader . 2017. Approximating personalized Katz centrality in dynamic graphs . In Proceedings of the International Conference on Parallel Processing and Applied Mathematics (PPAM\u201917) . Springer, 290--302. Eisha Nathan and David A. Bader. 2017. Approximating personalized Katz centrality in dynamic graphs. In Proceedings of the International Conference on Parallel Processing and Applied Mathematics (PPAM\u201917). Springer, 290--302."},{"key":"e_1_2_1_31_1","volume-title":"International Conference on Computational Science (ICCS\u201917)","volume":"108","author":"Nathan Eisha","year":"2017","unstructured":"Eisha Nathan , Geoffrey Sanders , James Fairbanks , and David A. Bader . 2017. Graph ranking guarantees for numerical approximations to Katz centrality . In International Conference on Computational Science (ICCS\u201917) , Vol. 108 . Elsevier, 68--78. DOI:10.1016\/j.procs. 2017 .05.021 10.1016\/j.procs.2017.05.021 Eisha Nathan, Geoffrey Sanders, James Fairbanks, and David A. Bader. 2017. Graph ranking guarantees for numerical approximations to Katz centrality. In International Conference on Computational Science (ICCS\u201917), Vol. 108. Elsevier, 68--78. DOI:10.1016\/j.procs.2017.05.021"},{"key":"e_1_2_1_33_1","volume-title":"Mohammad Mehdi Daliri Khomami, and Mohammad Reza Meybodi","author":"Rezvanian Alireza","year":"2019","unstructured":"Alireza Rezvanian , Behnaz Moradabadi , Mina Ghavipour , Mohammad Mehdi Daliri Khomami, and Mohammad Reza Meybodi . 2019 . Social network sampling. In Learning Automata Approach for Social Networks. Springer , 91--149. Alireza Rezvanian, Behnaz Moradabadi, Mina Ghavipour, Mohammad Mehdi Daliri Khomami, and Mohammad Reza Meybodi. 2019. Social network sampling. In Learning Automata Approach for Social Networks. Springer, 91--149."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2012.6425857"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0423-0"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations","volume":"1","author":"Takac Lubos","year":"2012","unstructured":"Lubos Takac and Michal Zabovsky . 2012 . Data analysis in public social networks . In Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations , Vol. 1 . Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks. In Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations, Vol. 1."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms (ESA\u201918)","author":"van der Grinten Alexander","year":"2018","unstructured":"Alexander van der Grinten , Elisabetta Bergamini , Oded Green , David A. Bader , and Henning Meyerhenke . 2018 . Scalable Katz ranking computation in large static and dynamic graphs . In Proceedings of the 26th Annual European Symposium on Algorithms (ESA\u201918) . 42:1--42:14. Alexander van der Grinten, Elisabetta Bergamini, Oded Green, David A. Bader, and Henning Meyerhenke. 2018. Scalable Katz ranking computation in large static and dynamic graphs. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA\u201918). 42:1--42:14."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052665"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1142\/9789812773289_0004","article-title":"Fast approximation of centrality","volume":"5","author":"Joseph Wang David Eppstein","year":"2006","unstructured":"David Eppstein Joseph Wang . 2006 . Fast approximation of centrality . Graph Algorithms and Applications 5 , 5 (2006), 39 . David Eppstein Joseph Wang. 2006. Fast approximation of centrality. Graph Algorithms and Applications 5, 5 (2006), 39.","journal-title":"Graph Algorithms and Applications"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI\u201918)","author":"Was Tomasz","year":"2018","unstructured":"Tomasz Was and Oskar Skibski . 2018 . An axiomatization of the Eigenvector and Katz centralities . In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI\u201918) . Tomasz Was and Oskar Skibski. 2018. An axiomatization of the Eigenvector and Katz centralities. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI\u201918)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0024306"},{"key":"e_1_2_1_43_1","first-page":"1","article-title":"estimation and correction of bias in network simulations based on respondent-driven sampling data","volume":"10","author":"Zhu Lin","year":"2020","unstructured":"Lin Zhu , Nicolas A. Menzies , Jianing Wang , Benjamin P. Linas , Steven M. Goodreau , and Joshua A. Salomon . 2020 . estimation and correction of bias in network simulations based on respondent-driven sampling data . Scientific Reports 10 , 1 (2020), 1 -- 11 . Lin Zhu, Nicolas A. Menzies, Jianing Wang, Benjamin P. Linas, Steven M. Goodreau, and Joshua A. Salomon. 2020. estimation and correction of bias in network simulations based on respondent-driven sampling data. Scientific Reports 10, 1 (2020), 1--11.","journal-title":"Scientific Reports"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441646","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3441646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:30Z","timestamp":1750195470000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441646"}},"subtitle":["Estimating Katz Centrality Based on Sampling for Large-Scale Social Networks"],"short-title":[],"issued":{"date-parts":[[2021,4,18]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8,31]]}},"alternative-id":["10.1145\/3441646"],"URL":"https:\/\/doi.org\/10.1145\/3441646","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,18]]},"assertion":[{"value":"2020-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}