Graph View

Backlinks

The Library

Search

SearchSearch

Fundamental Constructs of Network Science

Sep 25, 2024, 6 min read

Important Quantities

  • The degree probability denoted is given as follows

    • is a normalizing constant. Usually, this may be given as the average degree
    • is the probability that any node has degree .

  • The link probability is the probability that a link exists between two nodes.

  • The Degree Distribution is a probability distribution that provides the probability that a randomly selected node in the graph has degree . This is denoted

    • It can be obtained using Frequentist Statistics. Let denote the number of nodes in the network with degree , and the total nodes. Then

    • A hub is a node in the network whose number of links greatly exceeds the average degree

    • The natural cutoff of a degree distribution is the maximum degree, denoted . This arises from the finite nature of most graphs.

    • The structural cutoff imposes a degree cutoff in the degree distribution

      More formally, we define the structural cutoff as

      Where is the number of links between nodes of degrees and (allowing for double counting). This is given by

      is the largest possible value of which is

      Where represents the probability of having a node with degree .

      The structural cutoff is defined such that

      • Realistically . However, in real networks this value can exceed 1 which indicates a structural problem within the network
      • Hence the point Is where we define the cutoff where the network is structurally sound (i.e., the structural cutoff).

  • The degree exponent of a power law is the exponent found in the power law. More specifically if

    then is the degree exponent

  • The link similarity involving vertices of a graph is calculated as

    Where denotes the neighborhood of including itself.

    • The formula is really a variation of the Jaccard Index.
    • A high link similarity indicates that a link tends to connect to the same group of nodes.

  • Network Degree Correlation.

  • Network Communities

  • Let be a graph. The Global Clustering Coefficient denoted . It is defined as the total number of closed triangles in the graph.

    Where the number of connected triples is an ordered set where vertices connects to and connects to .

Characteristics of Networks

  • A network property is any property of a network. Usually it is something that can be described with a monotonic sequence

    • If some subgraph has the property, then any network that contains this subgraph has this property.

    • Property does not hold if

    • Property holds if

    • For a network and network property , a threshold function is a function that satisfies

    • A phase transition for property occurs at a point such that given a threshold function and a network property —

      • If then the property does not hold. We call this region a subcritical region
      • If , then the property does hold. We call this region a supercritical region.

  • A network is exponentially bounded if its degree distribution decreases exponentially or faster for higher degrees.

    • As a consequence we have that
    • Here, the degrees of the network do not have variations
    • Examples: Erdos-Renyi model; Watt-Strogatz model.

  • A network is fat tailed if it has a fat tail in the region corresponding to high degree nodes

    • As a consequence, we have that
    • We expect outliers or exceptionally high-degree nodes in the network.
    • Most networks that fall under this classification are scale-free

Classes of Network Models

  • A static network model is a model for a network where the number of nodes is fixed, and we simply place the links between the nodes.

    • The degree distribution of a static network model is bounded.

  • The Evolving Network Model is a model that captures the time evolution (i.e., growth) of a network.

  • A generative network model is a model where we generate a network with a predefined degree distribution.

    • These models help us understand the relationship between various properties of the network with its degree distribution
    • The configuration model allows us to generate a random network with pre-defined degree sequence by performing rewritings in the network.
    $$

    p_{ij}=\frac{k_ik_j}{2L-1}
$$
    * The obtained network will contain loops and multi-edges. 
    * This model is desirable if we have a simple degree distribution
    • The hidden parameter model is an algorithm that generates a random network with predefined degree sequence but without loops or multi edges
      • Start with isolated nodes and assign each hidden parameter . This hidden parameter can be sampled using either of the following
        • From a predefined distribution
        • From a deterministic sequence
      • This model is desirable if we do not know the average degree and want to generate a degree distribution with this average degree
      • A scale free network can be generated using the sequence

Miscellaneous

  • Degree Preserving Randomization is an algorithm that ensures a generated network has nodes with degrees that follow a given degree sequence.
    • The idea is as follows: Simply, select two links and swap them, assuming that no multi-links will be created. The degree of the nodes involved in the swap remain unchanged so that hubs remain hubs and small-degree nodes remain small.
    • Effectively, under this process, we follow the degree sequence, but change the wiring of the network itself.
    • This model is desirable if we want to generate a network with exactly the same degree sequence as the input.

Links