node weights in multilayer networks

[dmalzl]

Hi,

I am trying to use infomap to find communities in a multilayer network of metabolites. In this regard each layer represents the pairwise correlation network of metabolites for the given timepoint and interlayer links are pairwise correlations of metabolites between successive timepoints.

Setting up the network and running the algorithm works pretty well using the multilayer Pajek file format but I also wanted to somehow reflect the metabolic state of the organism at a given timepoint by assigning weights to nodes. After reading through the documentation and digging through the code I found that this is possible when using the state Pajek file format where one can specify state_id node_id name weight in the *states section of the file. However, although this works fine I feel like this completely disregards the layers of the network and results in all state nodes being assigned to their own cluster unless I use a very high markov time.

Is there any way to use the multilayer format and assign weights to state nodes and use this for module detection or am I doing everything they way it is intended already and just don't understand the algorithm enough?

Thanks for the reply in advance and best regards,
Daniel

[antoneri]

Hi, and thanks for reaching out!

It sounds like you have a good understanding of the basic workflow. There's currently no way to assign weights to the generated multilayer states as they are opaque to the user when running Infomap.

One way to get around this is to output the generated state network with
Infomap -o states --no-infomap --matchable-multilayer-ids N
where N is the largest layer id.

Before adding weights to the generated state network, a good check is to ensure that the resulting modules are the same as when using the multilayer input!

With --matchable-multilayer-ids N, the state ids are generated with
stateId = nodeId << (log2(N) + 1) | layerId
so you can get the layer from the least significant bits with something like
layerId = stateId & ((1 << log2(N) + 1) - 1).
(The node id is available in the file, you don't need to extract that.)

This is all kinds of contrived, but it's the only thing I can come up with now that directly solves your problem!

Of course, you can avoid this by directly modeling your data as a state network to have complete control.

I hope this helps!

[dmalzl]

Hi Anton,

Thanks for you informative reply. I will definitely try the --matchable-multilayer-ids parameter again (as it did not really make any difference when using infomap with a multilayer format file).

So to summarize you would suggest building the network in multilayer and state format and comparing them using the bitshifting approach to get the layerIds back from the stateIds?

Would it be possible for you to elaborate on how to build the network as a state network or point me to any resources I can look this up? I thought I already did using the state format (see example below where I basically assigned node state ids as physicalId * layerId) but this resulted in the behaviour described in my first post.

# A network in state format
*Vertices 346
# node_id name
1 "A002_HILIC"
2 "A054_HILIC"
...
345 "C116_RP"
346 "B109_RP"
*States
# state_id node_id as defined above "node_name" weight
1 1 "A002_HILIC_E14_5" 1.0
2 2 "A054_HILIC_E14_5" 0.09785202863961814
...
345 345 "C116_RP_E14_5" 0.859504132231405
346 346 "B109_RP_E14_5" 0.01
347 1 "A002_HILIC_P2" 0.01
348 2 "A054_HILIC_P2" 0.01
...
691 345 "C116_RP_P2" 1.0
692 346 "B109_RP_P2" 0.02547744653007811
693 1 "A002_HILIC_P40" 0.34285714285714286
694 2 "A054_HILIC_P40" 1.0
...
1037 345 "C116_RP_P40" 0.01
1038 346 "B109_RP_P40" 1.0
*Links
# state_id state_id weight
1 317 0.9814329841314368
2 98 0.9997481425473214
2 185 0.9704978843471527
...

[antoneri]

When you use physicalId * layerId, the state ids are not guaranteed to be unique.
For example:
Physical node 1 in layer 3 results in the same state id as physical node 3 in layer 1.

This is why we use this bit shift "hack" to generate deterministic state ids -- although our motivation is different.
We use it to, for example, compare two multilayer networks with the same nodes but different links.
Then, the auto-generated state ids would enumerate the state ids differently and make them harder to compare!
Deterministic state ids avoid this problem.

I suggest generating a state network using the command I wrote above. Modify that state network to add weights (and use the least significant bit trick above to extract the original layer id). Finally, rerun Infomap on the weighted state network.

While writing the above, I realized that you could directly create your state network as you did but use deterministic state ids directly using, for example, our method. This also solves your problem!

Does this make sense?

[dmalzl]

Ah yes sorry I misspecified it is actually physicalId + N * (layerId - 1) so all nodes would have different IDs e.g. node 1 in layer 1 will have stateId 1 and in layer 2 stateId 347.

However, you might be right in the sense that I should let the algorithm take care of this pecularities and I just work with the result.

It definitely makes sense. I will try it and report back.

Thanks for the help :)

[dmalzl]

Hi Anton,

I started to try your suggestion and state network generation works fine with the command you wrote above. However, I am still not sure how to exploit the bitshift trick. I am well aware what it does and how it works but in order to really be sure I get the right layerId back I also tried to infer the stateId from the nodeId and the layerId. According to the code this is computed as

stateId = physicalId << (ceil(log2(N)) + 1) | layerId

