{"entities":{"Q1736547":{"pageid":1747288,"ns":120,"title":"Item:Q1736547","lastrevid":72377592,"modified":"2026-04-14T04:29:54Z","type":"item","id":"Q1736547","labels":{"en":{"language":"en","value":"Computing the eccentricity distribution of large graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042153"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$95522932-FAAC-4039-9540-5A54FE67BED9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3b24b36673634c8d767647d64af223f4ed1202f5","datavalue":{"value":{"text":"Computing the eccentricity distribution of large graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736547$B7352E20-AEDD-49F9-AAF0-7CA030249BDF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a19d7d9856780dde0f2c17e48fb39080b414ed9b","datavalue":{"value":"1462.05128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736547$AEE8EAFE-2813-4963-BCE3-A2A4FAE832D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8dff9a8f8353f4d0e7b61c141990413a34aa5300","datavalue":{"value":{"entity-type":"item","numeric-id":1736546,"id":"Q1736546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$A337294D-5092-4581-8FC2-D7CF065C4E44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"594290c33adb9b7077f6bd5b7a0718d12b66efa6","datavalue":{"value":{"entity-type":"item","numeric-id":1029094,"id":"Q1029094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$4DB9426C-1392-4427-BB31-BCDF1EF796CE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$3CE7761D-B6E4-4961-92D3-52A31BC2E8D0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736547$48DE81F9-758C-4A36-B543-10058EBE018E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"37f24c98c9d94ab6a24a260fca932eff9394232d","datavalue":{"value":"Summary: The eccentricity of a node in a graph is defined as the length of a longest shortest path starting at that node. The eccentricity distribution over all nodes is a relevant descriptive property of the graph, and its extreme values allow the derivation of measures such as the radius, diameter, center and periphery of the graph. This paper describes two new methods for computing the eccentricity distribution of large graphs such as social networks, web graphs, biological networks and routing networks. We first propose an exact algorithm based on eccentricity lower and upper bounds, which achieves significant speedups compared to the straightforward algorithm when computing both the extreme values of the distribution as well as the eccentricity distribution as a whole. The second algorithm that we describe is a hybrid strategy that combines the exact approach with an efficient sampling technique in order to obtain an even larger speedup on the computation of the entire eccentricity distribution. We perform an extensive set of experiments on a number of large graphs in order to measure and compare the performance of our algorithms, and demonstrate how we can efficiently compute the eccentricity distribution of various large real-world graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736547$9BF01017-B055-4515-BB30-C153191BA44D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736547$27884E1C-F0EC-44A5-B69F-C0AFB2395292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736547$1148E115-7FD5-40A7-8C81-31500D3E877A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736547$B945C2A0-CFDD-4097-A37A-065562141024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736547$AFB7B868-8896-40E0-94BB-D0F138A96A30","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"46076f0f198d61f2be97419fb5d4c39c15f96a33","datavalue":{"value":"7042153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736547$6F1D3E1B-1F15-4954-ABDE-D8ECC63935C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d7a6b1e80a17b8d39f4ca4c174505c465cec55b","datavalue":{"value":"eccentricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736547$00280D31-7E9C-4E7C-8363-DAE6D32BBAB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736547$F1ABA195-2A4E-47BE-A2C6-9EFA19DF27E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7567554b1367efc97f3e213c87dba0f77ed4b4f7","datavalue":{"value":"radius","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736547$A4C5C40C-9FEB-4A96-829E-6E3673EF8113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5271886e1f4d2ccecbbef8eb4a8d76d474f622b4","datavalue":{"value":"periphery","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736547$ED0A568F-ED01-4CB8-87C8-5B1EF439703B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c37211a0bc536eab7b9257b09616514207c6194","datavalue":{"value":"center","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736547$DDE70DBC-B54F-4CA9-9B44-76BDDC9C2400","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"3ac64f8f2d2d17b9ddaeef3601effaa3d3406995","datavalue":{"value":{"entity-type":"item","numeric-id":24207,"id":"Q24207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$4E96E1C7-45E2-4301-BD1F-378A0D4CC423","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$6392C844-D2BF-4CD9-A735-8FBFE61DB24D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"981573d04690d8ee1e6f15b04399628970f44bfc","datavalue":{"value":"https://doi.org/10.3390/a6010100","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736547$B1B6BF8A-21D5-4153-9206-0806AD034844","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"96c6add2c6e1a22b5913d2885ab2053822fc687a","datavalue":{"value":"W2070017344","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736547$9B361CEC-43D6-43C5-80BA-549DE3BE5E35","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f17d17fc163e6a7e797dd46ad5e959c0152a3a1c","datavalue":{"value":{"entity-type":"item","numeric-id":2777195,"id":"Q2777195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$3321ED29-5F24-4364-A51A-7FDADFE17DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"042e69cc69c4f2d18a2b570e4c210dba0319140b","datavalue":{"value":{"entity-type":"item","numeric-id":3045073,"id":"Q3045073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$B1EA352A-F314-4321-BC87-FFB732462796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eda6eb34e803e1ded0ec6d7fb8efe6a29a65a462","datavalue":{"value":{"entity-type":"item","numeric-id":5406179,"id":"Q5406179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$AD5FE448-A79E-401F-A076-2F2615890504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54a0860ac5f1dc8f1d05db4fd3a4acba0d6e52ad","datavalue":{"value":{"entity-type":"item","numeric-id":386904,"id":"Q386904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$AC71E81A-D229-4079-B505-9E1EF7B73999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b9801113749c352a4e39dec5a447b7853e40292","datavalue":{"value":{"entity-type":"item","numeric-id":2765440,"id":"Q2765440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$434BD09C-F928-42A0-9CB8-CD89E4803496","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94321bfc87e7cf05b1e33334d6e9df89ae8102af","datavalue":{"value":{"entity-type":"item","numeric-id":1240256,"id":"Q1240256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$7841A834-9954-4E97-8597-A62742A770CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02264d5ffdee50219b903ea31c4440a6a214ae3d","datavalue":{"value":{"entity-type":"item","numeric-id":4692391,"id":"Q4692391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$5B3601BB-788B-4B6C-B72F-4DE5216085F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95e2edeb25db622319d824547264f2dae397ef10","datavalue":{"value":{"entity-type":"item","numeric-id":3191982,"id":"Q3191982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$E7C971E2-6A88-4BE1-A68E-B841777CA2ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6c6ee8f59857ee1cb4085b2f3966b195e2fb90c","datavalue":{"value":{"entity-type":"item","numeric-id":1376406,"id":"Q1376406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$7F761AF4-E9C2-4BA3-A0A3-0316A9260655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eda4d9f1ee65e39750d1156f284e4dfb4ad7eff3","datavalue":{"value":{"entity-type":"item","numeric-id":2768297,"id":"Q2768297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$E0E7C7F3-F0A6-4FC5-8E01-6FBB0DD83C9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"969ace7f0132dce1164dd34145e9edf9e2f456c1","datavalue":{"value":{"entity-type":"item","numeric-id":2999337,"id":"Q2999337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$3A80CA96-4E0B-4500-92ED-9898C2910313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4f826b91deeaf9143fdbb59bfe243979dd325b3","datavalue":{"value":{"entity-type":"item","numeric-id":5450743,"id":"Q5450743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$D3A41AFF-CEDB-452F-8105-27C625497AF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb97551072b5603d612d30231e226d11f68f6a91","datavalue":{"value":{"entity-type":"item","numeric-id":1025963,"id":"Q1025963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$69E7D8BB-D892-4561-8C29-30971FAA56FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ca9d3ec4ef78a89ee9448f23a6c7bc94a9658bb","datavalue":{"value":{"entity-type":"item","numeric-id":3164211,"id":"Q3164211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$E7FB8991-93B9-49FB-8D73-7274E70FF6E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"61aa54fbba4f1f4de000c4e41271b46b81b52a55","datavalue":{"value":"10.3390/A6010100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736547$ADE96EA3-8D8B-42B7-AD63-7F9DC3DB9114","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d779c48a7becd0e288b8f2903c727b84a168cc8d","datavalue":{"value":{"entity-type":"item","numeric-id":4968378,"id":"Q4968378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aec94996ceb400578a8fd43889c1d54b8cc88e67","datavalue":{"value":{"amount":"+0.767604410648346","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736547$2FD023BB-DD26-46DB-A8B8-37B8C785569F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"920793f932d002d213dc791d9e379af5ff541f68","datavalue":{"value":{"entity-type":"item","numeric-id":2819520,"id":"Q2819520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2e422e0e7961e3337bb41a57299dd0d0e03d99c","datavalue":{"value":{"amount":"+0.7518012523651123","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736547$17682FBD-019C-41B1-8385-01BFBE4392B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"259f6ab5e0a47b7f2fda4c5a51e9b2876750ccba","datavalue":{"value":{"entity-type":"item","numeric-id":2194537,"id":"Q2194537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a880553a472125396ce8cf613c02ee3db077c31b","datavalue":{"value":{"amount":"+0.748404324054718","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736547$60D10B6B-0C96-4ABC-A775-D5C6A4EB0C23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1b736e9d2baf717b0bfb79ecb8bc074c10bd2c1","datavalue":{"value":{"entity-type":"item","numeric-id":2327101,"id":"Q2327101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"307e6c73ccf8b6ed389151470804cacdaae8c764","datavalue":{"value":{"amount":"+0.7474305033683777","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736547$569C5997-619A-4046-AB9D-97811EF4EF5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28e0d9aefbac60b90e2f7d59d14c954db378b0ac","datavalue":{"value":{"entity-type":"item","numeric-id":3708836,"id":"Q3708836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f4464ca6042ef0b4fd34b508030dc0031b0ced2","datavalue":{"value":{"amount":"+0.7474192380905151","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736547$1411E2D1-C31D-43EF-B923-F57FFEB75A65","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736547$A7B948BA-FE3A-4E48-9A9A-401BBF5F5011","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing the eccentricity distribution of large graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_the_eccentricity_distribution_of_large_graphs"}}}}}