Null Models

Most segregation and polarization measures contain a null model that compares the excess polarization in the observed network. The most basic example can be given from Freeman’s segregation index, which calculates the excess ratio of cross-group tie density. Most of the measures assume a random graph with the same edge density as the observed network to quantify the excess polarization. If a measure contains a null model, it basically aims to return 0 when the observed network’s segregation is similar to a random network with the same edge density.

netseg allows picking your own null models, adjusting the null model of the original metric, or adding a null model difference calculation. These null models might contain graphs with a similar degree distribution (Salloum, 2024) or counterfactual simulations directly generated from a statistical model such as an Exponential Random Graph Model (Duxbury, 2023).

The following lists the measures and indicates whether they inherently contain a null model:

Metric Name	Year	Contains a Null Model
Boundary Connectivity	2013	True
Random Walk Controversy	2018	False
Dipole Moment	2015	False
Freeman’s Segregation Index	1978	True
Krackhardt E-I	1988	False
Segregation Matrix Index	1997	False
Coleman’s Homophily Index	1958	True
GAM Index	1989	False
ORWG	2001	True
Spectral Segregation Index	2007	False
Assortativity	2003	True

If a metric contains a null model, netseg measures the score in the given null model list and changes the value accordingly; if it does not contain a null model, netseg directly returns the excess amount of segregation compared to a null model. netseg explicitly avoids double subtraction that subtracts a null model’s score from a metric with a null model. A few examples can be given as follows:

Boundary Connectivity: In the case of boundary connectivity, it quantifies the spread of the cross-group edges and inner-group edges of the nodes in the boundary. The value 0.5 in the following equation:

\[P = \frac{1}{|B|} \sum_{v \in B} \left[ \frac{d_i(v)}{d_b(v) + d_i(v)} - 0.5 \right]\]

represents equally distributed edges between inner and outer groups. Hence, it serves as a baseline. For example, netseg allows you to change this parameter from a given list of ig.Graph objects. Notice that netseg will use the original membership of the nodes in the observed graph; hence, you do not have to state the membership again.

from netseg import boundary_connectivity
import igraph as ig 
def make_symmetric_sbm(p_in, p_out, n_groups, nodes_per_group, membership, **kwargs):
    pref_matrix = [
        [p_in if i == j else p_out for j in range(n_groups)] 
        for i in range(n_groups)
    ]
    block_sizes = [nodes_per_group] * n_groups
    g = ig.Graph.SBM(pref_matrix, block_sizes, **kwargs)
    
    g.vs['membership'] = membership
    
    return g 

membership = [0 if i < 100 else 1 for i in range(200)]
g_simple = make_symmetric_sbm(0.4, 0.03, 2, 100, membership )
bc_score_embedded_null = boundary_connectivity("membership", g_simple)
null_models = [make_symmetric_sbm(0.4, 0.03, 2, 100, membership ) for i in range(10)]
bc_score_similar_graphs = boundary_connectivity("membership", g_simple, null_models= null_models)

print("=" * 30)
print("BC Score with Embedded Null:", bc_score_embedded_null)
print("=" * 30)
print("BC Score with Similar Graphs as Null: ", bc_score_similar_graphs)
print("=" * 30)

==============================
BC Score with Embedded Null: 0.46549762535721495
==============================
BC Score with Similar Graphs as Null:  -0.0035322612611077275
==============================

Since we are giving similar graphs as an ensemble of null models, netseg returns a value of approximately zero.

Random Walk Controversy: For example RWC does not contain any null models, hence if an ensemble of graphs are given, netseg will calculate the difference between the given graphs’ RWC score and the observed network’s RWC score on average.

from netseg import random_walk_controversy

rwc_score_without_null = random_walk_controversy("membership", graph  = g_simple, maximum_walk_length= 1000, n_sim= 10000, k_top= 10, balanced= True)
rwc_score_similar_graphs = random_walk_controversy("membership", graph  = g_simple, maximum_walk_length= 1000, n_sim= 10000, k_top= 10, balanced= True, null_models=null_models)

print("=" * 30)
print("RWC Score with Embedded Null:", rwc_score_without_null)
print("=" * 30)
print("RWC Score with Similar Graphs as Null: ", rwc_score_similar_graphs)
print("=" * 30)

==============================
RWC Score with Embedded Null: 0.38069741977862753
==============================
RWC Score with Similar Graphs as Null:  -0.031161674907683068
==============================

This leads to the possibility of measuring segregation in counterfactual simulations. For example, if you have a network that might be formed due to a myriad of factors, you can create what-if scenarios to measure segregation with certain statistical network models (e.g., you can measure the contribution of triadic closure to the final segregation score (Duxbury, 2023) or homophily across different exogenous nodal attributes).

It is important to note that each graph in the ensemble will increase the calculation time for the metrics, since the metric itself needs to be calculated on the given null graph (\(M \times \text{Original Complexity of the Metric}\)). Currently, only Boundary Connectivity supports parallel computation; nonetheless, this approach is still experimental and is not useful for small graphs. It is recommended only for very large individual graphs. For an ensemble of many small-to-medium graphs, serial execution is typically much faster, since when utilizing multiprocessing, Python must package (pickle) the C-backed igraph objects to send them across process boundaries via Inter-Process Communication (IPC), and the worker processes must unpackage (unpickle) them. For a large ensemble of small-to-medium graphs, the memory overhead and time required to serialize and deserialize these objects vastly exceed the time saved by parallelizing the mathematical operations. Nonetheless, in the future, it might be implemented for certain other measures.

References

• Duxbury, Scott W. “Micro effects on macro structure in social networks.” Sociological Methodology 54.1 (2024): 1-26.

• Salloum, Ali, Ted Hsuan Yun Chen, and Mikko Kivelä. “Separating polarization from noise: comparison and normalization of structural polarization measures.” Proceedings of the ACM on human-computer interaction 6.CSCW1 (2022): 1-33.