# Network centrality in a set of networks with shared nodes

I have a set of weighted networks, each represented as a complete graph composed of nodes and connections with weights (see also "weighted networks" on Wikipedia). All networks share the same nodes and the connection weights differ from network to network.

My goal is to identify nodes that consistently (across the whole set) show high node strength* and express this consistency using statistical significance.

* Node strength is the sum of weights of all connections a node participates in.

Think of the following three examples:

1. A network whose nodes are countries and whose weights represent the amount of trade in a particular commodity between any two countries. It's possible to create such a network for many commodities and arrive at a set of networks.
2. A network whose nodes are brain regions and whose weights represent how well they are connected with white matter tracts. It's possible to create such a network for many subjects.
3. A network whose nodes are particles and whose weights represent the interacting forces between particles. It's possible to sample the state of the interacting forces at multiple times and arrive at a set of networks.

For simplicity, we can think of the weights as being normalized to a [0,1] range in each network. Moreover, the number of nodes in my networks is in the order of thousands.

It's easy to calculate node strength for each node in every network of the set, and calculate its mean and variance across the set. However, I struggle in expressing the statistical significance of "being strongly connected" across all networks in the set. In other words, I struggle in being able to show/disprove that while each network in the set might be slightly different, the most connected nodes remain approximately the same.

UPDATE

I'd like to put forward two ideas how to approach this.

Approach 1:

1. Take a network, compute node strength of all nodes in the network and transform them into z-scores, i.e., subtract mean strength and divide by standard deviation of node strengths. Repeat this process for all networks in the set.
2. For each node, run a one-sample t-test, with the alternative hypothesis being that the mean z-score of node strength of the node is larger than 0. Raise the p-threshold until a given percentage of nodes remains (e.g. 10%).
3. The remaining 10% of are the most connected nodes across the whole set of networks, i.e., they are the top nodes whose strength is significantly different from 0 (i.e. the mean node strength) at the given p-level.*

* The p-level can be corrected for multiple comparisons. However, since I will always take the top 10%, I believe it's not so important.

Approach 2 (proposed by Benjamin in the comment below):

Convert node strengths to percentiles and put a confidence interval around them. Then pick nodes whose confidence intervals consistently exceed a pre-determined threshold (e.g., 90%).

I believe that the methods will probably arrive at different solutions. Since I'm interested in identifying the most connected nodes across the set (and sorry for not being clear about this earlier), I prefer approach 1. Is it a valid approach? If not, can you sketch a different method?

• Maybe convert the centrality scores into percentiles, take the mean for each node across the networks, and put a confidence interval around it (based on the standard deviation or a bootstrap). If that confidence interval consistently exceeds a threshold (e.g., .95%), then call it a "hub." – BenjaminLind Nov 20 '14 at 18:58
• @BenjaminLind Let's say you had a network with 1000 nodes each with a centrality score contained in a 1000 element vector. You can calculate percentiles but I don't understand how to create confidence intervals from that? If you could explain that would be very helpful. Thanks :) – O.rka Mar 8 '18 at 17:37

Let me stick to your desiderata of proving the statistical significance of the difference between the hubs and the non-hubs. I believe by that you mean that all the hubs are statistically different than the non-hubs.

So you cannot avoid doing all pairwise comparisons. Since there will be many of those you should be careful in choosing the multiple comparison procedure. Also, your data is paired so if possible you should make use of that - otherwise you loose power, and the set of hubs will be smaller than it should. If you can assume that the the node strength for each node is normally distributed across all networks you can use a parametric test, see http://en.wikipedia.org/wiki/Post-hoc_analysis I usually prefer the Holm method and it can be used in a pairwise comparison (as far as I remember).

If the data for each node is not normally distributed, then the only pairwise multiple comparison method I know is the Nemenyi test (see for example http://www.researchgate.net/post/Which_Statistical_test_is_most_applicable_to_Nonparametric_Multiple_Comparison).

So I would order all node strengths, and compute a multiple comparison among all of then. And then go up the list of nodes (from lower to higher strength) and select the first for which all nodes above (higher strength) or equal are significantly different than the ones below.

It could also be the case that you want that the mean of the strengths of the hubs is significantly different than mean of the non-hubs. In this case you will need a multiple comparison procedure that allow for contrasts. As far as I know only Scheffe method (parametric) allow it. But in this case you will need a different way of computing a candidate hub set, so that you can set the contrast that distinguished the hubs from the non-hubs.

this might be too simplistic but why not use something like Kruskal-Wallis (or any unbalanced anova-type test) to see if one set of scores (one node) consistently dominates? App1 is not incorrect but is very convoluted, also note that (1.2) might be sensitive to the number of observations/node.

• I'd like to identify not just a single node, but a group of nodes, say the top 10%. How would you go about doing that after running Kruskal-Wallis? Using Dunn's test? – John Manak Nov 25 '14 at 13:20
• KW would tell you whether any of the nodes are significantly better. If that isn't of interest, why not just rank, or z-score as you suggest, all nodes/network, then choose top 10% with highest ranks? – katya Nov 25 '14 at 20:18
• Because I would like to somehow ensure reliability across individual networks. – John Manak Nov 26 '14 at 6:35
• Alternatively, use a Hotelling T2 Test? – Sue Doh Nimh Nov 26 '14 at 12:04

Is there any significance to the upper bound for weights on different networks? I.e. if we take the simplification to [0,1], are we eliminating any significant information about networks where max weights are stronger?

If not, you could model the 'adjacency' between each (i,j) as a beta distribution on [0,1], with the two parameters alpha and beta being the 'agreeability' of nodes i and j. You'd end up with n parameters to estimate (as the alpha for node i will be the beta for some other node k) and an ML formulaton to be solved over (n(n-1)/2)*m datapoints. (m being the number of networks).

• Thanks! However, how would you do the statistical inference regarding the reliability of the centrality measures across networks in this model? – John Manak Nov 26 '14 at 10:45
• The method I'm proposing isn't to deduce centrality, it's to produce a parameter which could be interpreted as an index of a given node's 'attractiveness'. Are you interested in some population value of a particular centrality measure? You might want to look into knife-edging the data. Here's a useful paper, you can easily generalise it to multiple networks (this can be applied to any statistic, including node strength): stats.ox.ac.uk/~snijders/Snijders_Borgatti.pdf – Sue Doh Nimh Nov 26 '14 at 12:02