File(s) under permanent embargo
New benchmarks for large-scale networks with given maximum degree and diameter
journal contribution
posted on 2010-09-01, 00:00 authored by E Loz, Guillermo Pineda VillavicencioGuillermo Pineda VillavicencioLarge-scale networks have become ubiquitous elements of our society. Modern social networks, supported by communication and travel technology, have grown in size and complexity to unprecedented scales. Computer networks, such as the Internet, have a fundamental impact on commerce, politics and culture. The study of networks is also central in biology, chemistry and other natural sciences. Unifying aspects of these networks are a small maximum degree and a small diameter, which are also shared by many network models, such as small-world networks. Graph theoretical methodologies can be instrumental in the challenging task of predicting, constructing and studying the properties of large-scale networks. This task is now necessitated by the vulnerability of large networks to phenomena such as cross-continental spread of disease and botnets (networks of malware). In this article, we produce the new largest known networks of maximum degree 17 ≤ Δ ≤ 20 and diameter 2 ≤ D ≤ 10, using a wide range of techniques and concepts, such as graph compounding, vertex duplication, Kronecker product, polarity graphs and voltage graphs. In this way, we provide new benchmarks for networks with given maximum degree and diameter, and a complete overview of state-of-the-art methodology that can be used to construct such networks.
History
Journal
Computer journalVolume
53Issue
7Pagination
1092 - 1105Publisher
Oxford University PressLocation
Oxford, Eng.Publisher DOI
ISSN
0010-4620eISSN
1460-2067Language
engPublication classification
C1.1 Refereed article in a scholarly journalCopyright notice
2009, The AuthorUsage metrics
Categories
No categories selectedKeywords
degree\/diameter problemMoore boundMoore graphslarge-scale networkssmall-world networksvertex duplicationKronecker productgraph compoundingvoltage assignmentpolarity graphsvoltage graphsCayley graphsScience & TechnologyTechnologyComputer Science, Hardware & ArchitectureComputer Science, Information SystemsComputer Science, Software EngineeringComputer Science, Theory & MethodsComputer Sciencedegreediameter problemLARGE GRAPHSCOMPOUND GRAPHS
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC