4
$\begingroup$

I have a network with N nodes and E directed edges. Each edge (Eij) is an integer that represents the number of connections between a source node (Ni) and a target node (Nj).

My null model is that all nodes have an equal probability of being connected. In other words, if we know the in-degree and out-degree of each node, then this information alone is sufficient to estimate the pairwise connectivity among all nodes. For example, if node N1 has 20% of all outgoing connections and N2 has 10% of all incoming connections, then under the null model, edge E12 should represent 2% of the total edge weight within the graph.

However, I expect that some pairs of nodes will be preferentially connected - and these cases are what I would like to discover. For example, perhaps nodes 3 and 7 are always connected (or never connected) with each other - then this would be a departure from the null model. I would like to find a statistical test that can identify these cases, ideally controlling for the rest of the network.

Unfortunately, I am having trouble finding an appropriate statistical test for this situation. If anyone can point me in the right direction, I would really appreciate it.


Update:

One idea is to calculate the in-degree and out-degree of each node, and use these to generate 1000 "random" graphs (for example, by randomly sampling the edges from a multinomial distribution). I could then calculate an empirical p-value for each edge by comparing the true edge weight to those that were randomly generated under the null hypothesis.

Unfortunately, this method fails to account for the overall graph structure. For example, suppose N1 has 20% of all outgoing connections and N2 has 10% of all incoming connections. Under the null model, edge E12 should capture 2% of the total edge weight, but let's say it deviates from the null model and actually captures 10% of the total edge weight. Clearly, the p-value for edge E12 will be significant - but so will the p-values for many other edges, simply because they are all measured relative to each other. Because edge E12 accounts for more connections than expected, other edges in the graph will be forced to have fewer connections than expected.

Therefore, this method does not quite work for my situation (although maybe there is a simple modification that could fix this problem?)

$\endgroup$
0
$\begingroup$

The type of modelling approach that you are describing looks a lot like what exponential random graph models (ERGM) are doing.

In essence, ERGMs are models that attempt to explain network structure. The idea is to understand the processes that lead to the existence of ties in an observed network. In your ERGM, you specify configurations of interest (number of edges, number of reciprocal edges, numbers of triads of a specific type) as parameters and the model estimates coefficients for these parameters given the observed network. The coefficients can be interpreted as whether one observes more (positive coefficient) or less (negative coefficient) of a specific configuration in the observed network than expected in a set of comparable random graphs. For example, if 2 nodes are more likely to be connected because they share characteristic A, you will find a positive coefficient for the homophily effect for characteristic A.

This description is voluntarily non-technical, detailed technical explanation are available in the following book:

Lusher, D., Koskinen, J. and Robins, G. eds., 2013. Exponential random graph models for social networks: Theory, methods, and applications. Cambridge University Press.

R has several packages for the estimation of ERGMs. The ergm package has well developed vignettes with example applications.

The journal Social Networks has published a number of papers using ERGMs in analysis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.