3.6 Block Models

Random Network Models:

  • Erdos-Renyi
    • Useful for understanding thresholds and how networks come to exhibit certain features
    • Miss many real-world features: e.g., clustering
  • other models link-by-link models
    • Watts and Strogatz, Barabasi and Albert, Jackson and Rogers...
    • Capture other features: clustering, degree distribution, correlation...
  • Stochastic Block Models
    • Enrich Erdos-Renyi to allow for probabilities to depend on node characteristics, attributes(or on latent - unobserved characteristics)
  • Popular set of models: ERGMs and new ones: SERGMs/SUGMs
    • flexible way to introduce various local features and dependencies
    • estimated statistically

Block model

Extend the basic Erdos-Renyi G(n, p) model:

Nodes have characteristics: e.g., age, gender, religion, profession, etc. links between nodes depend on the pairs' characteristics. So people of similar ages are more likely to link than people of different ages, people of similar religions and so forth.

Networks with attributes

Block models

Continuous covariates:

For instance, we keep track of age in days or in fractions of years, then we would have instead of just green yellow and blue, we might have people that are 34 and half years old and people that are 60 years old and so forth.

Example: link between i and j depends on their characteristics:

$\beta_iX_i + \beta_jX_j + \beta_{ij}|X_i - X_j|$

E.g. log of probability that there's a link between i and j compared to the probability that there's not a link between i and j:

$log(p_{ij}/(1 - p_{ij})) = \beta_iX_i + \beta_jX_j + \beta_{ij}|X_i - X_j|$

Now it's a more complicated stochastic model, but one that still very easy to go ahead and estimate, and you can use this in most any standard statistics package or allow you to do logistic regressions.

Could use this sort of model to test for homophily...

What is missed?

  • Likelihood of link depends on node attributes (observed or latent)
  • also depends on whether nodes have friends in common
    • A and B both have a common friend C makes it more likely that they are going to be linked to each other than if they didn't have a friend in common