×

A novel small-world network model: keeping connectivity without adding edges. (English) Zbl 1178.68055

Summary: Considering the problems of potentially generating a disconnected network in the WS small-world network model and of adding edges in the NW small-world network model, we propose a novel small-world network model. First, generate a regular ring lattice of \(N\) vertices. Second, randomly rewire each edge of the lattice with probability \(p\). During the random rewiring procedure, keep the edges between the two nearest neighbor vertices, namely, always keep a connected ring. This model need not add edges and can maintain connectivity of the network at all times in the random rewiring procedure. Simulation results show that the novel model has the typical small-world properties which are small characteristic path length and high clustering coefficient. For large \(N\), the model is approximately equal to the WS model. For large \(N\) and small \(p\), the model is approximately equal to the WS model or the NW model.

MSC:

68M10 Network design and communication in computer systems
90B10 Deterministic network models in operations research
90B15 Stochastic network models in operations research
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1038/30918 · Zbl 1368.05139 · doi:10.1038/30918
[2] Barabási A. L., Science 286 pp 509– · Zbl 1353.94001
[3] Jeong H., Nature 407 pp 651–
[4] DOI: 10.1126/science.298.5594.824 · doi:10.1126/science.298.5594.824
[5] DOI: 10.1016/j.physa.2004.03.019 · doi:10.1016/j.physa.2004.03.019
[6] DOI: 10.1140/epjb/e2005-00237-9 · doi:10.1140/epjb/e2005-00237-9
[7] DOI: 10.1016/S0375-9601(99)00757-4 · Zbl 0940.82029 · doi:10.1016/S0375-9601(99)00757-4
[8] DOI: 10.1007/s100510051038 · doi:10.1007/s100510051038
[9] DOI: 10.1209/epl/i2001-00346-7 · doi:10.1209/epl/i2001-00346-7
[10] DOI: 10.1103/PhysRevLett.88.128701 · doi:10.1103/PhysRevLett.88.128701
[11] Li Y., Commun. Theor. Phys. 45 pp 950–
[12] DOI: 10.1103/PhysRevE.72.046127 · doi:10.1103/PhysRevE.72.046127
[13] DOI: 10.1016/j.physa.2006.10.071 · doi:10.1016/j.physa.2006.10.071
[14] DOI: 10.1103/PhysRevE.67.036106 · doi:10.1103/PhysRevE.67.036106
[15] DOI: 10.1103/PhysRevLett.96.138701 · doi:10.1103/PhysRevLett.96.138701
[16] DOI: 10.1073/pnas.200327197 · doi:10.1073/pnas.200327197
[17] DOI: 10.1103/PhysRevE.69.046106 · doi:10.1103/PhysRevE.69.046106
[18] DOI: 10.1103/PhysRevLett.84.3201 · doi:10.1103/PhysRevLett.84.3201
[19] DOI: 10.1007/s100510050067 · doi:10.1007/s100510050067
[20] DOI: 10.1017/CBO9780511814068 · doi:10.1017/CBO9780511814068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.