# What does it mean when all edges in a real-world network/graph are statistically just as likely to happen by chance?

I've been using the backbone network extraction method outlined in this paper: http://www.pnas.org/content/106/16/6483.abstract

Basically, the authors propose a method based in statistics that produces a probability, for each edge in the graph, that the edge could have happened just by chance. I use the typical statistical significance cutoff of 0.05.

I've been applying this method to several real-world networks, and interestingly some networks end up with no edges as significant. I'm trying to understand what this entails for the network. The only other time I've applied the method to a network and had no edges come out as significant was when I applied the method to random networks that I generated, which is exactly what we'd expect.

As an example real world network, you may have seen the recent network visualization that went on The Economist showing the polarization of the U.S. Senate in the past 25 years: http://www.economist.com/news/united-states/21591190-united-states-amoeba. I applied the backbone network extraction method to those networks and no edges came up as significant. Even though the raw edges apparently show preferential attachment and clustering, is this just by chance? Is the Senate voting network network essentially random?

The null hypothesis behind backbone methods is

[The] normalized weights that correspond to the connections of a certain node of degree k are produced by a random assignment from a uniform distribution.

If there aren't any "significant" edges, the null hypothesis holds for the entire graph, i.e., edge weights result from nodal propensities to send and receive ties.

Depending on the relationships you're analyzing, the backbone method might not be appropriate. The method works best for networks that are conceptually one-mode weighted networks. Two-mode networks can be projected as a weighted one-mode network, but it often doesn't make sense to do so.

Drawing upon your example in the Economist, it doesn't make sense to analyze Senate voting as a one-mode network weighted by the number of shared votes. Voting in the Senate is a signed, two-mode relationship. Senators (i) have relationships to a pieces of legislation (j) and they either abstain from voting (0) or they vote for (+1) or against (-1) the legislation. To transform the network into a weighted one-mode agreement network, then perform a backbone analysis on it would be a severe reduction of data. Some pieces of legislation are more politically divisive and some have more votes than others--backbone methods wouldn't capture these mechanisms.

You may want to consider Conditional Uniform Graph (CUG) tests instead of backbone methods. The idea behind these tests is to determine if certain graph-level properties (e.g., clustering, average path length, centralization, homophily) result from chance. The process is as follows:

1. Take measurement f from the observed graph
2. Generate a random graph that controls for certain properties of the observed graph (e.g., size, number of edges, degree distribution, etc)
3. Take measurement f from the random graph
4. Repeat steps 2 and 3 many times (e.g., 1000) to produce a null distribution
5. Compare the observed measurement to the null distribution

For two-mode networks, it would make sense to create the random graph by permuting the observed graph (both tnet and statnet in R have routines for permuting two-mode networks). If measurement f requires a one-mode network, the randomization process should be done on the two-mode network before projecting it as a one-mode network.

In the article you cite, the authors consider that, in a complex network, "[the] nodes represent the elements of the [modeled] system and the weighted edges identify the presence of an interaction and its relative strength" (emphasis by me).

In the network you study, if I understand correctly the Economist article, there's a link between 2 senators if they voted similarly at least 100 times. So, the links do not model interactions, but similarities (between the senators voting behavior). From my experience, similarity networks do not exhibit the same degree distribution than interaction networks, in the sense it is not as heterogeneous. Also, the threshold parameter used when extracting the network (here: 100) sometimes has a strong effect on the degree distribution.

Moreover, I could not find the mention of any weights in the Economist article. Yet, the presence of weights seems to be an important point in the method described in the work of Ángeles Serrano et al. you cite in your question.

From these two observations, it seems possible the method does not perform accurately on these data because it was not designed to process networks of this type. Maybe you can check the degree distribution: is it centred on a characteristic value, or heterogeneous? And what about the weights, are there any?

• I reproduced the data myself from the source web site, so I included weights and did not apply the arbitrary cutoff threshold. Thus I think the data I applied the backbone method to should not have been affected by these issues. Good idea on checking the degree distribution -- I'll have to take a look! Dec 29, 2013 at 16:39