{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:42:21Z","timestamp":1773895341533,"version":"3.50.1"},"reference-count":32,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2013,2,18]],"date-time":"2013-02-18T00:00:00Z","timestamp":1361145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a6010100","type":"journal-article","created":{"date-parts":[[2013,2,19]],"date-time":"2013-02-19T11:11:16Z","timestamp":1361272276000},"page":"100-118","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":45,"title":["Computing the Eccentricity Distribution of Large Graphs"],"prefix":"10.3390","volume":"6","author":[{"given":"Frank","family":"Takes","sequence":"first","affiliation":[{"name":"Leiden Institute of Advanced Computer Science, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands"}]},{"given":"Walter","family":"Kosters","sequence":"additional","affiliation":[{"name":"Leiden Institute of Advanced Computer Science, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands"}]}],"member":"1968","published-online":{"date-parts":[[2013,2,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Sala, A., Cao, L., Wilson, C., Zablit, R., Zheng, H., and Zhao, B. (2010, January 26\u201330). Measurement-Calibrated Graph Models for Social Network Experiments. Proceedings of the 19th ACM International Conference on the World Wide Web (WWW), Raleigh, NC, USA.","DOI":"10.1145\/1772690.1772778"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/505659.505663","article-title":"Analysis of the autonomous system network topology","volume":"31","author":"Magoni","year":"2001","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Magoni, D., and Pansiot, J. (2002, January 19\u201324). Analysis and Comparison of Internet Topology Generators. Proceedings of the 2nd International Conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; and Mobile and Wireless Communications, Pisa, Italy.","DOI":"10.1007\/3-540-47906-6_29"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Pavlopoulos, G., Secrier, M., Moschopoulos, C., Soldatos, T., Kossida, S., Aerts, J., Schneider, R., and Bagos, P. (2011). Using graph theory to analyze biological networks. BioData Min., 4.","DOI":"10.1186\/1756-0381-4-10"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Magnien, C., Latapy, M., and Habib, M. (2009). Fast computation of empirically tight bounds for the diameter of massive graphs. J. Exp. Algorithm., 13.","DOI":"10.1145\/1412228.1455266"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Takes, F.W., and Kosters, W.A. (2011, January 24\u201328). Determining the Diameter of Small World Networks. Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM), Glasgow, UK.","DOI":"10.1145\/2063576.2063748"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Grossi, R., Habib, M., Lanzi, L., and Marino, A. (2012). On computing the diameter of real-world undirected graphs. Theor. Comput. Sci., in press.","DOI":"10.1007\/978-3-642-30850-5_10"},{"key":"ref_8","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":"Soc. Netw."},{"key":"ref_9","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":"ref_10","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF02017925","article-title":"Eccentric sequences in graphs","volume":"6","author":"Lesniak","year":"1975","journal-title":"Period. Math. Hung."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0378-8733(94)00248-9","article-title":"Eccentricity and centrality in networks","volume":"17","author":"Hage","year":"1995","journal-title":"Soc. Netw."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kang, U., Tsourakakis, C., Appel, A., Faloutsos, C., and Leskovec, J. (2011). Hadi: Mining radii of large graphs. ACM Trans. Knowl. Discov. Data (TKDD), 5.","DOI":"10.1145\/1921632.1921634"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J., and Faloutsos, C. (2007). Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data (TKDD), 1.","DOI":"10.1145\/1217299.1217301"},{"key":"ref_14","unstructured":"Palmer, C., Gibbons, P., and Faloutsos, C. (2002, January 23\u201326). ANF: A Fast and Scalable Tool for Data Mining in Massive Graphs. Proceedings of the 8th ACM International Conference on Knowledge Discovery and Data Mining (KDD), Edmonton, Canada."},{"key":"ref_15","unstructured":"Buckley, F., and Harary, F. (1990). Distance in Graphs, Addison-Wesley."},{"key":"ref_16","unstructured":"Yuster, R., and Zwick, U. (2005, January 23\u201325). Answering Distance Queries in Directed Graphs Using Fast Matrix Multiplication. Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), Pittsburgh, PA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Kleinberg, J. (2000, January 21\u201323). The Small-World Phenomenon: An Algorithm Perspective. Proceedings of the 32nd ACM symposium on Theory of Computing, Portland, OR, USA.","DOI":"10.1145\/335305.335325"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/316194.316229","article-title":"On power-law relationships of the internet topology","volume":"29","author":"Faloutsos","year":"1999","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Leskovec, J., and Faloutsos, C. (2006, January 20\u201323). Sampling from Large Graphs. Proceedings of the 12th ACM International Conference on Knowledge Discovery and Data Mining (KDD), Philadelphia, PA, USA.","DOI":"10.1145\/1150402.1150479"},{"key":"ref_20","unstructured":"Eppstein, D., and Wang, J. (2001, January 7\u20139). Fast Approximation of Centrality. Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), Washington, DC, USA."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Grossi, R., Lanzi, L., and Marino, A. (2011, January 18\u201320). A Comparison of Three Algorithms for Approximating the Distance Distribution in Real-World Graphs. Proceedings of the Theory and Practice of Algorithms in (Computer) Systems (TAPAS), LNCS 6595, Rome, Italy.","DOI":"10.1007\/978-3-642-19754-3_11"},{"key":"ref_22","unstructured":"Klimt, B., and Yang, Y. (2004, January 20\u201324). The Enron Corpus: A New Dataset for Email Classification Research. Proceedings of the 15th European Conference on Machine Learning (ECML), LNCS 3201, Pisa, Italy."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Boldi, P., Rosa, M., and Vigna, S. (2011, January 16\u201320). HyperANF: Approximating the Neighbourhood Function of very Large Graphs on a Budget. Proceedings of the 20th ACM International Conference on the World Wide Web (WWW), Hyderabad, India.","DOI":"10.1145\/1963405.1963493"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1038\/35075138","article-title":"Lethality and centrality in protein networks","volume":"411","author":"Jeong","year":"2001","journal-title":"Nature"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J., and Faloutsos, C. (2007). Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1.","DOI":"10.1145\/1217299.1217301"},{"key":"ref_26","unstructured":"Sommer, C. Graphs. Available online: http:\/\/www.sommer.jp\/graphs."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"G\u00f3mez, V., Kaltenbrunner, A., and L\u00f3pez, V. (2008, January 21\u201325). Statistical Analysis of the Social Network and Discussion Threads in Slashdot. Proceedings of the 17th International Conference on the World Wide Web (WWW), Beijng, China.","DOI":"10.1145\/1367497.1367585"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Mislove, A., Marcon, M., Gummadi, K., Druschel, P., and Bhattacharjee, B. (2007, January 24\u201326). Measurement and Analysis of Online Social Networks. Proceedings of the 7th ACM Conference on Internet Measurement, San Diego, CA, USA.","DOI":"10.1145\/1298306.1298311"},{"key":"ref_29","unstructured":"Richardson, M., Agrawal, R., and Domingos, P. (2003, January 20\u201323). Trust Management for the Semantic Web. Proceedings of the 2nd International Semantic Web Conference (ISWC), LNCS 2870, Sanibel Island, FL, USA."},{"key":"ref_30","first-page":"29","article-title":"Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters","volume":"6","author":"Leskovec","year":"2009","journal-title":"Int. Math."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0378-4371(00)00018-2","article-title":"Scale-free characteristics of random networks: The topology of the world-wide web","volume":"281","author":"Albert","year":"2000","journal-title":"Phys. Stat. Mech. Appl."},{"key":"ref_32","unstructured":"Magoni, D., and Pansiot, J. (2002, January 1\u20134). Internet Topology Modeler Based on Map Sampling. Proceedings of the 7th International Symposium on Computers and Communications (ISCC), Taormina, Italy."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/1\/100\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:44:58Z","timestamp":1760219098000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/1\/100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,18]]},"references-count":32,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2013,3]]}},"alternative-id":["a6010100"],"URL":"https:\/\/doi.org\/10.3390\/a6010100","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2,18]]}}}