Equations transitivity() and edge_connectivity()

Usage
1

Hi,

I am a sport scientist using igraph (as R-package) heavily for one of my manuscripts. The reviewers of the manuscript want me to include mathematical equations for my calculated network metrics. I have managed to find equations for 7 out of the 9 metrics/functions. Unfortunately I am struggling with 2 of them, namely the functions transitivity() and edge_connectivity(). I was hoping someone would be willing to help me out.

I have read the igraph manual, tried to find the source code of the functions (to see the calculation, but what I can find in R it only refers to C functions) and read the literature that are in the references for the two specific functions. Unfortunately the references do not give an equation either.

For transitivity() in the manual an equation is given for the special case of Barret (and weighted graphs).

weighted C_i = \frac{1}{s_i} \frac{1}{k_i-1} \sum_{j,h} \frac{w_{ij}+w_{ih}}{2 a_{ij} a_{ih} a_{jh}}

I use the default (type = “global”) and therefore was wondering if for me the transitivity is the same equations without the weight factor (W_{ij} + W_{ih} )/2?

Moreover in the description “si is the strength of vertex i, see strength, aij are elements of the adjacency matrix, ki is the vertex degree, wij are the weights.”
I was wondering what the vertex degree is?

For edge_connectivity() I struggle more to find information how to “write it in a equation”. So far I am fairly certain it is an iteration instead of a equation, but I’m not sure how to write this out.

The piece in the manual states “The edge connectivity of a graph is the minimum of the edge connectivity of every (ordered) pair of vertices in the graph. edge_connectivity calculates this quantity if neither the source nor the target arguments are given (ie. they are both NULL).”

Does it start at a random edge, removes it and checks if the graph is connected?

Then also I have checks = TRUE, the description is “Whether to check that the graph is connected and also the degree of the vertices.” How does the function check if it is connected?

I would greatly appreciate if anyone would be willing to point me in the right direction. As a sport scientist it is quite a challenging task.

2

The degree is the number of connections a vertex has. If you are not yet familiar with this term, I very strongly recommend reading up on the basics of network analysis. Network metrics are easily misinterpreted, so it’s good to have the fundamentals in place.

Perhaps you can ask your colleagues to recommend an introduction for a non-mathematical audience. I can recommend the introductory book M E J Newman: Networks, but it will take a bit more effort and some math background to go through it.

“Writing it as an equation” does not make sense for all concepts. Edge connectivity is simply the size of the smallest set of edges whose removal makes the graph disconnected. This is discussed in the book I suggested.

To get an actual smallest-size set of edges (not just its size), you can use min_cut(graph, value.only=F) in igraph.

Transitivity is also called “clustering coefficient”.

There are two distinct concepts, the global and the local clustering coefficient. They are also discussed in the above book.

The global clustering coefficient is simply the fraction of the length-2 paths which are closed:

image

1-2-3 is a length-2 path. If 1-3 are also connected, then it is closed.

The local clustering is not a single number for the entire graph, but a separate value for each vertex: it is the fraction of neighbouring vertex pairs that are connected to each other.

Barrat’s transitivity is a less frequently used concept, and it is a generalization of the local clustering coefficient to weighted graphs. I refer you to the original paper for the details (referenced from the igraph documentation).

Sometimes people also use the average local clustering coefficient to characterize the entire graph with a single number.

You were asking about how igraph computes the edge connectivity.

I suggest that at this point you focus on network science concepts, rather than igraph specifically. These concepts are widely used and are implemented in many libraries. What is most relevant for your paper is how these concepts are defined (not usually through an algorithm), and how you can interpret them in the context of your dataset, not the specific way in which igraph computes them.

Some of these are discussed on Wikipedia, but you should be cautious with Wikipedia: there are many errors and misleading statements in pages about network science topics. Graph theory pages are better though, and Wikipedia is still a good starting point to find further references.

1 Like