{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T19:19:20Z","timestamp":1648927160210},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Betweenness centrality of a vertex in a graph measures the fraction of shortest paths going through the vertex. This is a basic notion for determining the importance of a vertex in a network. The $k$-betweenness centrality of a vertex is defined similarly, but only considers shortest paths of length at most $k$. The sequence of $k$-betweenness centralities for all possible values of $k$ forms the betweenness centrality profile of a vertex. We study properties of betweenness centrality profiles in trees.<\/jats:p>\n               <jats:p>We show that for scale-free random trees, for fixed $k$, the expectation of $k$-betweenness centrality strictly decreases as the index of the vertex increases. We also analyse worst-case properties of profiles in terms of the distance of profiles from being monotone, and the number of times pairs of profiles can cross. This is related to whether $k$-betweenness centrality, for small values of $k$, may be used instead of having to consider all shortest paths. Bounds are given that are optimal in order of magnitude. We also present some experimental results for scale-free random trees.<\/jats:p>","DOI":"10.1093\/comnet\/cnx007","type":"journal-article","created":{"date-parts":[[2017,4,7]],"date-time":"2017-04-07T11:08:24Z","timestamp":1491563304000},"page":"776-794","source":"Crossref","is-referenced-by-count":0,"title":["Betweenness centrality profiles in trees"],"prefix":"10.1093","volume":"5","author":[{"given":"Benjamin","family":"Fish","sequence":"first","affiliation":[{"name":"Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 851 S. Morgan St., Chicago, IL 60607, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Kushwaha","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, 851 S. Morgan St., Chicago, IL 60607, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, IL 60607, USA and"},{"name":"MTA-SZTE Research Group on Artificial Intelligence, Szeged, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2017,5,3]]},"reference":[{"key":"2020021403392012200_B1","doi-asserted-by":"crossref","first-page":"16","DOI":"10.17730\/humo.7.3.f4033344851gl053","article-title":"A mathematical model for group structures","volume":"7","author":"Bavelas","year":"1948","journal-title":"Human Organ."},{"key":"2020021403392012200_B2","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1016\/j.socnet.2005.11.005","article-title":"A graph-theoretic perspective on centrality","volume":"28","author":"Borgatti","year":"2006","journal-title":"Social Networks"},{"key":"2020021403392012200_B3","doi-asserted-by":"crossref","DOI":"10.1007\/b106453","volume-title":"Network Analysis: Methodological Foundations","author":"Brandes","year":"2005"},{"key":"2020021403392012200_B4","first-page":"1","author":"Anthonisse","year":"1971","journal-title":"The Rush in a Directed Graph"},{"key":"2020021403392012200_B5","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/3033543","article-title":"A set of measures of centrality based on betweenness","author":"Freeman","year":"1977","journal-title":"Sociometry"},{"key":"2020021403392012200_B6","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0378-8733(78)90025-4","article-title":"The medieval river trade network of Russia revisited","volume":"1","author":"Pitts","year":"1979","journal-title":"Social Networks"},{"key":"2020021403392012200_B7","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","article-title":"A faster algorithm for betweenness centrality","volume":"25","author":"Brandes","year":"2001","journal-title":"J. Math. Sociol."},{"key":"2020021403392012200_B8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.7155\/jgaa.00081","article-title":"Fast approximation of centrality","volume":"8","author":"Eppstein","year":"2004","journal-title":"J. of Graph Algori. Appl."},{"key":"2020021403392012200_B9","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1145\/2556195.2556224","article-title":"Fast approximation of betweenness centrality through sampling","volume-title":"Proceedings of the 7th ACM International Conference on Web Search and Data Mining","author":"Riondato","year":"2014"},{"key":"2020021403392012200_B10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0012-365X(73)90035-6","article-title":"Theory of Path Length Distributions I","volume":"6","author":"Faudree","year":"1973","journal-title":"Discrete Math."},{"key":"2020021403392012200_B11","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1002\/jgt.3190150308","article-title":"Tutte polynomials for trees","volume":"15","author":"Chaudhary","year":"1991","journal-title":"J. Graph Theory"},{"key":"2020021403392012200_B12","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0012-365X(94)00278-Q","article-title":"Trees with the same degree sequence and path numbers","volume":"147","author":"Gordon","year":"1995","journal-title":"Discrete Math."},{"key":"2020021403392012200_B13","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1016\/j.dam.2011.02.010","article-title":"On the distance distribution of trees","volume":"159","author":"Dankelmann","year":"2011","journal-title":"Discrete Appl. Math."},{"key":"2020021403392012200_B14","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1145\/2187980.2188239","article-title":"k-Centralities: Local approximations of global measures based on shortest paths","volume-title":"Proceedings of the 21st International Conference Companion on World Wide Web","author":"Pfeffer","year":"2012"},{"key":"2020021403392012200_B15","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barab\u00e1si","year":"1999","journal-title":"Science"},{"key":"2020021403392012200_B16","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0377-0427(92)90252-S","article-title":"Distances in random plane-oriented recursive trees","volume":"41","author":"Mahmoud","year":"1992","journal-title":"J. Comput. Appl. Math."},{"key":"2020021403392012200_B17","first-page":"1","article-title":"A survey of recursive trees","volume":"51","author":"Smythe","year":"1995","journal-title":"Theory Probab. Math. Stat."},{"key":"2020021403392012200_B18","doi-asserted-by":"crossref","first-page":"036114","DOI":"10.1103\/PhysRevE.69.036114","article-title":"Shortest paths and load scaling in scale-free trees","volume":"69","author":"Bollob\u00e1s","year":"2004","journal-title":"Phys. Rev. E"},{"key":"2020021403392012200_B19","doi-asserted-by":"crossref","first-page":"026101","DOI":"10.1103\/PhysRevE.66.026101","article-title":"Shortest paths and load scaling in scale-free trees","volume":"66","author":"Szab\u00f3","year":"2002","journal-title":"Phys. Rev. E"},{"key":"2020021403392012200_B20","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/TNSE.2015.2397592","article-title":"On the influence of the seed graph in the preferential attachment model","volume":"2","author":"Bubeck","year":"2014","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"2020021403392012200_B21","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1002\/rsa.20649","article-title":"Finding Adam in random growing trees","volume":"50","author":"Bubeck","year":"2014","journal-title":"Random Struct. & Algor."},{"key":"2020021403392012200_B22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TNSE.2016.2622923","article-title":"Analysis of centrality in sublinear preferential attachment trees via the Crump-Mode-Jagers branching process","volume":"4","author":"Jog","year":"2017","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"2020021403392012200_B23","first-page":"1","article-title":"Mathematical results on scale-free random graphs","volume-title":"Handbook of Graphs and Networks: From the Genome to the Internet","author":"Bollob\u00e1s","year":"2003"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/5\/5\/776\/20506303\/cnx007.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/5\/5\/776\/20506303\/cnx007.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T08:39:36Z","timestamp":1581669576000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/5\/5\/776\/3792105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,3]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnx007","relation":{},"ISSN":["2051-1310","2051-1329"],"issn-type":[{"value":"2051-1310","type":"print"},{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2017,10]]},"published":{"date-parts":[[2017,5,3]]}}}