Problems with the estimation of the connectivity


I’m noob in Network Analysis and I’ve some doubts about ‘‘connectivity’’. I’m analysing a biological network and trying to quantify the connectedness. Firstly, I checked some articles and the common statistic that everyone use is the average degree but I saw the edge_connectivity command and it seems more attractive and robust (what is the minimum number of edges to remove to generate a disconnected graph). I used the command:

edge_connectivity(Mygraph, source = NULL, target = NULL, checks = TRUE)

R says that the value is 0. I don’t know if it is because source and target shouldn’t be NULL or due to I failed in a previous step.

Do you know other ways to estimate connectedness?
Thank you very much for your time!
Best regards,

This means that your graph is not connected, or not strongly connected if it is directed.

This really depends on what you mean by “connectedness”. There are many quantities one might compute from a graph. Which one to use depends on what you want to find out about the graph. Ideally, you would find a quantity which is directly relevant to some physical or biological process related to this network.

You can ask questions like:

  • Does it have many connections relative to the number of vertices? Here one can use the graph density (\sim E/V^2 where V and E are vertex and edge counts) or the mean degree (\sim E/V). Even here, which one to use depends on the application. How do you expect the edge count to scale as the vertex count increases? In many real-world networks it scales linearly, therefore it is the mean degree that is meaningful.
  • What is the minimum number of edges (or total edge weight) to remove to disconnected the graph? This is edge connectivity or minimum edge cut.
  • We can ask the same for vertices, that’s the vertex connectivity.
  • How easily does the network get disconnected if you remove edges (or vertices—which is different) randomly? You can plot the size of the largest component against the fraction of removed edges.
  • What if you remove edges (or vertices) in a targeted way instead of randomly?

Finally, all of these can be compared to an appropriately chosen random null model—a random network that matches your empirical network in some biologically relevant properties. That’s how you can tell if a value you get is “high” or “low”.

Many thanks!!!
In my preliminary analysis I calculated the average grade and density. My network is made up of two-set nodes (not interacting with each other) and edges (unidirectional) without weights. Is it impossible to calculate edge or vertex connectivity? What R command do you recommend?
Thanks in advance (again T.T).

I don’t understand what you mean. You can compute the edge and vertex connectivity using edge_connectivity and vertex_connectivity. If the graph has more than one (strongly) connected component, then its connectivity is zero by definition.

I have some problems with the interpretations of the values of edge/vertex_connectivity. When I calculated these values in my initial network, both were 0. Now, I calculated same parameters to other network and the values are 1. But…I don’t understand how interpret these values.
I was following your idea to calculate the minimum number of edges/vertex to remove to disconnect the graph but I don’t get any page/paper/manual to do this with R.
Sorry to bother you so much, I’m new to the world of network analytics.
Best wishes,

edge_connectivity() returns the smallest number of edge cuts that can be used to disconnect the graph. If the result is k, it means that there exists a set of k edges whose removal will disconnect the graph. To see one such set of edges (out of typically many), use min_cut(graph, value.only = F).

vertex_connectivity() is the same for vertices. What is the size of the smallest vertex set whose removal disconnects the graph?