but implementing this myself and also writing it down on paper already yields different results for very small nodeIds e.g. for nodeId = 2 and layerId = 2 and N = 3 I get different results than what the generated state network contains (here the output of Infomap assigns stateId = 5 or 6 for nodeId = 2 but I get 18 which is quite far off)

I am using the python API to interact with Infomap with the following lines of code:

pjkfile = '../data/temporal_network_neg.multilayer.pjk'
im = Infomap(
    '''
    -o states 
    --no-infomap 
    --matchable-multilayer-ids 3 
    --out-name /groups/pavri/bioinfo/daniel/novarinocollab/data/temporal_network_neg.unweighted
    '''
)
im.read_file(pjkfile)
im.run()

The output is also as expected:

Parsing undirected network from file '../data/temporal_network_neg.multilayer.pjk'...
  Parsing vertices...
  -> 346 physical nodes added
  Parsing multilayer links...
  Creating matchable state ids using: nodeId << (log2(3) + 1) | layerId
  -> 11043 links in 3 layers
    -> 3693 intra-layer links
    -> 7350 inter-layer links
Done!
-------------------------------------
  -> 520 state nodes
  -> 346 physical nodes
  -> 10229 links with total weight 10769.7422

Do you have any clue why this difference arises?

[antoneri]

This is what I get using your example:

>>> from math import log2, ceil
>>> node, layer, N = 2, 2, 3
>>> node << ceil(log2(N)) + 1 | layer
18

Edit: corrected my code!

[dmalzl]

An this is how the *states section of the Pajek file looks like

*States
# stateId physicalId
2 1
3 1
5 2
6 2
7 2
9 4
10 4
11 5
13 6
14 6
15 7
17 8
18 9
19 9
21 10
22 10
23 10
25 12
26 12

which actually looks like it was initialised as if the --matchable-multilayer-ids argument was not used (according to the code)

[antoneri]

That is very strange!

On Infomap Online, running the "Full multilayer" example network with
-o states --no-infomap --matchable-multilayer-ids 2
I get

# v2.5.0
# ./Infomap multilayer . -o states --no-infomap --matchable-multilayer-ids 2
*Vertices
1 "i"
2 "j"
3 "k"
4 "l"
5 "m"
*States
# stateId physicalId
5 1
6 1
10 2
14 3
17 4
21 5
*Links
5 10 0.2
5 14 0.2
5 17 0.8
5 21 0.8
6 10 0.8
6 14 0.8
6 17 0.2
6 21 0.2
10 6 1
10 14 1
14 6 1
14 10 1
17 5 1
17 21 1
21 5 1
21 17 1

[dmalzl]

Very, very strange and interesting behaviour.
I also used the online version now and the result is quite different but at least as expected. This is the log

=======================================================
  Infomap v2.5.0 starts at 2022-06-29 17:13:58
  -> Input network: network
  -> Output path:   ./
  -> Configuration: matchable-multilayer-ids = 3
                    no-infomap
                    output = states
=======================================================
Parsing undirected network from file 'network'...
  Parsing vertices...
  -> 346 physical nodes added
  Parsing multilayer links...
  Creating matchable state ids using: nodeId << (log2(3) + 1) | layerId
  -> 11043 links in 3 layers
    -> 3693 intra-layer links
    -> 7350 inter-layer links
Done!
-------------------------------------
  -> 1036 state nodes
  -> 346 physical nodes
  -> 11043 links with total weight 10769.7422

which, if you compare it to the previous one has a different number of state nodes generated (1036 compared to 520 previous which I was already suspicious about tbh because this does not sum up to 3 * 346 = 1036 as I have 346 nodes per layer). The generated state network now also looks correct

*States
# stateId physicalId
9 1
10 1
11 1
17 2
18 2
19 2
25 3
26 3
27 3
33 4
34 4

[dmalzl]

this is the output I get when running the example with my local version

# v2.5.0
# ./Infomap  --no-infomap --matchable-multilayer-ids 2 --out-name /groups/pavri/bioinfo/daniel/novarinocollab/data/example --output states
*Vertices
1 "i"
2 "j"
3 "k"
4 "l"
5 "m"
*States
# stateId physicalId
2 1
3 1
6 2
9 4
11 5
*Links
2 6 1.6
2 9 0.2
2 11 0.2
3 6 0.4
3 9 0.8
3 11 0.8
6 2 2
6 6 2
9 3 1
9 11 1
11 3 1
11 9 1

which is again quite different than what the online version gives. So there seems to be some problem either with the ingestion of the file

[dmalzl]

Sorry for the scattering of the replies didn't notice that I wrote new comments everytime

[antoneri]

No worries!

You have indeed found a bug! I can reproduce this using the python API, but not using the command line version.

I'll open an issue. For now, you can get the correct behavior using the stand-alone version of Infomap.

[dmalzl]

Always good to know that I am not the problem ;)
Will do so thanks for the help!