{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:24:01Z","timestamp":1762323841301,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,5,26]],"date-time":"2015-05-26T00:00:00Z","timestamp":1432598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Polish Ministry of Science and Higher Education from the budget for science in the years 2013--2015, Project No. IP2012 022972"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2015,7,21]]},"abstract":"<jats:p>In this tutorial, 17 structural complexity indices are presented and compared, each representing one of the following categories: adjacency- and distance-based metrics, Shannon entropy-based metrics, product measures, subgraph-based metrics, and path- and walk-based metrics. The applicability of these indices to computer and communication networks is evaluated with the aid of different elementary, specifically designed, random, and real network topologies. On the grounds of the evaluation study, advantages and disadvantages of particular metrics are identified. In addition, their general properties and runtimes are assessed, and a general view on the structural network complexity is presented.<\/jats:p>","DOI":"10.1145\/2755621","type":"journal-article","created":{"date-parts":[[2015,5,27]],"date-time":"2015-05-27T18:11:50Z","timestamp":1432750310000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Assessing the Structural Complexity of Computer and Communication Networks"],"prefix":"10.1145","volume":"47","author":[{"given":"Andrzej","family":"Kamisi\u0144ski","sequence":"first","affiliation":[{"name":"AGH University of Science and Technology, Krak\u00f3w, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Cho\u0142da","sequence":"additional","affiliation":[{"name":"AGH University of Science and Technology, Krak\u00f3w, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Jajszczyk","sequence":"additional","affiliation":[{"name":"AGH University of Science and Technology, Krak\u00f3w, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,5,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/qua.10057"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"A.-L. Barab\u00e1si and R. Albert. 1999. Emergence of scaling in random networks. Science 286 5439 509--512. DOI:http:\/\/dx.doi.org\/10.1126\/science.286.5439.509  A.-L. Barab\u00e1si and R. Albert. 1999. Emergence of scaling in random networks. Science 286 5439 509--512. DOI:http:\/\/dx.doi.org\/10.1126\/science.286.5439.509","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.1906679"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1021\/ja00402a071"},{"key":"e_1_2_1_6_1","volume-title":"Graduate Texts in Mathematics","volume":"184","author":"Bollob\u00e1s B.","year":"1998"},{"key":"e_1_2_1_7_1","unstructured":"D. Bonchev and G. A. Buck. 2005. Quantitative measures of network complexity. In Complexity in Chemistry Biology and Ecology D. Bonchev and D. H. Rouvray (Eds.). Springer New York NY 191--235. DOI:http:\/\/dx.doi.org\/10.1007\/0-387-25871-X&lowbar;5  D. Bonchev and G. A. Buck. 2005. Quantitative measures of network complexity. In Complexity in Chemistry Biology and Ecology D. Bonchev and D. H. Rouvray (Eds.). Springer New York NY 191--235. DOI:http:\/\/dx.doi.org\/10.1007\/0-387-25871-X&lowbar;5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"J. R. Bunch and J. E. Hopcroft. 1974. Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation 28 125 231--236.  J. R. Bunch and J. E. Hopcroft. 1974. Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation 28 125 231--236.","DOI":"10.1090\/S0025-5718-1974-0331751-8"},{"key":"e_1_2_1_9_1","unstructured":"G. Caldarelli. 2013. Scale-Free Networks: Complex Webs in Nature and Technology. Oxford University Press Oxford UK.  G. Caldarelli. 2013. Scale-Free Networks: Complex Webs in Nature and Technology. Oxford University Press Oxford UK."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"J. C. Claussen. 2008. Offdiagonal complexity: A computationally quick network complexity measure--application to protein networks and cell division. In A. Deutsch R. B. Parra R. J. de Boer O. Diekmann P. Jagers E. Kisdi M. Kretzschmar P. Lansky and H. Metz (Eds.) Mathematical Modeling of Biological Systems Volume II Birkh\u00e4user Boston MA 279--287. DOI:http:\/\/dx.doi.org\/10.1007\/978-0-8176-4556-4_25  J. C. Claussen. 2008. Offdiagonal complexity: A computationally quick network complexity measure--application to protein networks and cell division. In A. Deutsch R. B. Parra R. J. de Boer O. Diekmann P. Jagers E. Kisdi M. Kretzschmar P. Lansky and H. Metz (Eds.) Mathematical Modeling of Biological Systems Volume II Birkh\u00e4user Boston MA 279--287. DOI:http:\/\/dx.doi.org\/10.1007\/978-0-8176-4556-4_25","DOI":"10.1007\/978-0-8176-4556-4_25"},{"key":"e_1_2_1_11_1","unstructured":"D. M. Cvetkovi\u0107 M. Doob and H. Sachs. 1998. Spectra of Graphs: Theory and Applications (3rd revised and enlarged ed.). Wiley-VCH Weinheim Germany.  D. M. Cvetkovi\u0107 M. Doob and H. Sachs. 1998. Spectra of Graphs: Theory and Applications (3rd revised and enlarged ed.). Wiley-VCH Weinheim Germany."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"M. Dehmer and F. Emmert-Streib. 2013. Advances in Network Complexity. Wiley-VCH Verlag GmbH &amp; Co. KGaA. DOI:http:\/\/dx.doi.org\/10.1002\/9783527670468  M. Dehmer and F. Emmert-Streib. 2013. Advances in Network Complexity. Wiley-VCH Verlag GmbH &amp; Co. KGaA. DOI:http:\/\/dx.doi.org\/10.1002\/9783527670468","DOI":"10.1002\/9783527670468"},{"volume-title":"Retrieved","year":"2014","author":"Britannica Encyclop\u00e6dia","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I","volume":"6","author":"Erd\u0151s P.","year":"1959","journal-title":"Publlicationes Mathematicae Debrecen"},{"key":"e_1_2_1_15_1","unstructured":"G. H. Golub and C. F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press Baltimore MD.   G. H. Golub and C. F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press Baltimore MD."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"J. L. Gross and J. Yellen. 2003. Discrete mathematics and its applications. In Handbook of Graph Theory (1st ed.). CRC Press Boca Raton FL.  J. L. Gross and J. Yellen. 2003. Discrete mathematics and its applications. In Handbook of Graph Theory (1st ed.). CRC Press Boca Raton FL.","DOI":"10.1201\/9780203490204.ch1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci000149u"},{"volume-title":"Retrieved","year":"2015","author":"Kamisi\u0144ski A.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"V. Karyotis E. Stai and S. Papavassiliou. 2013. Evolutionary Dynamics of Complex Communications Networks. CRC Press Boca Raton FL. DOI:http:\/\/dx.doi.org\/10.1201\/b15505   V. Karyotis E. Stai and S. Papavassiliou. 2013. Evolutionary Dynamics of Complex Communications Networks. CRC Press Boca Raton FL. DOI:http:\/\/dx.doi.org\/10.1201\/b15505","DOI":"10.1201\/b15505"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"J. Kim and T. Wilhelm. 2008. What is a complex graph&quest; Physica A: Statistical Mechanics and its Applications 387 11 2637--2652. DOI:http:\/\/dx.doi.org\/10.1016\/j.physa.2008.01.015  J. Kim and T. Wilhelm. 2008. What is a complex graph&quest; Physica A: Statistical Mechanics and its Applications 387 11 2637--2652. DOI:http:\/\/dx.doi.org\/10.1016\/j.physa.2008.01.015","DOI":"10.1016\/j.physa.2008.01.015"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"V. Latora and M. Marchiori. 2003. Economic small-world behavior in weighted networks. The European Physical Journal B\u2014Condensed Matter and Complex Systems 32 2 249--263. DOI:http:\/\/dx.doi.org\/10.1140\/epjb\/e2003-00095-5  V. Latora and M. Marchiori. 2003. Economic small-world behavior in weighted networks. The European Physical Journal B\u2014Condensed Matter and Complex Systems 32 2 249--263. DOI:http:\/\/dx.doi.org\/10.1140\/epjb\/e2003-00095-5","DOI":"10.1140\/epjb\/e2003-00095-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_23_1","first-page":"8","article-title":"On walk counts and complexity of general graphs","volume":"1","author":"Lukovits I.","year":"2002","journal-title":"Internet Electronic Journal of Molecular Design"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"E. A. Moore B. T. Sutcliffe A. H. Pakiari T. E. Simos S. Wilson M. Springborg D. Pugh R. A. Lewis N. Trinajsti\u0107 and K. Travis. 2004. Chemical Modelling. SPR\u2014Chemical Modelling Vol. 3. The Royal Society of Chemistry. DOI:http:\/\/dx.doi.org\/10.1039\/9781847553331  E. A. Moore B. T. Sutcliffe A. H. Pakiari T. E. Simos S. Wilson M. Springborg D. Pugh R. A. Lewis N. Trinajsti\u0107 and K. Travis. 2004. Chemical Modelling. SPR\u2014Chemical Modelling Vol. 3. The Royal Society of Chemistry. DOI:http:\/\/dx.doi.org\/10.1039\/9781847553331","DOI":"10.1039\/9781847553331"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1021\/c160017a018"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02476948"},{"key":"e_1_2_1_27_1","first-page":"321","article-title":"A symmetry index for graphs. Symmetry","volume":"21","author":"Mowshowitz A.","year":"2010","journal-title":"Culture and Science"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v55:3"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.540050612"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"M. Razinger. 1982. Extended connectivity in chemical graphs. Theoretica chimica acta 61 6 581--586. DOI:http:\/\/dx.doi.org\/10.1007\/BF00552670  M. Razinger. 1982. Extended connectivity in chemical graphs. Theoretica chimica acta 61 6 581--586. DOI:http:\/\/dx.doi.org\/10.1007\/BF00552670","DOI":"10.1007\/BF02394734"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1021\/ci00015a005","article-title":"Counts of all walks as atomic and molecular descriptors","volume":"33","author":"R\u00fccker G.","year":"1993","journal-title":"Journal of Chemical Information and Computer Sciences"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1078"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of \u201csmall-world\u201d networks. Nature 393 6684 440--442. DOI:http:\/\/dx.doi.org\/10.1038\/30918  D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of \u201csmall-world\u201d networks. Nature 393 6684 440--442. DOI:http:\/\/dx.doi.org\/10.1038\/30918","DOI":"10.1038\/30918"},{"key":"e_1_2_1_34_1","unstructured":"D. B. West. 2000. Introduction to Graph Theory (2nd ed.). Prentice Hall Upper Saddle River NJ.  D. B. West. 2000. Introduction to Graph Theory (2nd ed.). Prentice Hall Upper Saddle River NJ."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3800(03)00207-2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2007.06.029"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2755621","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2755621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:17:05Z","timestamp":1750227425000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2755621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,26]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,7,21]]}},"alternative-id":["10.1145\/2755621"],"URL":"https:\/\/doi.org\/10.1145\/2755621","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"type":"print","value":"0360-0300"},{"type":"electronic","value":"1557-7341"}],"subject":[],"published":{"date-parts":[[2015,5,26]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}