Hypergraphs

An implementation of the random preferential attachment hypergraph model with vertex deactivation.

Model

Motivation

The main idea of this model is to generate random hypergraphs whose degree distribution follows a power-law distribution with an exponential cutoff:

P(k) ~ C k-α γk

where C, α and γ are some constant parameters of the distribution.

Such hypergraphs can be used to model real-world collaboration networks, where vertices correspond to authors and hyperedges correspond to publications. It has been observed that collaboration networks expose the presence of the exponential cutoff in their degree distribution.

Basically, the model is a combination of the Avin et al. model [1], which generates scale-free hypergraphs, and the Fenner et al. model [2], which introduces vertex deactivation leading to the appearance of the exponential cutoff.

Description

The model can be described as a 5-tuple H(H0, pv, pe, pd, Y), where

• H0 is the initial hypergraph (we assume that it consist of a single vertex with degree 1);
• pv is the probability of the vertex arrival event;
• pe is the probability of the edge arrival event;
• pd is the probability of the vertex deactivation event;
• Y = (Y1, Y2, ...) is a sequence of random variables, which represent sizes of added hyperedges.

The model is then defined as follows:

• Step t = 0. Initialize the model with H0.

• Step t > 0. Construct a hypergraph Ht from Ht-1 as follows:

  • with probability pv, add a vertex and a preferentially selected hyperedge of size Yt between active vertices of Ht-1,
  • with probability pe, add a preferentially selected hyperedge of size Yt between active vertices of Ht-1,
  • with probability pd, deactivate a preferentially selected active vertex of Ht-1;

Preferential selection means that the probability of selecting a vertex v from a set A is proportional to its degree. That is,

P[v is chosen] = deg v / sum u in A deg u

Usage

The program can be used by simply running

cargo run --release

Additional parameters of the model can be specified after --. Running

cargo run --release -- --help

yields

hypergraphs
Generates a hypergraph according to the random preferential attachment hypergraph model with vertex
deactivation

USAGE:
    hypergraphs.exe <SUBCOMMAND>

FLAGS:
    -h, --help       Prints help information
    -V, --version    Prints version information

SUBCOMMANDS:
    gen     Generates a hypergraph according to the specified model
    help    Prints this message or the help of the given subcommand(s)
    plot    Plots the degree distribution of the specified hypergraph

gen Command

Generates hypergraphs according to the model.

Example

cargo run --release -- gen 0.3 0.49 0.21 3 1000 --save="data/hypergraph" --runs=100 --par

This command generates 100 hypergraphs according to the model with parameters pv = 0.3, pe = 0.49, pd = 0.21 and Y = 3 after t = 1000 steps. Also,

• hypergraphs are saved to files of the format data/hypergraph-{i}.json, where i corresponds to the index of the generated hypergraph;
• hypergraphs are generated in parallel.

Format

A generated hypergraph is saved to a file in the JSON format:

{
  "parameters": {
    "pv": 0.30,
    "pe": 0.49,
    "pd": 0.21,
    "m": 3,
    "t": 1000
  },
  "vertices": 311,
  "edges": [[0], [0, 0, 1], [0, 0, 2], ...],
  "degree": [27, 2, 2, 6, 12, 6, ...],
  "theta": [1.0, 2.5, 3.857142857142857, 6.6, ...]
}

Fields in this format represent the following:

• parameters contains parameters of the model that the hypergraph was generated with;
• vertices is the number of vertices in the hypergraph;
• edges is a list of hyperedges (each hyperedge may contain the same vertex several times);
• degree is a list of degrees of vertices;
• theta is a list of the expected degrees of deactivated vertices:
  • theta[t] = sum of squares of active degrees / sum of active degrees at step t.

plot Command

Plots the degree distribution of a generated hypergraph.

Example

cargo run --release -- plot "data/hypergraph-0.json" --save="hypergraph-0.png"

This command reads a generated hypergraph from the file "data/hypergraph-0.json" and plots its degree distribution. It then saves this plot to a file named "hypergraph-0.png".

References

[1] Chen Avin, Zvi Lotker, Yinon Nahum, and David Peleg. Random preferential attachment hypergraph. In ASONAM ’19: International Conference on Advances in Social Networks Analysis and Mining, Vancouver, British Columbia, Canada, 27-30 August, 2019, pages 398–405. ACM, August 2019. doi:10.1145/3341161.3342867.

[2] Trevor I. Fenner, Mark Levene, and George Loizou. A model for collaboration networks giving rise to a power-law distribution with an exponential cutoff. Social Networks, 29(1):70–80, 2007. doi:10.1016/j.socnet.2005.12.003.

License

This package is licensed under the MIT license.