More Web Proxy on the site http://driver.im/

tutorial

Assessing the Structural Complexity of Computer and Communication Networks

Authors:

Andrzej Kamisiński,

Andrzej JajszczykAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 47, Issue 4

Article No.: 66, Pages 1 - 36

https://doi.org/10.1145/2755621

Published: 26 May 2015 Publication History

Abstract

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.

References

[1]

R. Albert and A.-L. Barabási. 2002. Statistical mechanics of complex networks. Reviews of Modern Physics 74, 1, 47--97.

[2]

D. Babić, D. J. Klein, I. Lukovits, S. Nikolić, and N. Trinajstić. 2002. Resistance-distance matrix: A computational algorithm and its application. International Journal of Quantum Chemistry 90, 1, 166--176.

[3]

A.-L. Barabási and R. Albert. 1999. Emergence of scaling in random networks. Science 286, 5439, 509--512.

[4]

A. Bavelas. 1950. Communication patterns in task-oriented groups. Journal of the Acoustical Society of America 22, 6, 725--730.

[5]

S. H. Bertz. 1981. The first general index of molecular complexity. Journal of the American Chemical Society 103, 12, 3599--3601.

[6]

B. Bollobás. 1998. Modern Graph Theory. Graduate Texts in Mathematics, Vol. 184. Springer, New York, NY.

[7]

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.

[8]

J. R. Bunch and J. E. Hopcroft. 1974. Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation 28, 125, 231--236.

[9]

G. Caldarelli. 2013. Scale-Free Networks: Complex Webs in Nature and Technology. Oxford University Press, Oxford, UK.

[10]

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äuser, Boston, MA, 279--287.

[11]

D. M. Cvetković, M. Doob, and H. Sachs. 1998. Spectra of Graphs: Theory and Applications (3rd revised and enlarged ed.). Wiley-VCH, Weinheim, Germany.

[12]

M. Dehmer and F. Emmert-Streib. 2013. Advances in Network Complexity. Wiley-VCH Verlag GmbH & Co. KGaA.

[13]

Encyclopædia Britannica. 2014. Chemical compound. (2014). Retrieved April 21, 2015 from http://www.britannica.com/EBchecked/topic/108614/chemical-compound/278310/Functional-groups.

[14]

P. Erdős and A. Rényi. 1959. On random graphs I. Publlicationes Mathematicae Debrecen 6, 290--297.

[15]

G. H. Golub and C. F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press, Baltimore, MD.

Digital Library

[16]

J. L. Gross and J. Yellen. 2003. Discrete mathematics and its applications. In Handbook of Graph Theory (1st ed.). CRC Press, Boca Raton, FL.

[17]

I. Gutman, C. Rücker, and G. Rücker. 2001. On walks in molecular graphs. Journal of Chemical Information and Computer Sciences 41, 3, 739--745.

[18]

A. Kamisiński, P. Chołda, and A. Jajszczyk. 2015. Online Appendix. (Jan. 2015). Retrieved April 12, 2015 from http://kt.agh.edu.pl/&sim;kamisinski/pub/2015&lowbar;csur&lowbar;complexity/.

[19]

V. Karyotis, E. Stai, and S. Papavassiliou. 2013. Evolutionary Dynamics of Complex Communications Networks. CRC Press, Boca Raton, FL.

Digital Library

[20]

J. Kim and T. Wilhelm. 2008. What is a complex graph&quest; Physica A: Statistical Mechanics and its Applications 387, 11, 2637--2652.

[21]

V. Latora and M. Marchiori. 2003. Economic small-world behavior in weighted networks. The European Physical Journal B—Condensed Matter and Complex Systems 32, 2, 249--263.

[22]

F. Le Gall. 2014. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC’14). ACM, New York, NY, 296--303.

Digital Library

[23]

I. Lukovits, A. Miličević, S. Nikolić, and N. Trinajstić. 2002. On walk counts and complexity of general graphs. Internet Electronic Journal of Molecular Design 1, 8. 388--400. http://www.biochempress.com/av01&lowbar;0388.html.

[24]

E. A. Moore, B. T. Sutcliffe, A. H. Pakiari, T. E. Simos, S. Wilson, M. Springborg, D. Pugh, R. A. Lewis, N. Trinajstić, and K. Travis. 2004. Chemical Modelling. SPR—Chemical Modelling, Vol. 3. The Royal Society of Chemistry.

