Introduction to multigraphr

Random stub matching model for multigraphs

The first model is obtained by random stub matching (RSM) given observed degree sequence of a multigraphs, so that edges are assigned to sites given fixed degree sequence \(\mathbf{d}=(d_1, \ldots, d_n)\). The edge assignment probability sequence \(\mathbf{Q}\) is defined as a function of these degrees and the edge assignment probabilities are given by \[\begin{equation} Q_{ij}= \left\{ \begin{array}{ll} \displaystyle \binom{d_i}{2}\bigg/ \binom{2m}{2} & \mbox{for $i=j$}\\ \displaystyle d_id_j\bigg/ \binom{2m}{2} & \mbox{for $i<j$} \ , \end{array} \right . \end{equation}\]

The probability of a multigraph under this model is given by \[\begin{equation}P(\mathbf{M}=\mathbf{m})=\frac{2^{m_2} \binom {m}{\mathbf{m}}}{\binom{2m}{\mathbf{d}}}=\frac{2^{m_2} m! \prod_{i=1}^n d_i!}{(2m)! \prod_{i\leq j} m_{ij}!} \ ,\end{equation}\] where \(m_2=\sum \sum_{i<j}m_{ij}\) (Shafie, 2016).

A <-  matrix(c(1, 1, 0, 
               1, 2, 2, 
               0, 2, 0), 
             nrow = 3, ncol = 3)
A

##      [,1] [,2] [,3]
## [1,]    1    1    0
## [2,]    1    2    2
## [3,]    0    2    0

D <- get_degree_seq(adj = A, type = 'graph')
D

## [1] 3 7 2

rsm_1 <- rsm_model(deg.seq = D)
rsm_1$m.seq

##   M11 M12 M22 M13 M23 M33
## 1   1   1   0   3   0   1
## 2   1   1   0   2   2   0
## 3   1   0   1   3   1   0
## 4   0   3   0   2   0   1
## 5   0   3   0   1   2   0
## 6   0   2   1   2   1   0
## 7   0   1   2   3   0   0

rsm_1$prob.dists

##     prob.rsm loops multiedges simple
## 1 0.03030303     5          1      0
## 2 0.18181818     3          3      0
## 3 0.06060606     4          2      0
## 4 0.06060606     3          3      0
## 5 0.24242424     1          5      0
## 6 0.36363636     2          4      0
## 7 0.06060606     3          3      0

Independent edge assignment model for multigraphs

The second is obtained by independent edge assignments (IEA) according to a common probability distribution. The \(m\) edges of the multigraph are independently assigned to the sites \((i,j)\in \mathcal{R}\) and the edge multiplicity sequence \(\mathbf{M}\) follows a multinomial distribution with parameters \(m\) and \(\mathbf{Q}=(Q_{ij}: (i, j) \in \mathcal{R})\), where \(\mathbf{Q}\) is the edge probability sequence with edge assignment probabilities \(Q_{ij}\) for each site \((i,j)\in \mathcal{R}\) (Shafie, 2015). The probability of a multigraph under this model is given by \[\begin{equation} P(\mathbf{M}=\mathbf{m})= \binom{m}{\mathbf{m}} \mathbf{Q}^{\mathbf{m}} = \frac{m!}{\prod_{i\leq j} m_{ij} !} \prod_{i\leq j}Q_{ij}^{m_{ij}}. \end{equation}\] Moments of certain statistics to analyse multigraph structures are easier derived under this model, facilitating the structural analysis of the multigraphs since the full probability distribution of multigraphs is not needed. Thus, it is of interest to approximate the RSM model by the IEA model. There are two ways in which this can be done:

1. Independent edge assignment of stubs (IEAS)

In order to get an RSM approximation using the IEA model we can simply ignore the dependency between the edge assignments in the RSM model. The distribution of \(\mathbf{M}\) is approximated with the edge probability sequence defined as a function of the fixed degrees \(\mathbf{Q}(\mathbf{d})\). This approximation can be viewed as repeated assignments with replacements of stubs, whereas RSM is repeated assignments without replacement of stubs.

2. Independent stub assignment (ISA)

A Bayesian version of the RSM model is obtained by assigning a prior to the parameter \(\mathbf{d}\), i.e., assuming that the stubs are independently attached to the \(n\) nodes according to a probability distribution \(\mathbf{p}=(p_1, p_2, \ldots, p_n)\) where \(p_i>0\) and \(\sum_{i=1}^np_i = 1\). Thus, is the outcome of a random degree sequence that is multinomial distributed with parameters \(2m\) and \(\mathbf{p}=\mathbf{d}\). Then it follows that the multiplicity sequence \(\mathbf{M}\) has an IEA distribution with edge probability sequence \(\mathbf{Q}(\mathbf{p})\). For the RSM approximation, \(\mathbf{p}=\mathbf{d}/2m\).

The relations between the models are summarized in the below figure:

ieas_1 <-   iea_model(adj = A , type = 'graph',  model = 'IEAS', K = 0, apx = TRUE)
isa_1 <-   iea_model(adj = A , type = 'graph',  model = 'ISA', K = 0, apx = TRUE)
isa_1$nr.multigraphs

## [1] 462

ieas_1$nr.multigraphs

## [1] 462

ieas_2 <-   iea_model(adj = A , type = 'graph', model = 'IEAS', 
                      K = 0, apx = FALSE)

isa_2 <-   iea_model(adj = A , type = 'graph', model = 'ISA', 
                     K = 0, apx = FALSE, p.seq = c(1/3, 1/3, 1/3))

Statistics to analyze structural properties

Several statistics for analyzing the structural properties of multigraphs under the different models are implemented in the package. These include number of loops denoted \(M_1\) and number of non-loops denoted \(M_2\) (indicator of e.g. homophily and heterophily). Other statistics which are only implemented for the IEA model are those part of a so called complexity sequence with the distribution of edge multiplicities. This sequence is given by \(\mathbf{R}=(R_0, R_1, R_2, \ldots, R_m)\) where \[\begin{equation} R_k = \sum \sum_{i<j}I(M_{ij} = k) \ \textrm{ for } \ k = 0,1, \ldots, m \ , \end{equation}\] and \(I\) is an indicator variable. Thus, \(R_0\) denotes the number of vertex pair sites with no edge occupancy, \(R_1\) single edge occupancy, \(R_2\) double edge occupancy, and so forth. These statistics are useful as an indicator of e.g. multiplexity/interlocking.

Approximate 95% interval estimates for these statistics are given by \(\hat{E} \pm 2\sqrt{\hat{V}}\).

rsm_1$M

##              M1    M2
## Expected  2.273 3.727
## Variance  0.986 0.986
## Upper 95% 4.259 5.713
## Lower 95% 0.287 1.741

ieas_1$M

##               M1    M2
## Observed   3.000 3.000
## Expected   2.273 3.727
## Variance   1.412 1.412
## Upper 95%  4.649 6.104
## Lower 95% -0.104 1.351

ieas_1$R

##              R0     R1     R2
## Observed  2.000  2.000  2.000
## Expected  2.674  1.588  1.030
## Variance  0.575  1.129  0.760
## Upper 95% 4.191  3.713  2.773
## Lower 95% 1.156 -0.537 -0.713

isa_1$M

##              M1    M2
## Observed  3.000 3.000
## Expected  2.583 3.417
## Variance  1.471 1.471
## Upper 95% 5.009 5.842
## Lower 95% 0.158 0.991

isa_1$R

##              R0     R1     R2
## Observed  2.000  2.000  2.000
## Expected  2.599  1.703  1.018
## Variance  0.622  1.223  0.748
## Upper 95% 4.176  3.915  2.748
## Lower 95% 1.021 -0.509 -0.711

Goodness of fit tests

Goodness of fits tests of multigraph models using Pearson (\(S\)) and information divergence (\(A\)) test statistics under the random stub matching (RSM) and by independent edge assignments (IEA) model, where the latter is either independent edge assignments of stubs (IEAS) or independent stub assignment (ISA). The tests are performed using goodness-of-fit measures between the edge multiplicity sequence of a specified model or an observed multigraph, and the expected multiplicity sequence according to a simple or composite hypothesis.

Tests of a simple multigraph hypothesis

The following test statistics are used when edge multiplicities according to \(\textrm{IEA}(\mathbf{Q})\) and correct model \(\mathbf{Q_0}=\mathbf{Q}\) is tested:

• the Pearson statistic \[S_0=\sum\sum_{i \leq j}\frac{(M_{ij}-mQ_{0ij})^2}{mQ_{0ij}}=\sum\sum_{i \leq j}\frac{M_{ij}^2}{mQ_{0ij}}-m \stackrel{asymp}{\sim} \chi^2(r-1)\]

• the divergence statistic \[D_0=\sum\sum_{i\leq j}\frac{M_{ij}}{m} \log \frac{M_{ij}}{mQ_{0ij}} \quad \textrm{and} \quad A_0=\frac{2m}{\log \textrm{e}}D_0 \stackrel{asymp}{\sim} \chi^2(r-1)\]

Tests of a composite multigraph hypothesis

The composite multigraph hypotheses are ISA for unknown \(\mathbf{p}\) and IEAS for unknown \(\mathbf{d}\) where parameters have to be estimated from data \(\mathbf{M}\).

When the correct model is tested, the statistics are given by

• the Pearson statistic \[\hat{S}=\sum\sum_{i \leq j}\frac{(M_{ij}-m\hat{Q}_{ij})^2}{m\hat{Q}_{ij}}=\sum\sum_{i \leq j}\frac{M_{ij}^2}{m\hat{Q}_{ij}}-m \stackrel{asymp}{\sim} \chi^2(r-n)\]

• the divergence statistic \[\hat{D}=\sum\sum_{i\leq j}\frac{M_{ij}}{m} \log \frac{M_{ij}}{m\hat{Q}_{ij}} \qquad \textrm{and} \quad \hat{A}=\frac{2m}{\log \textrm{e}}\hat{D}\stackrel{asymp}{\sim} \chi^2(r-n)\]

Example

Simulated goodness of fit tests for multigraphs with n=4 nodes and m=10 edges (be patient, these take a while to run).

(1) Testing a simple IEAS hypothesis with degree sequence (6,6,6,2) against a RSM model with degrees (8,8,2,2):

gof1 <- gof_sim(m = 10, model = 'IEAS', deg.mod = c(8,8,2,2), 
                hyp = 'IEAS', deg.hyp = c(6,6,6,2))

(2) Testing a correctly specified simple IEAS hypothesis with degree sequence (14,2,2,2):

gof2 <- gof_sim(m = 10, model = 'IEAS', deg.mod = c(14,2,2,2), 
                hyp = 'IEAS', deg.hyp = c(14,2,2,2))

The non-null (gof1) and null (gof2) distributions of the test statistics together with their asymptotic chi2-distribution can be visualized using e.g. ggplot2:

(3) Testing a composite IEAS hypothesis against a RSM model with degree sequence (14,2,2,2):

gof3 <- gof_sim(m = 10, model = 'RSM', deg.mod = c(14,2,2,2), 
                hyp = 'IEAS', deg.hyp = 0)

(4) Testing a composite ISA hypothesis against a ISA model with degree sequence (14,2,2,2):

gof4 <- gof_sim(m = 10, model = 'ISA', deg.mod = c(14,2,2,2), 
                hyp = 'ISA', deg.hyp = 0)

The non-null (gof3) and null (gof4) distributions of the test statistics can then be visualized as shown above to check their fit to the asymptotic \(\chi^2\)-distribution.

Example

All edge multiplicity sequences/multigraph with 2 nodes and 4 edges

r <- (2*3)/2 # vertex pair sites (or length of edge multiplicity sequences)
mg <- nsumk(r,4) # number of rows give number of possible multigraphs
mg

##       [,1] [,2] [,3]
##  [1,]    0    0    4
##  [2,]    0    1    3
##  [3,]    0    2    2
##  [4,]    0    3    1
##  [5,]    0    4    0
##  [6,]    1    0    3
##  [7,]    1    1    2
##  [8,]    1    2    1
##  [9,]    1    3    0
## [10,]    2    0    2
## [11,]    2    1    1
## [12,]    2    2    0
## [13,]    3    0    1
## [14,]    3    1    0
## [15,]    4    0    0

The function get_edge_assignment_probs can be used to calculates the edge assignment probabilities \(\mathbf{Q}\) given specified degree sequence under the two ways in which the RSM model can be approximated by the IEA model.

Example

Under the IEAS model with 10 possible vertex pair sites (4 nodes), the edge assignment probabilities are given by

Q <- get_edge_assignment_probs(m = 8, deg.seq = c(4,4,4,4), model = 'IEAS')
Q

##  [1] 0.0500000 0.1333333 0.1333333 0.1333333 0.0500000 0.1333333 0.1333333
##  [8] 0.0500000 0.1333333 0.0500000

Given a degree sequence, the function get_edge_multip_seq can be used to find all unique edge multiplicity sequences as rows in a data frame. Each row in the data frame represents a unique multigraph given the degree sequence. This is useful if you need to find the full outcome space of multgraphs under the IEA model (but only practical and readable for small multigraphs)

Example

To find all multigraphs with degree sequence \((4,2,2)\)

mg <- get_edge_multip_seq(deg.seq = c(4,2,2))
mg

##   M11 M12 M22 M13 M23 M33
## 1   2   0   0   1   0   1
## 2   2   0   0   0   2   0
## 3   1   2   0   0   0   1
## 4   1   1   1   0   1   0
## 5   1   0   2   1   0   0
## 6   0   2   2   0   0   0