{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T17:40:41Z","timestamp":1662831641703},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2019,2,23]],"date-time":"2019-02-23T00:00:00Z","timestamp":1550880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Degree is a fundamental property of nodes in networks. However, computing the degree distribution of nodes in probabilistic networks is an expensive task for large networks. To overcome this difficulty, expected degree is commonly utilized in the literature. However, in this article, we show that in some cases expected degree does not allow us to evaluate the probability of two nodes having the same degree or one node having higher degree than another. This suggests that expected degree in probabilistic networks does not completely play the same role as degree in deterministic networks. For each node, we define a reference node with the same expected degree but the least possible variance, corresponding to the least uncertain degree distribution. Then, we show how the probability of a node\u2019s degree being higher or equal to the degree of its reference node can be approximated by using variance and skewness of the degree distribution in addition to expected degree. Experimental results on a real dataset show that our approximation functions produce accurate probability estimations in linear computational complexity, while computing exact probabilities is polynomial with order of 3.<\/jats:p>","DOI":"10.1093\/comnet\/cnz003","type":"journal-article","created":{"date-parts":[[2019,1,18]],"date-time":"2019-01-18T20:17:38Z","timestamp":1547842658000},"page":"749-763","source":"Crossref","is-referenced-by-count":1,"title":["Comparing node degrees in probabilistic networks"],"prefix":"10.1093","volume":"7","author":[{"given":"Amin","family":"Kaveh","sequence":"first","affiliation":[{"name":"InfoLab, Department of Information Technology, Uppsala University, L\u00e4gerhyddsv\u00e4gen 7, House 19, SE-752 37, 75105 Uppsala, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matteo","family":"Magnani","sequence":"additional","affiliation":[{"name":"InfoLab, Department of Information Technology, Uppsala University, L\u00e4gerhyddsv\u00e4gen 7, House 19, SE-752 37, 75105 Uppsala, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Rohner","sequence":"additional","affiliation":[{"name":"InfoLab, Department of Information Technology, Uppsala University, L\u00e4gerhyddsv\u00e4gen 7, House 19, SE-752 37, 75105 Uppsala, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,2,23]]},"reference":[{"key":"2019101609185367900_B1","first-page":"107","article-title":"The anatomy of a large-scale hypertextual web search engine","volume-title":"Comput. Netw. ISDN Syst.","author":"Brin,","year":"1998"},{"key":"2019101609185367900_B2","doi-asserted-by":"crossref","first-page":"12200","DOI":"10.1371\/journal.pone.0012200","article-title":"A new measure of centrality for brain networks","volume":"5","author":"Joyce,","year":"2010","journal-title":"PLoS One"},{"key":"2019101609185367900_B3","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1140\/epjb\/e2015-50671-y","article-title":"Correlation between centrality metrics and their application to the opinion model","volume":"88","author":"Li,","year":"2015","journal-title":"Eur. Phys. J. B"},{"key":"2019101609185367900_B4","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","article-title":"Modularity and community structure in networks","volume":"103","author":"Newman,","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2019101609185367900_B5","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of large-scale data sets of protein\u2013protein interactions","volume":"417","author":"Von Mering,","year":"2002","journal-title":"Nature"},{"key":"2019101609185367900_B6","doi-asserted-by":"crossref","first-page":"4569","DOI":"10.1073\/pnas.061034498","article-title":"A comprehensive two-hybrid analysis to explore the yeast protein interactome","volume":"98","author":"Ito,","year":"2001","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2019101609185367900_B7","doi-asserted-by":"crossref","first-page":"1851","DOI":"10.1145\/2806416.2806619","article-title":"Top-k reliable edge colors in uncertain graphs","volume-title":"Proceedings of the 24th ACM International on Conference on Information and Knowledge Management","author":"Khan,","year":"2015"},{"key":"2019101609185367900_B8","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-1-4419-6045-0_2","volume-title":"Graph data management and mining: A survey of algorithms and applications. Managing and mining graph data","author":"Aggarwal,","year":"2010"},{"key":"2019101609185367900_B9","doi-asserted-by":"crossref","first-page":"269","DOI":"10.17730\/humo.35.3.10215j2m359266n2","article-title":"Informant accuracy in social network data","volume":"35","author":"Killworth,","year":"1976","journal-title":"Hum. Organ."},{"key":"2019101609185367900_B10","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1111\/2041-210X.12468","article-title":"The structure of probabilistic networks","volume":"7","author":"Poisot,","year":"2016","journal-title":"Methods Ecol. Evol."},{"key":"2019101609185367900_B11","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1145\/2588555.2593668","article-title":"The pursuit of a good possible world: extracting representative instances of uncertain graphs","volume-title":"Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data","author":"Parchas,","year":"2014"},{"key":"2019101609185367900_B12","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/2818182","article-title":"Uncertain graph processing through representative instances","volume":"40","author":"Parchas,","year":"2015","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"2019101609185367900_B13","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/978-3-642-38562-9_55","article-title":"Probabilistic graph summarization","volume-title":"International Conference on Web-Age Information Management","author":"Hassanlou,","year":"2013"},{"key":"2019101609185367900_B14","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1109\/TAES.2010.5461658","article-title":"Closed-form expression for the Poisson-binomial probability density function","volume":"46","author":"Fern\u00e1ndez,","year":"2010","journal-title":"IEEE Trans. Aerosp. Electron. Syst."},{"key":"2019101609185367900_B15","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/S0019-9958(59)90082-8","article-title":"Entropy and the uncertainty principle","volume":"2","author":"Leipnik,","year":"1959","journal-title":"Inform. Control"},{"key":"2019101609185367900_B16","doi-asserted-by":"crossref","first-page":"065004","DOI":"10.1088\/1751-8113\/41\/6\/065004","article-title":"Probability distribution and entropy as a measure of uncertainty","volume":"41","author":"Wang,","year":"2008","journal-title":"J. Phys. A"},{"key":"2019101609185367900_B17","doi-asserted-by":"crossref","first-page":"2039","DOI":"10.1109\/18.930936","article-title":"Binomial and Poisson distributions as maximum entropy distributions","volume":"47","author":"Harremo\u00ebs,","year":"2001","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2019101609185367900_B18","doi-asserted-by":"crossref","first-page":"997","DOI":"10.14778\/1920841.1920967","article-title":"K-nearest neighbors in uncertain graphs","volume":"3","author":"Potamias,","year":"2010","journal-title":"Proc. VLDB Endow."},{"key":"2019101609185367900_B19","first-page":"295","article-title":"On the number of successes in independent trials","volume":"3","author":"Wang,","year":"1993","journal-title":"Stat. Sin."},{"key":"2019101609185367900_B20","doi-asserted-by":"crossref","first-page":"551","DOI":"10.14778\/2002938.2002941","article-title":"Distance-constraint reachability computation in uncertain graphs","volume":"4","author":"Jin,","year":"2011","journal-title":"Proc. VLDB Endow."},{"key":"2019101609185367900_B21","article-title":"Methods to determine node centrality and clustering in graphs with uncertain structure","volume-title":"ICWSM","author":"Pfeiffer III,","year":"2011"},{"key":"2019101609185367900_B22","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/11799511_5","article-title":"Link discovery in graphs derived from biological databases","volume-title":"International Workshop on Data Integration in the Life Sciences","author":"Sevon,","year":"2006"},{"key":"2019101609185367900_B23","doi-asserted-by":"crossref","first-page":"208701","DOI":"10.1103\/PhysRevLett.89.208701","article-title":"Assortative mixing in networks","volume":"89","author":"Newman,","year":"2002","journal-title":"Phys. Rev. Lett."},{"key":"2019101609185367900_B24","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1093\/comnet\/cnv005","article-title":"Assortativity in complex networks","volume":"3","author":"Noldus,","year":"2015","journal-title":"J. Complex Netw."},{"key":"2019101609185367900_B25","doi-asserted-by":"crossref","first-page":"2435","DOI":"10.1109\/TKDE.2018.2819651","article-title":"Uncertain graph sparsification","volume":"30","author":"Parchas,","year":"2018","journal-title":"IEEE Trans. Knowl. Data Eng"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/7\/5\/749\/30157019\/cnz003.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/7\/5\/749\/30157019\/cnz003.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T17:21:11Z","timestamp":1662830471000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/7\/5\/749\/5364036"}},"subtitle":[],"editor":[{"given":"Mattia","family":"Frasca","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2019,2,23]]},"references-count":25,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2019,2,23]]},"published-print":{"date-parts":[[2019,10,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnz003","relation":{},"ISSN":["2051-1329"],"issn-type":[{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,10]]},"published":{"date-parts":[[2019,2,23]]}}}