Skip to content
This repository has been archived by the owner on Jun 23, 2023. It is now read-only.

Implementation of ρ_ska normalization is incorrect when providing undirected (mirrored) networks #203

Closed
mjsmith037 opened this issue Feb 5, 2022 · 1 comment · Fixed by #205

Comments

@mjsmith037
Copy link
Collaborator

Describe the bug
When calculating an upper bound for the spectral radius using the ρ_ska formulation, the function in community/spectralradius.jl uses the number of links in the provided network (an undirected network produced by mirroring the converted bipartite network, if coming from ρ(N::T; varargs...) where {T <: BipartiteNetwork}). By contrast, Staniczenko, et al. note that the spectral radius is bounded from above by √|E|, where E is defined as the number of undirected edges (i.e. not the sum of the adjacency matrix, which effectively doubles the count of edges for undirected networks).

If the mirroring is built into the normalizing function, then we can safely resolve the issue by dividing by two as well:

ρ_ska(N::T, v::Float64) where {T <: UnipartiteNetwork} = v/sqrt(links(mirror(N)/2))

but this would mean doing the mirroring twice, since it is also currently done in order to get the eigenvalues. Alternatively, one could add a check to ρ_ska ensuring any network N is undirected.

The documentation should probably state explicitly that this normalization is only defined for undirected networks in any case.

To Reproduce

# using network 'N' from Staniczenko, et al. figure 1
N = BipartiteNetwork(convert(AbstractMatrix{Bool}, [1 1 1 1; 1 1 1 0; 1 1 1 0; 1 1 1 0; 1 1 1 0; 1 0 0 0]))
ρ(N, range=ρ_raw)
# 3.943904581962701
ρ(N, range=ρ_ska)
# 0.6763740557436609

Expected behavior
# 0.9565373628699811

@tpoisot
Copy link
Member

tpoisot commented Feb 10, 2022

Nice catch. There's a fix that doesn't involve a second mirror operation, I'll try to hotfix it this afternoon. As a note to myself, it's probably 2links(N)-sum(diag(N)) or something (writing this on the subway so...).

As a guideline, which should probably be clearer in the documentation, it's a good idea to always think of networks (in the package) as directed. A mirrored network isn't necessarily undirected, it just has interactions going both ways. That's a big design decision, and it might be lifted in the future, but for the moment thinking of networks as (un)directed isn't necessarily useful.

Thanks for the very informative bug reports! I'll get to the other one very soon.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants