University of Notre Dame
Browse
KharelSR042022D.pdf (27.31 MB)

Degree Preserving Network Growth

Download (27.31 MB)
thesis
posted on 2022-04-08, 00:00 authored by Shubha raj Kharel

Real-world networks evolve over time via the addition or removal of nodes and edges. Their evolution is often constrained by the cost and the capacity of the network elements. The degree of the node representing the node’s capacity to form links is one such dynamical constraint. The degree is simply the number of connections the node has. Maintaining connections bears a cost, due to which the process of creating new connections in physical networks is often accompanied by loss of connection between existing nodes. All current network models largely ignore this mechanism despite the fact that it is prevalent, as we show.

We introduce a novel family of network growth models called ‘Degree Preserving Network Growth’ (DPG), in which new nodes join the network over time without changing the existing node’s degrees. It is a simple stylized model that captures degree preservation and its consequences in network evolution. Key aspects of this model are mathematically tractable, which allows us to understand the rich network structures generated by DPG that are significantly different from those produced by existing models.

We show that DPG can generate the exact structure of most real-world networks despite the NP-hard complexity of such a problem. Moreover, DPG can grow scale-free networks with arbitrary exponents, used extensively in network studies. It does so without any explicit or implicit preferential bias, unlike in all other popular models. DPG can be used to grow networks with desired higher-order metrics (other than the degrees), allowing applications, for example, in epidemic control via network immunization, viral marketing, knowledge dissemination, and the design of molecular isomers with desired properties. Using DPG, we have also discovered a novel connection between prime numbers and graph theory.

History

Date Modified

2022-05-05

Defense Date

2022-03-29

CIP Code

  • 40.0801

Research Director(s)

Zoltán Toroczkai

Degree

  • Doctor of Philosophy

Degree Level

  • Doctoral Dissertation

Alternate Identifier

1313953072

Library Record

6209054

OCLC Number

1313953072

Program Name

  • Physics

Usage metrics

    Dissertations

    Categories

    No categories selected

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC