re 𝜃(𝐴)∝ℙ𝜃(𝐴)Lθ(A)∝Pθ(A)\mathcal L_\theta(A) \propto \mathbb P_\theta(A);

The reason we write ∝∝\propto instead of === is that, in the case of probability distributions, it is often rather tedious to take care of all constants when simplifying expressions, and these constants can detract from much of the intuition of what is going on. If we instead focus on the likelihood, we only need to worry about the parts of the probability statement that deal directly with the parameters 𝜃θ\theta and the realization itself 𝐴AA.

What does the likelihood for the a priori SBM look like? Fortunately, since 𝜏⃗ τ→\vec \tau is a parameter of the a priori SBM, the likelihood is a bit simpler than for the a posteriori SBM. This is because the a posteriori SBM requires a marginalization over potential realizations of 𝜏𝜏→ττ→\vec{\pmb \tau}, whereas the a priori SBM does not. The likelihood is as follows, omitting detailed explanations of steps that are described above: 𝜃(𝐴)∝ℙ𝜃(𝐀=𝐴)=∏𝑗>𝑖ℙ𝜃(𝐚𝑖𝑗=𝑎𝑖𝑗)Independence Assumption=∏𝑗>𝑖𝑏𝑎𝑖𝑗ℓ𝑘(1−𝑏ℓ𝑘)1−𝑎𝑖𝑗p.m.f. of Bernoulli distribution=∏𝑘,ℓ𝑏|ℓ𝑘|ℓ𝑘(1−𝑏ℓ𝑘)𝑛ℓ𝑘−|ℓ𝑘|Lθ(A)∝Pθ(A=A)=∏j>iPθ(aij=aij)Independence Assumption=∏j>ibℓkaij(1−bℓk)1−aijp.m.f. of Bernoulli distribution=∏k,ℓbℓk|Eℓk|(1−bℓk)nℓk−|Eℓk|\begin{align*} \mathcal L_\theta(A) &\propto \mathbb P_{\theta}(\mathbf A = A) \\ &= \prod_{j > i} \mathbb P_\theta(\mathbf a_{ij} = a_{ij})\;\;\;\;\textrm{Independence Assumption} \\ &= \prod_{j > i} b_{\ell k}^{a_{ij}}(1 - b_{\ell k})^{1 - a_{ij}}\;\;\;\;\textrm{p.m.f. of Bernoulli distribution} \\ &= \prod_{k, \ell}b_{\ell k}^{|\mathcal E_{\ell k}|}(1 - b_{\ell k})^{n_{\ell k} - |\mathcal E_{\ell k}|} \end{align*} Like the ER model, there are again equivalence classes of the sample space <ℎ𝑦𝑝𝑜𝑡ℎ𝑒𝑠𝑖𝑠−ℎ𝑖𝑔ℎ𝑙𝑖𝑔ℎ𝑡𝑐𝑙𝑎𝑠𝑠="ℎ𝑦𝑝𝑜𝑡ℎ𝑒𝑠𝑖𝑠−ℎ𝑖𝑔ℎ𝑙𝑖𝑔ℎ𝑡">𝑛</ℎ𝑦𝑝𝑜𝑡ℎ𝑒𝑠𝑖𝑠−ℎ𝑖𝑔ℎ𝑙𝑖𝑔ℎ𝑡><hypothesis−highlightclass="hypothesis−highlight">An</hypothesis−highlight>\mathcal A_n in terms of their likelihood. Let |ℓ𝑘(𝐴)||Eℓk(A)||\mathcal E_{\ell k}(A)| denote the number of edges in the (ℓ,𝑘)(ℓ,k)(\ell, k) block of adjacency matrix 𝐴AA. For a two-community setting, with 𝜏⃗ τ→\vec \tau and 𝐵BB given, the equivalence classes are the sets: 𝐸𝑎,𝑏,𝑐(𝜏⃗ ,𝐵)={𝐴∈𝑛:11(𝐴)=𝑎,21=12(𝐴)=𝑏,22(𝐴)=𝑐}Ea,b,c(τ→,B)={A∈An:E11(A)=a,E21=E12(A)=b,E22(A)=c}\begin{align*} E_{a,b,c}(\vec \tau, B) &= \left\{A \in \mathcal A_n : \mathcal E_{11}(A) = a, \mathcal E_{21}=\mathcal E_{12}(A) = b, \mathcal E_{22}(A) = c\right\} \end{align*} The number of equivalence classes possible scales with the number of communities, and the manner in which vertices are assigned to communities (particularly, the number of nodes in each community). As before, we have the following. For any 𝜏⃗ τ→\vec \tau and 𝐵BB: If 𝐴,𝐴′∈𝐸𝑎,𝑏,𝑐(𝜏⃗ ,𝐵)A,A′∈Ea,b,c(τ→,B)A, A' \in E_{a,b,c}(\vec \tau, B) (that is, 𝐴AA and 𝐴′A′A' are in the same equivalence class), 𝜃(𝐴)=𝜃(𝐴′)Lθ(A)=Lθ(A′)\mathcal L_\theta(A) = \mathcal L_\theta(A'), and If 𝐴∈𝐸𝑎,𝑏,𝑐(𝜏⃗ ,𝐵)A∈Ea,b,c(τ→,B)A \in E_{a, b, c}(\vec \tau, B) but 𝐴′∈𝐸𝑎′,𝑏′,𝑐′(𝜏⃗ ,𝐵)A′∈Ea′,b′,c′(τ→,B)A' \in E_{a', b', c'}(\vec \tau, B) where either 𝑎≠𝑎′,𝑏≠𝑏′a≠a′,b≠b′a \neq a', b \neq b', or 𝑐≠𝑐′c≠c′c \neq c', then 𝜃(𝐴)≠𝜃(𝐴′)Lθ(A)≠Lθ(A′)\mathcal L_\theta(A) \neq \mathcal L_\theta(A').

What does the likelihood for the a posteriori SBM look like? In this case, 𝜃=(𝜋⃗ ,𝐵)θ=(π→,B)\theta = (\vec \pi, B) are the parameters for the model, so the likelihood for a realization 𝐴AA of 𝐀A\mathbf A is: 𝜃(𝐴)∝ℙ𝜃(𝐀=𝐴)Lθ(A)∝Pθ(A=A)\begin{align*} \mathcal L_\theta(A) &\propto \mathbb P_\theta(\mathbf A = A) \end{align*} Next, we use the fact that the probability that 𝐀=𝐴A=A\mathbf A = A is, in fact, the marginalization (over realizations of 𝜏𝜏ττ\pmb \tau) of the joint (𝐀,𝜏𝜏)(A,ττ)(\mathbf A, \pmb \tau). In the line after that, we use Bayes’ Theorem to separate the joint probability into a conditional probability and a marginal probability: (2.1)¶=∫𝜏ℙ𝜃(𝐀=𝐴,𝜏𝜏=𝜏)d𝜏=∫𝜏ℙ𝜃(𝐀=𝐴∣∣𝜏𝜏=𝜏)ℙ𝜃(𝜏𝜏=𝜏)d𝜏=∫τPθ(A=A,ττ=τ)dτ=∫τPθ(A=A|ττ=τ)Pθ(ττ=τ)dτ\begin{align} &= \int_\tau \mathbb P_\theta(\mathbf A = A, \pmb \tau = \tau)\textrm{d}\tau \nonumber\\ &= \int_\tau \mathbb P_\theta(\mathbf A = A \big | \pmb \tau = \tau)\mathbb P_\theta(\pmb \tau = \tau)\textrm{d}\tau \label{eqn:apost_sbm_eq1} \end{align} Let’s think about each of these probabilities separately. Remember that for 𝜏𝜏ττ\pmb \tau, that each entry 𝜏𝜏𝑖ττi\pmb \tau_i is sampled independently and identically from 𝐶𝑎𝑡𝑒𝑔𝑜𝑟𝑖𝑐𝑎𝑙(𝜋⃗ )Categorical(π→)Categorical(\vec \pi).The probability mass for a 𝐶𝑎𝑡𝑒𝑔𝑜𝑟𝑖𝑐𝑎𝑙(𝜋⃗ )Categorical(π→)Categorical(\vec \pi)-valued random variable is ℙ(𝜏𝜏𝑖=𝜏𝑖;𝜋⃗ )=𝜋𝜏𝑖P(ττi=τi;π→)=πτi\mathbb P(\pmb \tau_i = \tau_i; \vec \pi) = \pi_{\tau_i}. Finally, note that if we are taking the products of 𝑛nn 𝜋𝜏𝑖πτi\pi_{\tau_i} terms, that many of these values will end up being the same. Consider, for instance, if the vector 𝜏=[1,2,1,2,1]τ=[1,2,1,2,1]\tau = [1,2,1,2,1]. We end up with three terms of 𝜋1π1\pi_1, and two terms of 𝜋2π2\pi_2, and it does not matter which order we multiply them in. Rather, all we need to keep track of are the counts of each 𝜋π\pi. term. Written another way, we can use the indicator that 𝜏𝑖=𝑘τi=k\tau_i = k, given by 𝟙𝜏𝑖=𝑘1τi=k\mathbb 1_{\tau_i = k}, and a running counter over all of the community probability assignments 𝜋𝑘πk\pi_k to make this expression a little more sensible. We will use the symbol 𝑛𝑘=∑𝑛𝑖=1𝟙𝜏𝑖=𝑘nk=∑i=1n1τi=kn_k = \sum_{i = 1}^n \mathbb 1_{\tau_i = k} to denote this value: ℙ𝜃(𝜏𝜏=𝜏)=∏𝑖=1𝑛ℙ𝜃(𝜏𝜏𝑖=𝜏𝑖)Independence Assumption=∏𝑖=1𝑛𝜋𝜏𝑖p.m.f. of a Categorical R.V.=∏𝑘=1𝐾𝜋𝑛𝑘𝑘Pθ(ττ=τ)=∏i=1nPθ(ττi=τi)Independence Assumption=∏i=1nπτip.m.f. of a Categorical R.V.=∏k=1Kπknk\begin{align*} \mathbb P_\theta(\pmb \tau = \tau) &= \prod_{i = 1}^n \mathbb P_\theta(\pmb \tau_i = \tau_i)\;\;\;\;\textrm{Independence Assumption} \\ &= \prod_{i = 1}^n \pi_{\tau_i} \;\;\;\;\textrm{p.m.f. of a Categorical R.V.}\\ &= \prod_{k = 1}^K \pi_{k}^{n_k} \end{align*} Next, let’s think about the conditional probability term, ℙ𝜃(𝐀=𝐴∣∣𝜏𝜏=𝜏)Pθ(A=A|ττ=τ)\mathbb P_\theta(\mathbf A = A \big | \pmb \tau = \tau). Remember that the entries are all independent conditional on 𝜏𝜏ττ\pmb \tau taking the value 𝜏τ\tau. This means that we can separate the probability of the entire 𝐀=𝐴A=A\mathbf A = A into the product of the probabilities edge-wise. Further, remember that conditional on 𝜏𝜏𝑖=ℓττi=ℓ\pmb \tau_i = \ell and 𝜏𝜏𝑗=𝑘ττj=k\pmb \tau_j = k, that 𝐚𝑖𝑗aij\mathbf a_{ij} is 𝐵𝑒𝑟𝑛(𝑏ℓ,𝑘)Bern(bℓ,k)Bern(b_{\ell,k}). The distribution of 𝐚𝑖𝑗aij\mathbf a_{ij} does not depend on any of the other entries of 𝜏𝜏ττ\pmb \tau. Remembering that the probability mass function of a Bernoulli R.V. is given by ℙ(𝐚𝑖𝑗=𝑎𝑖𝑗;𝑝)=𝑝𝑎𝑖𝑗(1−𝑝)𝑎𝑖𝑗P(aij=aij;p)=paij(1−p)aij\mathbb P(\mathbf a_{ij}=a_{ij}; p) = p^{a_{ij}}(1 - p)^{a_{ij}}, this gives: ℙ𝜃(𝐀=𝐴∣∣𝜏𝜏=𝜏)=∏𝑗>𝑖ℙ𝜃(𝐚𝑖𝑗=𝑎𝑖𝑗∣∣𝜏𝜏=𝜏)Independence Assumption=∏𝑗>𝑖ℙ𝜃(𝐚𝑖𝑗=𝑎𝑖𝑗∣∣𝜏𝜏𝑖=ℓ,𝜏𝜏𝑗=𝑘)𝐚𝑖𝑗 depends only on 𝜏𝑖 and 𝜏𝑗=∏𝑗>𝑖𝑏𝑎𝑖𝑗ℓ𝑘(1−𝑏ℓ𝑘)1−𝑎𝑖𝑗Pθ(A=A|ττ=τ)=∏j>iPθ(aij=aij|ττ=τ)Independence Assumption=∏j>iPθ(aij=aij|ττi=ℓ,ττj=k)aij depends only on τi and τj=∏j>ibℓkaij(1−bℓk)1−aij\begin{align*} \mathbb P_\theta(\mathbf A = A \big | \pmb \tau = \tau) &= \prod_{j > i}\mathbb P_\theta(\mathbf a_{ij} = a_{ij} \big | \pmb \tau = \tau)\;\;\;\;\textrm{Independence Assumption} \\ &= \prod_{j > i}\mathbb P_\theta(\mathbf a_{ij} = a_{ij} \big | \pmb \tau_i = \ell, \pmb \tau_j = k) \;\;\;\;\textrm{$\mathbf a_{ij}$ depends only on $\tau_i$ and $\tau_j$}\\ &= \prod_{j > i} b_{\ell k}^{a_{ij}} (1 - b_{\ell k})^{1 - a_{ij}} \end{align*} Again, we can simplify this expression a bit. Recall the indicator function above. Let |ℓ𝑘|=∑𝑗>𝑖𝟙𝜏𝑖=ℓ𝟙𝜏𝑗=𝑘𝑎𝑖𝑗|Eℓk|=∑j>i1τi=ℓ1τj=kaij|\mathcal E_{\ell k}| = \sum_{j > i}\mathbb 1_{\tau_i = \ell}\mathbb 1_{\tau_j=k}a_{ij}, and let 𝑛ℓ𝑘=∑𝑗>𝑖𝟙𝜏𝑖=ℓ𝟙𝜏𝑗=𝑘nℓk=∑j>i1τi=ℓ1τj=kn_{\ell k}= \sum_{j>i}\mathbb 1_{\tau_i = \ell}\mathbb 1_{\tau_j = k}. Note that ℓ𝑘Eℓk\mathcal E_{\ell k} is the number of edges between nodes in community ℓℓ\ell and community 𝑘kk, and 𝑛ℓ𝑘nℓkn_{\ell k} is the number of possible edges between nodes in community ℓℓ\ell and community 𝑘kk. This expression can be simplified to: ℙ𝜃(𝐀=𝐴∣∣𝜏𝜏=𝜏)=∏ℓ,𝑘𝑏|ℓ𝑘|ℓ𝑘(1−𝑏ℓ𝑘)𝑛ℓ𝑘−|ℓ𝑘|Pθ(A=A|ττ=τ)=∏ℓ,kbℓk|Eℓk|(1−bℓk)nℓk−|Eℓk|\begin{align*} \mathbb P_\theta(\mathbf A = A \big | \pmb \tau = \tau) &= \prod_{\ell,k} b_{\ell k}^{|\mathcal E_{\ell k}|}(1 - b_{\ell k})^{n_{\ell k} - |\mathcal E_{\ell k}|} \end{align*} Combining these into the integrand from Equation (\ref{eqn:apost_sbm_eq1}) gives: 𝜃(𝐴)∝∫𝜏ℙ𝜃(𝐀=𝐴∣∣𝜏𝜏=𝜏)ℙ𝜃(𝜏𝜏=𝜏)d𝜏=∫𝜏∏𝑘=1𝐾𝜋𝑛𝑘𝑘⋅∏ℓ,𝑘𝑏|ℓ𝑘|ℓ𝑘(1−𝑏ℓ𝑘)𝑛ℓ𝑘−|ℓ𝑘|d𝜏

∫𝜏

ℓ𝑘|ℓ𝑘(

𝑛𝑘=∑𝑛𝑖=1𝟙𝜏𝑖=𝑘nk=∑i=1n1τi=kn_k = \sum_{i = 1}^n \mathbb 1_{\tau_i = k}

𝜏𝜏

<ℎ𝑦𝑝𝑜𝑡ℎ𝑒𝑠𝑖𝑠−ℎ𝑖𝑔ℎ𝑙𝑖𝑔ℎ𝑡𝑐𝑙𝑎𝑠𝑠="ℎ𝑦𝑝𝑜𝑡ℎ𝑒𝑠𝑖𝑠−ℎ𝑖𝑔ℎ𝑙𝑖𝑔ℎ𝑡">𝑝</ℎ𝑦𝑝𝑜𝑡ℎ𝑒𝑠𝑖𝑠−ℎ𝑖𝑔ℎ𝑙𝑖𝑔ℎ𝑡>

Theory

=∏𝑗>𝑖ℙ𝜃(𝐚𝑖𝑗=𝑎𝑖𝑗)

model

Fig. 3.1 The MASE algorithm¶

Well, you could embed

The goal of MASE is to embed the networks into a single space, with each point in that space representing a single node

However, what you’d really like to do is combine them all into a single representation to learn from every network at once.

Non-Assortative Case

silhouette

section

K-means

Lloyd2

a searching procedure until all the cluster centers are in nice places

essentially random places in our data

faster implementation

1

covariates

from statistics

Stochastic Block Model¶

4.2359312775571826e-05 and a maximum weight of 40.00562586173658.

CASE simply sums these two matrices together, using a weight for 𝑋𝑋𝑇XXTXX^T so that they both contribute an equal amount of useful information to the result.

𝑋𝑋𝑇𝑖,𝑗XXi,jTXX^T_{i, j}

.

them

best

With a single network observed (or really, any number of networks we could collect in the real world) we would never be able to estimate 2𝑛22n22^{n^2} parameters. The number grows too quickly with 𝑛nn for any realistic choice of 𝑛nn in real-world data. This would lead to a thing called a lack of identifiability with a single network, which means that we would never be able to estimate 2𝑛22n22^{n^2} parameters from 111 network.

, we would need about 30,000,00030,000,00030,000,000 times the total number of storage available in the world to represent the parameters of a single distribution.

We use a semi-colon to denote that the parameters 𝜃θ\theta are supposed to be fixed quantities for a given 𝐀A\mathbf A.

What is the most natural choice for (Θ)P(Θ)\mathcal P(\Theta) that makes any sense?

t is, in general, good for (Θ)P(Θ)\mathcal P(\Theta) to be fairly rich; that is, when we specify a parametrized statistical model (𝑛,(Θ))(An,P(Θ))(\mathcal A_n, \mathcal P(\Theta)), we want (Θ)P(Θ)\mathcal P(\Theta) to contain distributions that we think faithfully could represent our network realization 𝐴

Note that by construction, we have that |(Θ)|=|Θ||P(Θ)|=|Θ|\left|\mathcal P(\Theta)\right| = \left|\Theta\right|. That is, the two sets have the same number of elements, since since 𝜃∈Θθ∈Θ\theta \in \Theta has a particular distribution ℙ𝜃∈(Θ)Pθ∈P(Θ)\mathbb P_\theta \in \mathcal P(\Theta), and vice-versa.

(Θ)|=|Θ|

So, now we know that we have probability distributions on networks, and a set 𝑛An\mathcal A_n which defines all of the aadjacency matrices that every probability distribution must assign a probability to. Now, just what is a single network model? The single network model is the tuple (𝑛,)(An,P)(\mathcal A_n, \mathcal P). Above, we learned that 𝑛An\mathcal A_n was the set of all possible adjacency matrices for unweighted networks with 𝑛nn nodes. We will call 𝑛An\mathcal A_n the sample space of 𝑛nn-node networks. In general, 𝑛An\mathcal A_n will be the same sample space for all 𝑛nn-node network models. This means that for any 𝑛nn-node network realization 𝐴AA, we can calculate a probability that 𝐴AA is described by any probability distribution on 𝑛An\mathcal A_n found in P\mathcal P. What is P\mathcal P? It depends on the model we want to use! In general, P\mathcal P has only one rule: it is a nonempty set (it contains at least something), where for every ℙ∈P∈P\mathbb P \in \mathcal P, ℙP\mathbb P is a probability distribution on 𝑛An\mathcal A_n. Not that this says only that P\mathcal P cannot be empty, but it doesn’t say anything about how big or diverse it can be! In general, we will simplify P\mathcal P through something called parametrization; that is, we will write P\mathcal P as the set:

{𝐴:𝐴∈{0,1}𝑛×𝑛}

When you see the short-hand expression ℙ(𝐴)P(A)\mathbb P(A), you should typically think back to the most recent random network 𝐀A\mathbf A that has been discussed, and it is typically assumed that ℙP\mathbb P refers to the probability distribution of that random network; e.g., 𝐀∼ℙA∼P\mathbf A \sim \mathbb P.

Is this set the same for any unweighted random network, or is it ever different? It turns out that the answer here is fairly straightforward: for any unweighted random network with 𝑛nn nodes, the set of possible realizations, which we represent with the symbol 𝑛An\mathcal A_n, is exactly the same!

possibly

if 𝐀A\mathbf A is an unweighted random network with 𝑛nn nodes,

topology

random network 𝐀

topology

𝐵

This is an especially common approach when people deal with networks that are said to be sparse. A sparse network is a network in which the number of edges is much less than the total possible number of edges. This contrasts with a dense network, which is a network in which the number of edges is close to the maximum number of possible edges. In the case of an 𝐸𝑅𝑛(𝑝)ERn(p)ER_{n}(p) network, the network is sparse when 𝑝pp is small (closer to 000), and dense when 𝑝pp is large (closer to 111).

Probability that an edge exists between a pair of vertices

0.3

True

True

ps

same

The

unlikely

the model

framework

.3

Structured Independent Edge Model (SIEM)¶

_{s}

$\pmb A \sim ER_n(p)$

Model Selection: The model is appropriate for the data w

Machine Learning

underlies

underlying

Stated another way, even if we believe that the process underlying the network isn’t random at all, we can still extract value by using a statistical model.

underlies

statistics

statistics

Comparing

lives

quantity

not

random

For instance, we might think that

Instead

this

discrimative modeling,

relating to how the network behaves

network

statistics

𝑑dd-dimensions

presentation

well

is that we have

reaization

with which we seek

Statistical modelling is a technique in which

Perhaps

perhaps

is filled with

might

the question that we

A common question as a scientist that we might have is how, exactly, we could describe the network in the simplest way possible

Topology

before

are

are

topology of a network

𝑋

𝑎𝑎aa\pmb a

𝑥𝑖

value

𝑋

generative

might have a slightly different group of friends depending on when we look at their friend circle

we assume that the true network is a network for which we could never observe completely, as each time we look at the network, we will see it slightly differently.

The way we characterize the network is called the choice of an underlying statistical model.

if we know people within the social network are groups of student

What Is A Network?¶ { requestKernel: true, binderOptions: { repo: "binder-examples/jupyter-stacks-datascience", ref: "master", }, codeMirrorConfig: { theme: "abcdef", mode: "python" }, kernelOptions: { kernelName: "python3", path: "./foundations/ch1" }, predefinedOutput: true } kernelName = 'python3'

Preface

$LL + aXX^T$

The p-value determines the probability ofobserving data (or more extreme results), contingenton having assumed the null-hypothesis is true. The formal definition can be expressed as follows: P(X≥ x|H0) or P(X≤ x|H0),