{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T22:37:13Z","timestamp":1740177433946,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T00:00:00Z","timestamp":1627603200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T00:00:00Z","timestamp":1627603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007051","name":"Uppsala University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007051","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2021,12]]},"abstract":"Abstract<\/jats:title>Sparsification is the process of decreasing the number of edges in a network while one or more topological properties are preserved. For probabilistic networks, sparsification has only been studied to preserve the expected degree of the nodes. In this work we introduce a sparsification method to preserve ego betweenness. Moreover, we study the effect of backboning and density on the resulting sparsified networks. Our experimental results show that the sparsification of high density networks can be used to efficiently and accurately estimate measures from the original network, with the choice of backboning algorithm only partially affecting the result.<\/jats:p>","DOI":"10.1007\/s41109-021-00401-7","type":"journal-article","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T12:06:49Z","timestamp":1627646809000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Probabilistic network sparsification with ego betweenness"],"prefix":"10.1007","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5797-1068","authenticated-orcid":false,"given":"Amin","family":"Kaveh","sequence":"first","affiliation":[]},{"given":"Matteo","family":"Magnani","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Rohner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,30]]},"reference":[{"key":"401_CR1","doi-asserted-by":"crossref","unstructured":"Bonchi F, Gullo F, Kaltenbrunner A, Volkovich Y (2014) Core decomposition of uncertain graphs. In: Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1316\u20131325","DOI":"10.1145\/2623330.2623655"},{"issue":"4","key":"401_CR2","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1145\/3186728.3164143","volume":"11","author":"M Ceccarello","year":"2017","unstructured":"Ceccarello M, Fantozzi C, Pietracaprina A, Pucci G, Vandin F (2017) Clustering uncertain graphs. Proc VLDB Endow 11(4):472\u2013484","journal-title":"Proc VLDB Endow"},{"key":"401_CR3","doi-asserted-by":"crossref","unstructured":"Coscia M, Neffke FM (2017) Network backboning with noisy data. In: 2017 IEEE 33rd international conference on data engineering (ICDE). IEEE, pp 425\u2013436","DOI":"10.1109\/ICDE.2017.100"},{"key":"401_CR4","doi-asserted-by":"crossref","unstructured":"Coscia M, Rossi L (2019) The impact of projection and backboning on network topologies. In: 2019 IEEE\/ACM international conference on advances in social networks analysis and mining (ASONAM). IEEE, pp 286\u2013293","DOI":"10.1145\/3341161.3342862"},{"issue":"6","key":"401_CR5","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1080\/1350486X.2015.1110492","volume":"22","author":"D-M Dang","year":"2015","unstructured":"Dang D-M, Jackson KR, Mohammadi M (2015) Dimension and variance reduction for Monte Carlo methods for high-dimensional models in finance. Appl Math Finance 22(6):522\u2013552","journal-title":"Appl Math Finance"},{"key":"401_CR6","doi-asserted-by":"crossref","unstructured":"De\u00a0Choudhury M, Mason WA, Hofman JM, Watts DJ (2010) Inferring relevant social networks from interpersonal communication. In: Proceedings of the 19th international conference on World Wide Web, pp 301\u2013310","DOI":"10.1145\/1772690.1772722"},{"issue":"1","key":"401_CR7","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.socnet.2004.11.007","volume":"27","author":"M Everett","year":"2005","unstructured":"Everett M, Borgatti SP (2005) Ego network betweenness. Soc Netw 27(1):31\u201338","journal-title":"Soc Netw"},{"issue":"3","key":"401_CR8","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0378-8733(78)90021-7","volume":"1","author":"LC Freeman","year":"1978","unstructured":"Freeman LC (1978) Centrality in social networks conceptual clarification. Soc Netw 1(3):215\u2013239","journal-title":"Soc Netw"},{"key":"401_CR9","doi-asserted-by":"crossref","unstructured":"Fushimi T, Saito K, Ikeda T, Kazama K (2018) A new group centrality measure for maximizing the connectedness of network under uncertain connectivity. In: International conference on complex networks and their applications. Springer, pp 3\u201314","DOI":"10.1007\/978-3-030-05411-3_1"},{"issue":"6","key":"401_CR10","doi-asserted-by":"publisher","first-page":"667","DOI":"10.14778\/3311880.3311884","volume":"12","author":"K Han","year":"2019","unstructured":"Han K, Gui F, Xiao X, Tang J, He Y, Cao Z, Huang H (2019) Efficient and effective algorithms for clustering uncertain graphs. Proc VLDB Endow 12(6):667\u2013680","journal-title":"Proc VLDB Endow"},{"issue":"9","key":"401_CR11","doi-asserted-by":"publisher","first-page":"551","DOI":"10.14778\/2002938.2002941","volume":"4","author":"R Jin","year":"2011","unstructured":"Jin R, Liu L, Ding B, Wang H (2011) Distance-constraint reachability computation in uncertain graphs. Proc VLDB Endow 4(9):551\u2013562","journal-title":"Proc VLDB Endow"},{"issue":"5","key":"401_CR12","first-page":"263","volume":"1","author":"H Kahn","year":"1953","unstructured":"Kahn H, Marshall AW (1953) Methods of reducing sample size in Monte Carlo computations. J Oper Res Soc Am 1(5):263\u2013278","journal-title":"J Oper Res Soc Am"},{"issue":"1","key":"401_CR13","first-page":"1","volume":"11","author":"A Kaveh","year":"2020","unstructured":"Kaveh A, Magnani M, Rohner C (2020) Defining and measuring probabilistic ego networks. Soc Netw Anal Min 11(1):1\u201312","journal-title":"Soc Netw Anal Min"},{"issue":"8","key":"401_CR14","doi-asserted-by":"publisher","first-page":"864","DOI":"10.14778\/3324301.3324304","volume":"12","author":"X Ke","year":"2019","unstructured":"Ke X, Khan A, Quan LLH (2019) An in-depth comparison of st reliability algorithms over uncertain graphs. Proc VLDB Endow 12(8):864\u2013876","journal-title":"Proc VLDB Endow"},{"issue":"2","key":"401_CR15","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1109\/TKDE.2011.243","volume":"25","author":"G Kollios","year":"2011","unstructured":"Kollios G, Potamias M, Terzi E (2011) Clustering large probabilistic graphs. IEEE Trans Knowl Data Eng 25(2):325\u2013336","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"401_CR16","doi-asserted-by":"crossref","unstructured":"Lee VE, Ruan N, Jin R, Aggarwal C (2010) A survey of algorithms for dense subgraph discovery. In: Managing and mining graph data. Springer, Boston, pp 303\u2013336","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"401_CR17","doi-asserted-by":"crossref","unstructured":"Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the eleventh ACM SIGKDD international conference on knowledge discovery in data mining, pp 177\u2013187","DOI":"10.1145\/1081870.1081893"},{"issue":"2","key":"401_CR18","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1109\/TKDE.2015.2485212","volume":"28","author":"R-H Li","year":"2015","unstructured":"Li R-H, Yu JX, Mao R, Jin T (2015) Recursive stratified sampling: a new framework for query evaluation on uncertain graphs. IEEE Trans Knowl Data Eng 28(2):468\u2013482","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"401_CR19","doi-asserted-by":"crossref","unstructured":"Magnani M, Montesi D, Rossi L (2010) Friendfeed breaking news: death of a public figure. In: 2010 IEEE second international conference on social computing. IEEE, pp 528\u2013533","DOI":"10.1109\/SocialCom.2010.83"},{"issue":"2","key":"401_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3044713","volume":"42","author":"S Maniu","year":"2017","unstructured":"Maniu S, Cheng R, Senellart P (2017) An indexing framework for queries on probabilistic graphs. ACM Trans Database Syst 42(2):1\u201334","journal-title":"ACM Trans Database Syst"},{"issue":"3\u20134","key":"401_CR21","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/S0378-4371(00)00311-3","volume":"285","author":"M Marchiori","year":"2000","unstructured":"Marchiori M, Latora V (2000) Harmony in the small-world. Phys A Stat Mech Appl 285(3\u20134):539\u2013546","journal-title":"Phys A Stat Mech Appl"},{"issue":"1\u20136","key":"401_CR22","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi H, Ibaraki T (1992) A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph. Algorithmica 7(1\u20136):583\u2013596","journal-title":"Algorithmica"},{"issue":"12","key":"401_CR23","doi-asserted-by":"publisher","first-page":"2435","DOI":"10.1109\/TKDE.2018.2819651","volume":"30","author":"P Parchas","year":"2018","unstructured":"Parchas P, Papailiou N, Papadias D, Bonchi F (2018) Uncertain graph sparsification. IEEE Trans Knowl Data Eng 30(12):2435\u20132449","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"401_CR24","unstructured":"Pfeiffer JJ III, Neville J (2011) Methods to determine node centrality and clustering in graphs with uncertain structure. In: ICWSM"},{"issue":"1\u20132","key":"401_CR25","doi-asserted-by":"publisher","first-page":"997","DOI":"10.14778\/1920841.1920967","volume":"3","author":"M Potamias","year":"2010","unstructured":"Potamias M, Bonchi F, Gionis A, Kollios G (2010) K-nearest neighbors in uncertain graphs. Proc VLDB Endow 3(1\u20132):997\u20131008","journal-title":"Proc VLDB Endow"},{"issue":"2","key":"401_CR26","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1023\/A:1026543900054","volume":"40","author":"Y Rubner","year":"2000","unstructured":"Rubner Y, Tomasi C, Guibas LJ (2000) The earth mover\u2019s distance as a metric for image retrieval. Int J Comput Vis 40(2):99\u2013121","journal-title":"Int J Comput Vis"},{"key":"401_CR27","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.neuroimage.2016.05.062","volume":"142","author":"M Termenon","year":"2016","unstructured":"Termenon M, Jaillard A, Delon-Martin C, Achard S (2016) Reliability of graph analysis of resting state FMRI using test-retest dataset from the human connectome project. Neuroimage 142:172\u2013187","journal-title":"Neuroimage"},{"issue":"1","key":"401_CR28","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1006\/nimg.2001.0978","volume":"15","author":"N Tzourio-Mazoyer","year":"2002","unstructured":"Tzourio-Mazoyer N, Landeau B, Papathanassiou D, Crivello F, Etard O, Delcroix N, Mazoyer B, Joliot M (2002) Automated anatomical labeling of activations in SPM using a macroscopic anatomical parcellation of the MNI MRI single-subject brain. Neuroimage 15(1):273\u2013289","journal-title":"Neuroimage"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00401-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-021-00401-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00401-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T12:47:47Z","timestamp":1627649267000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-021-00401-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,30]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["401"],"URL":"https:\/\/doi.org\/10.1007\/s41109-021-00401-7","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2021,7,30]]},"assertion":[{"value":"17 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"58"}}