power_centrality() should support edge weights

[davidskalinder]

Describe the bug

power_centrality() cannot handle weighted graphs and so returns different values for a weighted graph and for an equivalent graph with parallel edges.

sna::bonpow(), on which igraph::power_centrality() is based, does not have this problem since it accepts a weighted adjacency matrix as an input, but it's not possible to do this with the igraph function since it uses ensure_igraph() to only allow an igraph object as input. As a result, the only workaround to work with a weighted igraph is to convert the graph to something like an adjacency matrix (with weights in its cells) and then back into a graph with parallel edges instead of weights, which can then be passed to power_centrality() as in the reprex below.

The reason for this behavior is that this line in the function for dense matrices and this one in the function for sparse matrices use as_adj() to convert the igraph to an adjacency matrix, but they do not pass any arguments to as_adj(). The bug could be easily fixed by allowing the name of the weight attribute to be passed to as_adj()'s attr argument, but I'm hesitant to submit a PR since it's not clear to me how the fix would/should affect downstream compatibility. At a minimum, this unexpected behavior should be better documented.

To reproduce

library(igraph)
#> 
#> Attaching package: 'igraph'
#> The following objects are masked from 'package:stats':
#> 
#>     decompose, spectrum
#> The following object is masked from 'package:base':
#> 
#>     union

incidence <- matrix(c(1, 0, 1, 0, 1, 1, 1, 1, 1), nrow = 3, ncol = 3)
bipartite <- graph_from_incidence_matrix(incidence)
gph_weighted <- bipartite_projection(bipartite, which = TRUE)
adj_weighted <- as_adj(gph_weighted, attr = "weight")
gph_unweighted <- graph_from_adjacency_matrix(adj_weighted)
adj_unweighted <- as_adj(gph_unweighted)

identical(adj_weighted, adj_unweighted)
#> [1] TRUE

identical(power_centrality(gph_weighted), power_centrality(gph_unweighted))
#> [1] FALSE

Version information

• R/igraph version: 1.5.1
• R version: R version 4.1.2 (2021-11-01)
• Operating system: Ubuntu 20.04.6 LTS

> sessionInfo()
R version 4.1.2 (2021-11-01)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 20.04.6 LTS

Matrix products: default
BLAS:   /usr/lib/x86_64-linux-gnu/openblas-pthread/libblas.so.3
LAPACK: /usr/lib/x86_64-linux-gnu/openblas-pthread/liblapack.so.3

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C              
 [3] LC_TIME=en_US.UTF-8        LC_COLLATE=en_US.UTF-8    
 [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8   
 [7] LC_PAPER=en_US.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C            
[11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] igraph_1.5.1

loaded via a namespace (and not attached):
 [1] compiler_4.1.2    Matrix_1.6-1.1    magrittr_2.0.3    cli_3.6.1        
 [5] tools_4.1.2       rstudioapi_0.15.0 unix_1.5.5        grid_4.1.2       
 [9] rlang_1.1.1       pkgconfig_2.0.3   lattice_0.20-45 

[szhorvat]

This is really a feature request ...

The function does not have a weights parameter, which makes it clear that weights are not considered. Every igraph function that uses weights will have a weights parameter.

IMO if improvements are to be made to this function, the way forward is to move it to the C core of igraph. Currently it exists in R only, which means that it was not brought up to the same quality standards are the rest of igraph. If you are interested in helping out, here's what needs to be done:

• Write a summary of the theoretical background. Search the literature, and provide references. What is the relationship between "power centrality", "alpha centrality", Katz centrality, eigenvector centrality? Can the first three be unified in a single description? What are the common names for these concepts in various fields (going beyond social networks)?
• Develop the theory. What are efficient and numerically stable ways to compute these? Can they be written as an eigenvalue problem (like PageRank), which would probably make ARPACK a good choice for a robust solver? Do we need a sparse linear solver instead?
• Implement it in C. How to do this depends on the outcome of the above two points.

Any help with this is most welcome.

[davidskalinder]

This is really a feature request ...

Yes, I thought it could go either way. I filed it as a bug because I think the behavior is surprising since that there's no reason why power centrality should work differently than all the other types of centrality, and also because the sna implementation on which igraph's is based (consistent with the specification in Bonacich's paper) does accept a weighted adjacency matrix. At the moment, it's hard to figure out that igraph's function is indeed different in this regard; as a newcomer to power centrality I had to read several papers, quite a bit of sna's documentation, and the source code of both packages' power centrality functions just to confirm what was actually going on.

I've also realized since reporting this that the problem is worse than I thought, since the requirement of an igraph input combined with the inability to handle weights means that it's impossible to find power centrality of networks with non-integer edge values (as is the case, e.g., with correlation networks). As a result, this is a broken or at best a partial implementation of power centrality.

I agree though @szhorvat that the solution you've outlined is the best one and should be considered a feature request. I also understand that getting a feature like this in requires someone to stand up and do it, but unfortunately I think I don't think it can be me since I lack the cross-field knowledge of the concept, the understanding of the solver algorithms, and the C coding ability. Hopefully someone with some better knowledge will see this and be able to implement it properly!

In the meantime, are there any incremental improvements to the function that should be considered? I can see how temporary fixes might be a bad idea since they could get people depending on behavior that changes in the eventual fix, so I understand if we'd prefer to avoid solutions other than the proper one suggested above.

However, it does seem to me that simply updating the documentation to explicitly mention this behavior could add a lot of value until we get a better implementation: even just something like "Weighted networks are currently unsupported," or perhaps also some suggestions for workarounds or possibly a link to this issue (in hopes of finding a contributor!). It seems like that'd be a nearly costless minimal solution in the short term? I'd be happy to submit a PR for this if that's helpful.

[szhorvat]

PRs welcome either for just a doc update, or a fixup of the R code.

If you're up for the task, you can contribute to the larger goal of moving this to the C core by reading up on the theory and giving a short summary here, along the lines of what I wrote in my last message.

[szhorvat]

BTW writing docs is a lot of work, so PRs with documentation improvements are always welcome, for any function!

[davidskalinder]

PRs welcome either for just a doc update, or a fixup of the R code.

If you're up for the task, you can contribute to the larger goal of moving this to the C core by reading up on the theory and giving a short summary here, along the lines of what I wrote in my last message.

It'd take me a while to pin down the theory, but I might do so in the course of my current project anyway; so if that happens I'll definitely post it here.

Meanwhile, I think it'd be pretty trivial for me to alter the R code to accept a weights argument in a similar to way most of the other centrality measures. It sounds like the thing to do is for me to submit a PR with that change and see what the dev team makes of it?

[krlmlr]

As mentioned in #905, we first need #906 to handle this in a nice way.