{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T17:51:37Z","timestamp":1740160297586,"version":"3.37.3"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T00:00:00Z","timestamp":1528848000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T00:00:00Z","timestamp":1528848000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000005","name":"U.S. Department of Defense","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s13278-018-0520-3","type":"journal-article","created":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T01:17:12Z","timestamp":1528852632000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Estimating degree rank in complex networks"],"prefix":"10.1007","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7151-6309","authenticated-orcid":false,"given":"Akrati","family":"Saxena","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralucca","family":"Gera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. R. S.","family":"Iyengar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,13]]},"reference":[{"key":"520_CR1","doi-asserted-by":"crossref","unstructured":"Backstrom L, Leskovec J (2011) Supervised random walks: predicting and recommending links in social networks. In: Proceedings of the fourth ACM international conference on Web search and data mining, ACM, pp 635\u2013644","DOI":"10.1145\/1935826.1935914"},{"issue":"5439","key":"520_CR2","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509\u2013512","journal-title":"Science"},{"key":"520_CR3","doi-asserted-by":"crossref","unstructured":"Boldi P, Vigna S (2004) The WebGraph framework I: Compression techniques. In: Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), ACM Press, Manhattan, USA, pp 595\u2013601","DOI":"10.1145\/988672.988752"},{"key":"520_CR4","unstructured":"Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. In: Seventh international world-wide web conference (www 1998), april 14-18, 1998, brisbane, australia. Brisbane, Australia"},{"key":"520_CR5","doi-asserted-by":"crossref","unstructured":"Cem E, Sarac K (2015) Estimating the size and average degree of online social networks at the extreme. In: Communications (ICC), 2015 IEEE International Conference on, IEEE, pp 1268\u20131273","DOI":"10.1109\/ICC.2015.7248497"},{"key":"520_CR6","doi-asserted-by":"crossref","unstructured":"Cem E, Sarac K (2016a) Average degree estimation under ego-centric sampling design. In: Computer Communications Workshops (INFOCOM WKSHPS), 2016 IEEE Conference on, IEEE, pp 152\u2013157","DOI":"10.1109\/INFCOMW.2016.7562063"},{"key":"520_CR7","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.comnet.2016.09.003","volume":"108","author":"E Cem","year":"2016","unstructured":"Cem E, Sarac K (2016b) Estimation of structural properties of online social networks at the extreme. Comput Netw 108:323\u2013344","journal-title":"Comput Netw"},{"issue":"4","key":"520_CR8","doi-asserted-by":"publisher","first-page":"1777","DOI":"10.1016\/j.physa.2011.09.017","volume":"391","author":"D Chen","year":"2012","unstructured":"Chen D, L\u00fc L, Shang MS, Zhang YC, Zhou T (2012) Identifying influential nodes in complex networks. Physica Stat Mech Appl 391(4):1777\u20131787","journal-title":"Physica Stat Mech Appl"},{"key":"520_CR9","unstructured":"Chen L, Karbasi A, Crawford FW (2016) Estimating the size of a large network and its communities from a random sample. In: Advances in Neural Information Processing Systems, pp 3072\u20133080"},{"key":"520_CR10","doi-asserted-by":"crossref","unstructured":"Cho E, Myers SA, Leskovec J (2011) Friendship and mobility: user movement in location-based social networks. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 1082\u20131090","DOI":"10.1145\/2020408.2020579"},{"key":"520_CR11","doi-asserted-by":"crossref","unstructured":"Cooper C, Radzik T, Siantos Y (2012) A fast algorithm to find all high degree vertices in power law graphs. In: Proceedings of the 21st International Conference on World Wide Web, ACM, pp 1007\u20131016","DOI":"10.1145\/2187980.2188235"},{"key":"520_CR12","doi-asserted-by":"crossref","unstructured":"Dasgupta A, Kumar R, Sarlos T (2014) On estimating the average degree. In: Proceedings of the 23rd international conference on World wide web, ACM, pp 795\u2013806","DOI":"10.1145\/2566486.2568019"},{"key":"520_CR13","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-319-30569-1_7","volume-title":"Complex networks VII","author":"B Davis","year":"2016","unstructured":"Davis B, Gera R, Lazzaro G, Lim BY, Rye EC (2016) The marginal benefit of monitor placement on networks. In: Cherifi H, Gon\u00e7alves B, Menezes R, Sinatra R (eds) Complex networks VII, Springer, Cham, pp 93\u2013104"},{"key":"520_CR14","doi-asserted-by":"crossref","unstructured":"De\u00a0Choudhury M, Sundaram H, John A, Seligmann DD (2009) Social synchrony: Predicting mimicry of user actions in online social media. In: Computational Science and Engineering, 2009. CSE\u201909. International Conference on, IEEE, vol\u00a04, pp 151\u2013158","DOI":"10.1109\/CSE.2009.439"},{"key":"520_CR15","unstructured":"Eden T, Ron D, Seshadhri C (2016) Sublinear time estimation of degree distribution moments: The arboricity connection. arXiv preprint arXiv:160403661"},{"key":"520_CR16","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s P, R\u00e9nyi A (1960) On the evolution of random graphs. Publ Math Inst Hungar Acad Sci 5:17\u201361","journal-title":"Publ Math Inst Hungar Acad Sci"},{"key":"520_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139015165","volume-title":"Graph algorithms","author":"S Even","year":"2011","unstructured":"Even S (2011) Graph algorithms. Cambridge University Press, Cambridge"},{"key":"520_CR18","doi-asserted-by":"crossref","unstructured":"Fire M, Tenenboim L, Lesser O, Puzis R, Rokach L, Elovici Y (2011) Link prediction in social networks using computationally efficient topological features. In: Privacy, security, risk and trust (PASSAT) and IEEE third international confernece on social computing (SocialCom), IEEE, pp 73\u201380","DOI":"10.1109\/PASSAT\/SocialCom.2011.20"},{"key":"520_CR19","first-page":"59","volume-title":"International workshop on algorithms and models for the web-graph","author":"S Fortunato","year":"2006","unstructured":"Fortunato S, Bogu\u00f1\u00e1 M, Flammini A, Menczer F (2006) Approximating pagerank from in-degree. In: Aiello W, Broder A, Janssen J, Milios E (eds) International workshop on algorithms and models for the web-graph. Springer, Berlin, Heidelberg, pp 59\u201371"},{"issue":"1","key":"520_CR20","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/3033543","volume":"40","author":"LC Freeman","year":"1977","unstructured":"Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry 40(1):35\u201341","journal-title":"Sociometry"},{"key":"520_CR21","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1038\/ncomms1396","volume":"2","author":"G Ghoshal","year":"2011","unstructured":"Ghoshal G, Barab\u00e1si AL (2011) Ranking stability and super-stable nodes in complex networks. Nat Commun 2:394","journal-title":"Nat Commun"},{"key":"520_CR22","doi-asserted-by":"crossref","unstructured":"Gjoka M, Kurant M, Butts CT, Markopoulou A (2010) Walking in Facebook: A case study of unbiased sampling of OSNs. In: INFOCOM, 2010 Proceedings IEEE, IEEE, pp 1\u20139","DOI":"10.1109\/INFCOM.2010.5462078"},{"issue":"1","key":"520_CR23","first-page":"148","volume":"32","author":"LA Goodman","year":"1961","unstructured":"Goodman LA (1961) Snowball sampling. Ann Math Stat 32(1):148\u2013170","journal-title":"Stat"},{"issue":"4","key":"520_CR24","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1214\/aoms\/1177731356","volume":"14","author":"MH Hansen","year":"1943","unstructured":"Hansen MH, Hurwitz WN (1943) On the theory of sampling from finite populations. Ann Math Stat 14(4):333\u2013362","journal-title":"Ann Math Stat"},{"key":"520_CR25","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.jnca.2013.10.016","volume":"41","author":"G Haralabopoulos","year":"2014","unstructured":"Haralabopoulos G, Anagnostopoulos I (2014) Real time enhanced random sampling of online social networks. J Netw Comput Appl 41:126\u2013134","journal-title":"J Netw Comput Appl"},{"key":"520_CR26","unstructured":"Hardiman SJ, Katzir L (2013) Estimating clustering coefficients and size of social networks via random walk. In: Proceedings of the 22nd international conference on World Wide Web, International World Wide Web Conferences Steering Committee, pp 539\u2013550"},{"issue":"1","key":"520_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1140\/epjds5","volume":"1","author":"T Hogg","year":"2012","unstructured":"Hogg T, Lerman K (2012) Social dynamics of digg. EPJ Data Sci 1(1):1\u201326","journal-title":"EPJ Data Sci"},{"issue":"15","key":"520_CR28","doi-asserted-by":"publisher","first-page":"4012","DOI":"10.1016\/j.physa.2012.02.033","volume":"391","author":"B Hou","year":"2012","unstructured":"Hou B, Yao Y, Liao D (2012) Identifying all-around nodes for spreading dynamics in complex networks. Phys A Stat Mech Appl 391(15):4012\u20134017","journal-title":"Phys A Stat Mech Appl"},{"issue":"1","key":"520_CR29","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF02289026","volume":"18","author":"L Katz","year":"1953","unstructured":"Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39\u201343","journal-title":"Psychometrika"},{"key":"520_CR30","doi-asserted-by":"crossref","unstructured":"Konstas I, Stathopoulos V, Jose JM (2009) On social networks and collaborative recommendation. In: Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, ACM, pp 195\u2013202","DOI":"10.1145\/1571941.1571977"},{"key":"520_CR31","unstructured":"Kurant M, Butts CT, Markopoulou A (2012) Graph size estimation. arXiv preprint arXiv:12100460"},{"key":"520_CR32","doi-asserted-by":"crossref","unstructured":"Leskovec J, Faloutsos C (2006) Sampling from large graphs. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 631\u2013636","DOI":"10.1145\/1150402.1150479"},{"issue":"1","key":"520_CR33","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1217299.1217301","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data (TKDD) 1(1):2","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"issue":"1","key":"520_CR34","first-page":"1","volume":"2","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz L (1993) Random walks on graphs: A survey. Comb Paul erdos is eighty 2(1):1\u201346","journal-title":"Comb Paul erdos is eighty"},{"key":"520_CR35","doi-asserted-by":"crossref","unstructured":"Lu J, Li D (2012) Sampling online social networks by random walk. In: Proceedings of the First ACM International Workshop on Hot Topics on Interdisciplinary Social Networks Research, ACM, pp 33\u201340","DOI":"10.1145\/2392622.2392628"},{"key":"520_CR36","doi-asserted-by":"crossref","unstructured":"Lucchese R, Varagnolo D (2015) Networks cardinality estimation using order statistics. In: American Control Conference (ACC), 2015, IEEE, pp 3810\u20133817","DOI":"10.1109\/ACC.2015.7171924"},{"key":"520_CR37","unstructured":"Marchetti-Spaccamela A (1988) On the estimate of the size of a directed graph. In: International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, pp 317\u2013326"},{"key":"520_CR38","unstructured":"McAuley JJ, Leskovec J (2012) Learning to discover social circles in ego networks. NIPS 2012:548\u201356"},{"issue":"6","key":"520_CR39","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087\u20131092","journal-title":"J Chem Phys"},{"key":"520_CR40","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BFb0067700","volume-title":"Numerical analysis","author":"JJ Mor\u00e9","year":"1978","unstructured":"Mor\u00e9 JJ (1978) The levenberg-marquardt algorithm: implementation and theory. In: Watson GA (ed) Numerical analysis. Springer, Berlin, Heidelberg, pp 105\u2013116"},{"key":"520_CR41","doi-asserted-by":"crossref","unstructured":"Musco C, Su HH, Lynch N (2016) Ant-inspired density estimation via random walks. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, ACM, pp 469\u2013478","DOI":"10.1145\/2933057.2933106"},{"issue":"6","key":"520_CR42","doi-asserted-by":"publisher","first-page":"678","DOI":"10.14778\/2735703.2735707","volume":"8","author":"A Nazi","year":"2015","unstructured":"Nazi A, Zhou Z, Thirumuruganathan S, Zhang N, Das G (2015) Walk, not wait: faster sampling over online social networks. Proc VLDB Endow 8(6):678\u2013689","journal-title":"Proc VLDB Endow"},{"key":"520_CR43","doi-asserted-by":"crossref","unstructured":"Ribeiro B, Towsley D (2010) Estimating and sampling graphs with multidimensional random walks. In: Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, ACM, pp 390\u2013403","DOI":"10.1145\/1879141.1879192"},{"key":"520_CR44","doi-asserted-by":"crossref","unstructured":"Ribeiro B, Towsley D (2012) On the estimation accuracy of degree distributions from graph sampling. In: Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, IEEE, pp 5240\u20135247","DOI":"10.1109\/CDC.2012.6425857"},{"key":"520_CR45","doi-asserted-by":"crossref","unstructured":"Ribeiro B, Wang P, Murai F, Towsley D (2012) Sampling directed graphs with random walks. In: INFOCOM, 2012 Proceedings IEEE, IEEE, pp 1692\u20131700","DOI":"10.1109\/INFCOM.2012.6195540"},{"key":"520_CR46","doi-asserted-by":"crossref","unstructured":"Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, http:\/\/networkrepository.com","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"4","key":"520_CR47","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/BF02289527","volume":"31","author":"G Sabidussi","year":"1966","unstructured":"Sabidussi G (1966) The centrality index of a graph. Psychometrika 31(4):581\u2013603","journal-title":"Psychometrika"},{"issue":"1","key":"520_CR48","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1111\/j.0081-1750.2004.00152.x","volume":"34","author":"MJ Salganik","year":"2004","unstructured":"Salganik MJ, Heckathorn DD (2004) Sampling and estimation in hidden populations using respondent-driven sampling. Sociol Methodol 34(1):193\u2013240","journal-title":"Sociol Methodol"},{"key":"520_CR49","doi-asserted-by":"crossref","unstructured":"Saxena A, Gera R, Iyengar S (2017) Observe locally rank globally. In: Proceedings of the 2017 IEEE\/ACM international conference on advances in social networks analysis and mining. ACM, pp 139\u2013144","DOI":"10.1145\/3110025.3110063"},{"issue":"4","key":"520_CR50","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1037\/h0053638","volume":"49","author":"ME Shaw","year":"1954","unstructured":"Shaw ME (1954) Some effects of unequal distribution of information upon group performance in various communication nets. J Abnorm Soc Psychol 49(4):547\u2013553","journal-title":"J Abnorm Soc Psychol"},{"issue":"1","key":"520_CR51","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0378-8733(89)90016-6","volume":"11","author":"K Stephenson","year":"1989","unstructured":"Stephenson K, Zelen M (1989) Rethinking centrality: methods and examples. Soc Net 11(1):1\u201337","journal-title":"Soc Net"},{"issue":"16","key":"520_CR52","doi-asserted-by":"publisher","first-page":"4165","DOI":"10.1016\/j.physa.2011.12.021","volume":"391","author":"AL Traud","year":"2012","unstructured":"Traud AL, Mucha PJ, Porter MA (2012) Social structure of Facebook networks. Phys A 391(16):4165\u20134180","journal-title":"Phys A"},{"key":"520_CR53","doi-asserted-by":"crossref","unstructured":"Voudigari E, Salamanos N, Papageorgiou T, Yannakoudakis EJ (2016) Rank degree: An efficient algorithm for graph sampling. In: Advances in Social Networks Analysis and Mining (ASONAM), 2016 IEEE\/ACM International Conference on, IEEE, pp 120\u2013129","DOI":"10.1109\/ASONAM.2016.7752223"},{"issue":"1","key":"520_CR54","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10115-013-0693-z","volume":"42","author":"J Yang","year":"2015","unstructured":"Yang J, Leskovec J (2015) Defining and evaluating network communities based on ground-truth. Knowl Inf Syst 42(1):181\u2013213","journal-title":"Knowl Inf Syst"},{"issue":"2","key":"520_CR55","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1504\/IJSCCPS.2011.044172","volume":"1","author":"S Ye","year":"2011","unstructured":"Ye S, Wu SF (2011) Estimating the size of online social networks. Int J Soc Comput Cyber Phys Syst 1(2):160\u2013179","journal-title":"Int J Soc Comput Cyber Phys Syst"},{"issue":"3","key":"520_CR56","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.12733\/jics20105640","volume":"12","author":"Y Yu","year":"2015","unstructured":"Yu Y, Fan S (2015) Node importance measurement based on the degree and closeness centrality. J Inf Commput Sci 12(3):1281\u20131291","journal-title":"J Inf Commput Sci"},{"key":"520_CR57","unstructured":"Zafarani R, Liu H (2009) Social computing data repository at ASU. http:\/\/socialcomputing.asu.edu . Accessed Jan 2017"},{"issue":"4","key":"520_CR59","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/2847526","volume":"40","author":"Z Zhou","year":"2016","unstructured":"Zhou Z, Zhang N, Gong Z, Das G (2016) Faster random walks by rewiring online social networks on-the-fly. ACM Trans Database Syst (TODS) 40(4):26","journal-title":"ACM Trans Database Syst (TODS)"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13278-018-0520-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-018-0520-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-018-0520-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T16:00:34Z","timestamp":1661443234000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s13278-018-0520-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,13]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["520"],"URL":"https:\/\/doi.org\/10.1007\/s13278-018-0520-3","relation":{},"ISSN":["1869-5450","1869-5469"],"issn-type":[{"type":"print","value":"1869-5450"},{"type":"electronic","value":"1869-5469"}],"subject":[],"published":{"date-parts":[[2018,6,13]]},"assertion":[{"value":"21 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"42"}}