Growing scale-free networks with tunable clustering

Petter Holme; Beom Jun Kim

doi:10.1103/PhysRevE.65.026107

Access by Xinjiang University

Growing scale-free networks with tunable clustering

Petter Holme^* and Beom Jun Kim^†

Department of Theoretical Physics, Umeȧ University, 901 87 Umeȧ, Sweden

^*Electronic address: holme@tp.umu.se
^†Electronic address: kim@tp.umu.se

PDF

Phys. Rev. E 65, 026107 – Published 11 January, 2002

DOI: https://doi.org/10.1103/PhysRevE.65.026107

Abstract

We extend the standard scale-free network model to include a “triad formation step.” We analyze the geometric properties of networks generated by this algorithm both analytically and by numerical calculations, and find that our model possesses the same characteristics as the standard scale-free networks such as the power-law degree distribution and the small average geodesic length, but with the high clustering at the same time. In our model, the clustering coefficient is also shown to be tunable simply by changing a control parameter—the average number of triad formation trials per time step.

References (16)

For reviews, see e.g., D. J. Watts, Small Worlds (Princeton University Press, Princeton, 1999); M. E. J. Newman, J. Stat. Phys. 101, 819 (2000); S. H. Strogatz, Nature (London) 410, 268 (2001); S. N. Dorogovtsev and J. F. F. Mendes, Adv. Phys. (to be published).
A. Rapoport, Bull. Math. Biophys. 15, 523 (1953); 535 (2001).
A. Rapoport, Bull. Math. Biophys. 19, 257 (1957); T. J. Fararo and M. Sunshine, A Study of a Biased Friendship Net (Syracuse University Press, Syracuse, 1964); J. A. Davis, Human Relations 20, 181 (1967); I. Pool and M. Kochen, Soc. Networks 1, 1 (1978); ibid.J. Skvoretz, 7, 225 (1985).
C. C. Foster, A. Rapoport, and C. J. Orwant, Behav. Sci. 8, 56 (1963).
O. Frank and D. Strauss, J. Am. Stat. Assoc. 81, 832 (1986).
D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998).
A.-L. Barabási and R. Albert, Science 286, 509 (1999); A.-L. Barabási, R. Albert, and H. Jeong, Physica A 272, 173 (1999); R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 401, 130 (1999).
For an introduction to graph theory, see for example: R. J. Wilson, Introduction to Graph Theory (Oliver & Boyd, Edinburgh, 1972); G. Chartrand and L. Lesniak, Graphs and Digraphs (Weber and Smith, Boston, 1986).
M. E. J. Newman, Phys. Rev. E 64, 025102 (2001).
D. Strauss, SIAM Rev. 28, 513 (1986).
K. Klemm and V. M. Equíluz, e-print cond-mat/0107606; e-print cond-mat/0107607.
See the following recent studies, and references therein: S. Redner, Eur. Phys. J. B 4, 131 (1998); S. Bilke and C. Peterson, Phys. Rev. E 64, 036106 (2001); Y. Fang and R. Rosseau, Scientometrics 50, 273 (2001).
A. R. Puniyani, R. M. Lukose, and B. A. Huberman, e-print cond-mat/0107212.
J. Davidsen, H. Ebel, and S. Bornholdt, cond-mat/0108302.
In practice one may use $P_{w} {= (k}_{w} + 1) / \sum_{v \in V} {(k}_{v} + 1),$ to make it possible for disconnected vertices to be connected. This does not change the resultant network geometry significantly.
S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukin, Phys. Rev. E 63, 062101 (2001).

[c1] For reviews, see e.g., D. J. Watts, Small Worlds (Princeton University Press, Princeton, 1999); M. E. J. Newman, J. Stat. Phys. 101, 819 (2000); S. H. Strogatz, Nature (London) 410, 268 (2001); S. N. Dorogovtsev and J. F. F. Mendes, Adv. Phys. (to be published).

[c2] A. Rapoport, Bull. Math. Biophys. 15, 523 (1953); 535 (2001).

[c3] A. Rapoport, Bull. Math. Biophys. 19, 257 (1957); T. J. Fararo and M. Sunshine, A Study of a Biased Friendship Net (Syracuse University Press, Syracuse, 1964); J. A. Davis, Human Relations 20, 181 (1967); I. Pool and M. Kochen, Soc. Networks 1, 1 (1978); ibid.J. Skvoretz, 7, 225 (1985).

[c4] C. C. Foster, A. Rapoport, and C. J. Orwant, Behav. Sci. 8, 56 (1963).

[c5] O. Frank and D. Strauss, J. Am. Stat. Assoc. 81, 832 (1986).

[c6] D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998).

[c7] A.-L. Barabási and R. Albert, Science 286, 509 (1999); A.-L. Barabási, R. Albert, and H. Jeong, Physica A 272, 173 (1999); R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 401, 130 (1999).

[c8] For an introduction to graph theory, see for example: R. J. Wilson, Introduction to Graph Theory (Oliver & Boyd, Edinburgh, 1972); G. Chartrand and L. Lesniak, Graphs and Digraphs (Weber and Smith, Boston, 1986).

[c9] M. E. J. Newman, Phys. Rev. E 64, 025102 (2001).

[c10] D. Strauss, SIAM Rev. 28, 513 (1986).

[c11] K. Klemm and V. M. Equíluz, e-print cond-mat/0107606; e-print cond-mat/0107607.

[c12] See the following recent studies, and references therein: S. Redner, Eur. Phys. J. B 4, 131 (1998); S. Bilke and C. Peterson, Phys. Rev. E 64, 036106 (2001); Y. Fang and R. Rosseau, Scientometrics 50, 273 (2001).

[c13] A. R. Puniyani, R. M. Lukose, and B. A. Huberman, e-print cond-mat/0107212.

[c14] J. Davidsen, H. Ebel, and S. Bornholdt, cond-mat/0108302.

[c15] In practice one may use $P_{w} {= (k}_{w} + 1) / \sum_{v \in V} {(k}_{v} + 1),$ to make it possible for disconnected vertices to be connected. This does not change the resultant network geometry significantly.

[c16] S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukin, Phys. Rev. E 63, 062101 (2001).

Physical Review E

Export citation

Export citation

Growing scale-free networks with tunable clustering

Abstract

References (16)

Outline

Information

Filter

Filter

Article Lookup

Enter a citation