Is the *edge-vertex incidence matrix* implemented in igraph?

Development
1

From the documentation: of as_incidence_matrix():

  • as_incidence_matrix() was renamed to as_biadjacency_matrix() to create a more consistent API.

Reason:

Some authors refer to the bipartite adjacency matrix as the “bipartite incidence matrix”. igraph 1.6.0 and later does not use this naming to avoid confusion with the edge-vertex incidence matrix.

Is the edge-vertex incidence matrix implemented in igraph? I could not find a function in the R library of igraph.

2

No, it is not, but it was discussed before, and would be nice to have. Feel free to open a feature request so it wouldn’t be forgotten.

3

Note: a post must contain at least 20 characters.

To do.

4

So implementing this in C is not hard, but first we need to think carefully about how to best define the incidence matrix. If you like, you could help with that.

Questions to consider:

  • How do we define it for simple undirected graphs? This is fairly straightforward: 1 indicates when an edge and vertex are incident.
  • What about graphs with self-loops?
  • What about multi-edges?
  • What about directed graphs?
  • Do we need a special definition for weighted graphs? Is this definition consistent with multi-edges?
  • How does all this fit with BB^T being equal to the Laplacian? Do we get the directed and weighted generalizations of the Laplacian which are already implemented in igraph, or so we get something else?

Coming up with various definitions is not difficult. The main point for me is the last one: consistency with the Laplacian. It also makes sense to review how other software packages define the incidence matrix, and if there are differences, point them out.

If you would like to help with this, thinking through these questions and writing up a summary of what you found would be very useful. References to textbooks are also welcome, but beware that textbooks often differ from each other, and most consider only unweighted simple undirected graphs.

5

I am working on a draft proposal which will address your points and possibly more.
I let you know when on Github.

Above relationship does not hold for the weighted Laplacian matrix.

The relationship holds for undirected graphs if we do not take the matrix multiplication %*% but the (nonexisting) min operator: %min%.

Added.
The matrices should be calculated so that the following relations hold:

Let

  • Graph g is without loops.
  • L is the Laplacian matrix of graph g. Q is the signless Laplacian matrix.
  • B is the unweighted vertex-edge incidence matrix.
  • Bw is the (un)weighted matrix, depending on whether or not weights are taken into account.
  • W is the diagonal matrix containing the edge weights, or ones if weights are not considered.

Then

  • Bw = BW.
  • Q = BwBT, when g is undirected.
  • L = BwBT, when g is directed.

If graph g has loops then the above relations hold except for the diagonal.

1 Like
6

I have posted a draft feature request (#1122) on

I hope it is a good start.

7

I have included the weights argument.
See for example Incidence matrix - Wikipedia, chapter Weighted graphs.

For calculating the Laplacian matrix two edges must be equivalent to a single edge with weight = 2.