[25]

H. L. Morgan. 1965. The generation of a unique machine description for chemical structures—a technique developed at chemical abstracts service. Journal of Chemical Documentation 5, 2, 107--113.

[26]

A. Mowshowitz. 1968. Entropy and the complexity of graphs: I. An index of the relative complexity of a graph. Bulletin of Mathematical Biophysics 30, 1, 175--204.

[27]

A. Mowshowitz and M. Dehmer. 2010. A symmetry index for graphs. Symmetry: Culture and Science 21, 4, 321--327.

[28]

S. Orlowski, R. Wessäly, M. Pióro, and A. Tomaszewski. 2010. SNDlib 1.0—survivable network design library. Networks 55, 3, 276--286.

Digital Library

[29]

C. Raychaudhury, S. K. Ray, J. J. Ghosh, A. B. Roy, and S. C. Basak. 1984. Discrimination of isomeric structures using information theoretic topological indices. Journal of Computational Chemistry 5, 6, 581--588.

[30]

M. Razinger. 1982. Extended connectivity in chemical graphs. Theoretica chimica acta 61, 6, 581--586.

[31]

G. Rücker and C. Rücker. 1993. Counts of all walks as atomic and molecular descriptors. Journal of Chemical Information and Computer Sciences 33, 5, 683--695.

[32]

R. Seidel. 1995. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences 51, 3, 400--403.

Digital Library

[33]

D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of “small-world” networks. Nature 393, 6684, 440--442.

[34]

D. B. West. 2000. Introduction to Graph Theory (2nd ed.). Prentice Hall, Upper Saddle River, NJ.

[35]

T. Wilhelm. 2003. An elementary dynamic model for non-binary food webs. Ecological Modelling 168, 1--2, 145--152.

[36]

T. Wilhelm and J. Hollunder. 2007. Information theoretic description of networks. Physica A: Statistical Mechanics and Its Applications 385, 1, 385--396.

Cited By

Oehlers MFabian B(2021)Graph Metrics for Network Robustness—A SurveyMathematics10.3390/math90808959:8(895)Online publication date: 17-Apr-2021
https://doi.org/10.3390/math9080895
Hajder PRauch Ł(2019)Reconfiguration of the Multi-channel Communication System with Hierarchical Structure and Distributed Passive SwitchingComputational Science – ICCS 201910.1007/978-3-030-22741-8_36(502-516)Online publication date: 12-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-22741-8_36

Index Terms

Assessing the Structural Complexity of Computer and Communication Networks
1. Networks
  1. Network properties
    1. Network structure

Recommendations

A novel metric for assessing structural complexity of data warehouse requirements models
Abstract
Metrics can be used to evaluate the overall structural complexity of the data warehouse (DW) and assess its quality in the early phases of design and development. The requirements data model plays a crucial role in developing a quality-based DW. ...
Assessing the maintainability of software product line feature models using structural metrics

A software product line is a unified representation of a set of conceptually similar software systems that share many common features and satisfy the requirements of a particular domain. Within the context of software product lines, feature models are ...
Towards measurement of structural complexity for ontologies

Ontologies represent knowledge of a particular domain and form an elementary unit for inference techniques on the semantic web. It is important to measure the complexity of ontologies in order for users to better understand, maintain, reuse and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 47, Issue 4

July 2015

573 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/2775083

Editor:
Sartaj Sahni
Department of Computer and Information Science and Engineering/University of Florida/Gainesville, FL

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 May 2015

Accepted: 01 April 2015

Revised: 01 January 2015

Received: 01 April 2014

Published in CSUR Volume 47, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed

Funding Sources

Polish Ministry of Science and Higher Education from the budget for science in the years 2013--2015, Project No. IP2012 022972

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
557
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Oehlers MFabian B(2021)Graph Metrics for Network Robustness—A SurveyMathematics10.3390/math90808959:8(895)Online publication date: 17-Apr-2021
https://doi.org/10.3390/math9080895
Hajder PRauch Ł(2019)Reconfiguration of the Multi-channel Communication System with Hierarchical Structure and Distributed Passive SwitchingComputational Science – ICCS 201910.1007/978-3-030-22741-8_36(502-516)Online publication date: 12-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-22741-8_36

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents