Random graphs, models and generators of scale-free graphs
In this paper various models of random graphs describing real networks arising in different research fields: biology, computer science, engineering, sociology are considered. Particular attention is paid to models describing social networks. We start with observation of classical Erdos-Renyi mode...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ivannikov Institute for System Programming of the Russian Academy of Sciences
2018-10-01
|
| Series: | Труды Института системного программирования РАН |
| Subjects: | |
| Online Access: | https://ispranproceedings.elpub.ru/jour/article/view/1020 |
| _version_ | 1818542863063973888 |
|---|---|
| author | M. M. Bernovskiy N. N. Kuzyurin |
| author_facet | M. M. Bernovskiy N. N. Kuzyurin |
| author_sort | M. M. Bernovskiy |
| collection | DOAJ |
| description | In this paper various models of random graphs describing real networks arising in different research fields: biology, computer science, engineering, sociology are considered. Particular attention is paid to models describing social networks. We start with observation of classical Erdos-Renyi model and basic facts concerning properties of random graphs depending on the value p of the probability of appearance each edge in a graph. Then we observe so-called scale-free model of random graphs proposed by Barabassi and Albert and some its generalizations. Some mathematical results about properties of random graphs in such models are described. For one such model of Bollobas-Riordan we describe results concerning the diameter of random graph, the number of verticies of given degree (power-law distribution) and other different properties. This class of models can be characterized by the property that so-called power law constant cannot be chosen in advance and has one fixed value. For example in Bollobas-Riordan model this constant is 3. Finely we observe more general models of random graphs such as Aiello-Chung-Lu model where the power law constant can be chosen as a parameter. In such models there are interesting results concerning evolution properties of random graphs depending on the value of parameter of power law constant. The main example of such property is the size of maximum clique in random graph which we consider in this paper. |
| first_indexed | 2024-12-11T22:27:44Z |
| format | Article |
| id | doaj.art-8fc20e4b1f744e03825e070d61855880 |
| institution | Directory Open Access Journal |
| issn | 2079-8156 2220-6426 |
| language | English |
| last_indexed | 2024-12-11T22:27:44Z |
| publishDate | 2018-10-01 |
| publisher | Ivannikov Institute for System Programming of the Russian Academy of Sciences |
| record_format | Article |
| series | Труды Института системного программирования РАН |
| spelling | doaj.art-8fc20e4b1f744e03825e070d618558802022-12-22T00:48:14ZengIvannikov Institute for System Programming of the Russian Academy of SciencesТруды Института системного программирования РАН2079-81562220-64262018-10-012201020Random graphs, models and generators of scale-free graphsM. M. Bernovskiy0N. N. Kuzyurin1ФизТехИСП РАНIn this paper various models of random graphs describing real networks arising in different research fields: biology, computer science, engineering, sociology are considered. Particular attention is paid to models describing social networks. We start with observation of classical Erdos-Renyi model and basic facts concerning properties of random graphs depending on the value p of the probability of appearance each edge in a graph. Then we observe so-called scale-free model of random graphs proposed by Barabassi and Albert and some its generalizations. Some mathematical results about properties of random graphs in such models are described. For one such model of Bollobas-Riordan we describe results concerning the diameter of random graph, the number of verticies of given degree (power-law distribution) and other different properties. This class of models can be characterized by the property that so-called power law constant cannot be chosen in advance and has one fixed value. For example in Bollobas-Riordan model this constant is 3. Finely we observe more general models of random graphs such as Aiello-Chung-Lu model where the power law constant can be chosen as a parameter. In such models there are interesting results concerning evolution properties of random graphs depending on the value of parameter of power law constant. The main example of such property is the size of maximum clique in random graph which we consider in this paper.https://ispranproceedings.elpub.ru/jour/article/view/1020случайный графбезмасштабная сетьгенератор случайных графовэрдешболлобашчунгянсонлучак |
| spellingShingle | M. M. Bernovskiy N. N. Kuzyurin Random graphs, models and generators of scale-free graphs Труды Института системного программирования РАН случайный граф безмасштабная сеть генератор случайных графов эрдеш боллобаш чунг янсон лучак |
| title | Random graphs, models and generators of scale-free graphs |
| title_full | Random graphs, models and generators of scale-free graphs |
| title_fullStr | Random graphs, models and generators of scale-free graphs |
| title_full_unstemmed | Random graphs, models and generators of scale-free graphs |
| title_short | Random graphs, models and generators of scale-free graphs |
| title_sort | random graphs models and generators of scale free graphs |
| topic | случайный граф безмасштабная сеть генератор случайных графов эрдеш боллобаш чунг янсон лучак |
| url | https://ispranproceedings.elpub.ru/jour/article/view/1020 |
| work_keys_str_mv | AT mmbernovskiy randomgraphsmodelsandgeneratorsofscalefreegraphs AT nnkuzyurin randomgraphsmodelsandgeneratorsofscalefreegraphs |