Preferential Attachment with Flexible Heavy Tails

Thomas Boughen
t.w.boughen1@newcastle.ac.uk

Newcastle Univeristy

Clement Lee
Clement.Lee@newcastle.ac.uk

Newcastle Univeristy

Vianey Palacios Ramirez
vianey.palacios-ramirez@newcastle.ac.uk

Newcastle Univeristy

June 27, 2025

Areas of Focus

Mechanistic Models

  • e.g. Forest fire, preferential attachment (PA) , duplication divergence
  • Model behaviour of individual nodes and edges over time

Degree Distributions

  • e.g. Power Laws, tail estimation, mixture models
  • Model feature of a network structure, usually at a snapshot in time

Mechanistic Models

Preferential Attachment

Steps

  1. Node added to network
  2. Connects to existing nodes with weights \(\pi_i\): \[ \pi_i\propto b(k_i), \] where \(k_i\) is degree of node \(i\).

Preference Function

\[ \begin{gather} b(k) = k^\alpha \end{gather} \]

\(0<\alpha<1\)

Not scale-free

\(\alpha=1\)

Scale-free

\(\alpha>1\)

Winner takes all

Mechanistic Models

+

  • Can achieve complex behaviour with simple rules
  • Can gain insight into individual behaviour
  • If able to fit, can create predictions for network growth

-

  • Can be hard to fit, full evolution often not available

Modelling Degrees

Power Law

Tail Estimation

Mixture Model

Mixture Model [1]

Zipf-Polylog

\[ f(k) \propto x^{-\alpha} \theta^x, \qquad x=1, 2, \ldots, u \]

Integer Generalised Pareto

\[ f(k)\propto 1-\left(1+\frac{\xi(k-u)}{\sigma +\xi u}\right)_+^{-1/\xi}, \qquad x=u+1,\ldots \]

Modelling Degrees

+

  • Easy to fit
  • Learn about (in)equality between nodes

-

  • Learn nothing about network growth
  • Degrees aren’t everything

Returning to Preferential Attachment

Propose preference function of the form:

\[ b(k) = \begin{cases} k^\alpha + \varepsilon, &k\le k_0,\\ (k_0^\alpha + \varepsilon) + \beta(k-k_0), &k\ge k_0. \end{cases} \]

Limiting Degree Distribution [2]

\[ \bar F(k) = \prod_{i=0}^k\frac{b(i)}{\lambda^* + b(i)} \]

  • Heavy-tailed for all parameter choices

  • Allows sub/super-linear behaviour

  • Tail over \(k_0\) approximately discrete GP

Fitting Simulated Data

Simulating data

  • 100,000 nodes
  • 36 parameter combinations
  • \(k_0\) fixed at \(20\)
  • Only using final degrees

The results

\(\alpha\) posterior

The results

\(\varepsilon\) posterior

The results

\(k_0\) posterior

The results

\(\beta\) posterior

Real Data

Internet

Flights

Proteins

Data sourced from Network Data Repository[3]

We will fit the model and compare it to the mixture model.

Fitting to Real Data

Bonus Information

Conslusion

Summary

  • Preference function
    • Guarantees flexible heavy tail
    • Allows for sub/super-linear behaviour
  • Parameters can be recovered from degrees of snapshot
  • Performs similarly to existing degree modelling

Discussion

  • Could consider more than degrees
  • Model could be made more realistic
  • Results beyond trees?

Thank you for listening!

Preprint

Contacts

Thomas Boughen*

(t.w.boughen1@ncl.ac.uk)

Clement Lee

(Clement.Lee@ncl.ac.uk)

Vianey Palacios Ramirez

(vianey.palacios-ramirez@ncl.ac.uk)

References

1.
Lee C, Eastoe EF, Farrell A (2024) Degree distributions in networks: Beyond the power law. Statistica Neerlandica 78(4):702–718. https://doi.org/10.1111/stan.12355
2.
Rudas A, Tóth B, Valkó B (2007) Random trees and general branching processes. Random Structures & Algorithms 31(2):186–202. https://doi.org/10.1002/rsa.20137
3.
Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. In: AAAI