A random growth model with any real or theoretical degree distribution

Autor: Frédéric Giroire, Stéphane Pérennes, Thibaud Trolliet
Přispěvatelé: Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This work has been supported by the French government through the UCA JEDI(ANR-15-IDEX-01) and EUR DS4H (ANR-17-EURE-004) Investments in the Futureprojects, by the SNIF project, and by Inria associated team EfDyNet., ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), Université Nice Sophia Antipolis (1965 - 2019) (UNS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), EfdyNet, SNIF, ANR-17-EURE-0004,UCA DS4H,UCA Systèmes Numériques pour l'Homme(2017)
Rok vydání: 2023
Předmět:
FOS: Computer and information sciences
Random Growth Model
General Computer Science
Twitter
02 engineering and technology
Poisson distribution
Preferential attachment
Power law
Complex Networks
[INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI]
Theoretical Computer Science
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
symbols.namesake
Random Graphs
020204 information systems
0202 electrical engineering
electronic engineering
information engineering
Statistical physics
Mathematics
Social and Information Networks (cs.SI)
Degree (graph theory)
Preferential Attachment
Computer Science - Social and Information Networks
Function (mathematics)
Complex network
Heavy-Tailed Distributions
Degree distribution
Degree Distribution
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]
symbols
020201 artificial intelligence & image processing
Node (circuits)
Zdroj: COMPLEX NETWORKS 2020-9th International Conference on Complex Networks and their Applications
COMPLEX NETWORKS 2020-9th International Conference on Complex Networks and their Applications, Dec 2020, Madrid / Virtual, Spain
Studies in Computational Intelligence ISBN: 9783030653507
COMPLEX NETWORKS (2)
Theoretical Computer Science
Theoretical Computer Science, 2023, 940 (Part A), pp.36-51. ⟨10.1016/j.tcs.2022.10.036⟩
ISSN: 0304-3975
1879-2294
DOI: 10.1016/j.tcs.2022.10.036
Popis: The degree distributions of complex networks are usually considered to be power law. However, it is not the case for a large number of them. We thus propose a new model able to build random growing networks with (almost) any wanted degree distribution. The degree distribution can either be theoretical or extracted from a real-world network. The main idea is to invert the recurrence equation commonly used to compute the degree distribution in order to find a convenient attachment function for node connections - commonly chosen as linear. We compute this attachment function for some classical distributions, as the power-law, broken power-law, geometric and Poisson distributions. We also use the model on an undirected version of the Twitter network, for which the degree distribution has an unusual shape. We finally show that the divergence of chosen attachment functions is heavily links to the heavy-tailed property of the obtained degree distributions.
Comment: 23 pages, 3 figures
Databáze: OpenAIRE
Externí odkaz: