Модели сетей с предпочтительным присоединением
Автор: Щербакова Наталья Григорьевна
Журнал: Проблемы информатики @problem-info
Рубрика: Прикладные информационные технологии
Статья в выпуске: 3 (44), 2019 года.
Бесплатный доступ
В статье представлен краткий обзор механизмов генерации и роста, свойственных реальным комплексным сетям. Основное внимание уделено моделям, порождающим масштабноинвариантные сети.
Модели комплексных сетей, масштабно-инвариантные сети, механизм предпочтительного присоединения
Короткий адрес: https://sciup.org/143172475
IDR: 143172475 | УДК: 519.177
Models of networks with preferential attachment
Modeling is one of the methods of analyzing organizational principles of complex networks that define their topology and behavior. Traditionally networks with no apparent design principles were described as random graph that were first studied by Paul Erdos and Alfred Rcnyi fl, 2]. But it is known that the topology of real networks deviates from a random graph and many of them sclf-organizc into scale-free (SF) state. The basic motivation of main theoretical models that come under review in this article is to explain the origin of this scale invariance. The example of a network with in-degree and out-degree power-law distribution is the citation network observed by Derek do Sofia Price in [4, 5]. He discovered that in order the network to have these properties the rate at which a paper gets new citations should be proportional to the number that it already has. He called the process cumulative, advantage.Now it is known as preferential attachmentdue to [6].
Список литературы Модели сетей с предпочтительным присоединением
- Erdos Р., Renyi A. On random graphs // Publicationes Mathematicae Debrecen. V. 6. 1959. P. 290-297.
- Erdos P., Renyi A. On the evolution of random graphs // Bull. Inst. Internat. Statist. V. 38, № 4. 1961. P.343-347.
- Watts D. J., Strogatz S.H. Collective dynamics of "small-world" networks // Nature. 1998. V. 393. P.440-442.
- Price D. J. de Solla. Networks of Scientific Papers // Science. 1965. V. 149. P. 510-515.
- Price D. J. de Solla. A general theory of bibliometric and other cumulative advantage processes // J. of the American Society for Information Science. 1976. V. 27(5-5). P.292-306.
- Barabasi A.-L., Albert R. Emergence of scaling in random networks // Science. 1999. V. 286. P. 509-512.
- Barabasi A.-L., Albert R., Jeong H. Mean-field theory for scale-free random networks // Phvsica A 272. 1999. P. 173-187.
- Albert R., Barabasi A.-L. Statistical mechanics of complex networks // Rev. Mod. Phvs. 2001.V.47, N. 74. P.47-97.
- Dorogovtsev S. N., Mendes J. F. F. Evolution of networks // Advances in Phvs. 2002. V. 51, 1079.
- Dorogovtsev S. N., Mendes J. F. F., Samukhin A. N. Structure of growing network with preferential attachment // Phvs. Rev. Lett. 2000. V. 85, 4633.
- Kullmann L., Kertesz J. Preferential growth: exact solution of the time dependent distributions // Phvs. Rev. E. 63.051112. 2001.
- Krapvisky P.L.,Redner S., Leyvraz F. Connectivity of growing random networks // Phvs. Rev. Lett. V. 85, 4629. 2000.
- Krapvisky P. L., Redner S. Organization of growing random networks // Phvs. Rev. E 63, 066123. 2001.
- Albert R., Jeong H., Barabasi A.-L. Error and attack tolerance of complex networks // Nature. 2000. V.406. P.378-482.
- Albert R., Barabasi A.-L. Topology of evolving networks: local events and universality // Phvs. Review Letters. 2000. V. 85. P. 5234-5237.
- Dorogovtsev S. N., Mendes J. F. F. Scaling behavior of developing and decaying networks // Europhes. Lettr. 2000. V. 52, N. 3. P. 33-39.
- Dorogovtsev S.N., Mendes J.F.F. Evolution networks with aging of sites // Phvs. Rev. E62, 1842. 2000.
- Zhu H., Wang X., Zlli J-Y. The effect of aging on network structure // Phvs. Rev. E 68, 056121. 2003.
- Hajra К. B., Sen P. Phase transitions in an aging network // Phvs. Rev. E 70, 056103. 2004.
- Blanconl g., barabasi a.-l. bose-einstein condensation in complex networks // phvs. rev. lett. 86, 5632. 2001.
- Bianconi G., Barabasi A.-L. Competition and multiscaling in evolving networks // Europhvsics Letters, 54: 436-442, 2001.
- Ergon G, Rodgers G. J. Growing random network with fitness // arXiv: cond-mat/0103423.
- Wang D., Song C., Barabasi A.-L. Quantifying long-term scientific impact // Science. 2013. V.342. P. 127-131.
- Vazquez A. Knowing a network by walking on it: emergence of scaling // arXiv:cond- mat/0006132.
- McGlohon М., Akoglu L., Faloutsos С. Weighted graphs and disconnected components // PAKDDTO Proc. of the 14th Pacific-Asia conference on advances in knowledge discovery and data mining. 2010. Vol. P. 2. P.410-421.
- Kumar R., Raghavan P., Rajagopalan S., Sivakumar D., Tomkins A., Upfal E. Stochastic models for the Web graph // Proc. of the 41th IEEE symp. on foundations of computer science. 2000. P. 57-65.
- Leskovec J., Kleinberg J. M., Faloutsos C. Graph evolution: Densification and shrinking diameters // ACM Transactions on Knowledge Discovery from Data (TKDD). 2007. V. 1, iss. 1. Art. 2.
