Some problems with --cluster-data

[u-xixi]

Hallo,

I think I found some issues with the handling of cluster data in Infomap constructor and run(). Long story short, I wanted to use --assign-to-neighbouring-module, so I tried to give a clu or tree file to cluster_data, but it doesnt work in either Infomap() or run(). The web server is fine with the file tho.
with run(), there might be a typo. i set run(cluster_data=my.clu, assign_to_neighbouring_module=True) it says

> Infomap version 2.6.0 compiled with OpenMP
> Unrecognized option: '--assign-to-neightbouring-module'

maybe it's caused by the typoneightbour in your source code? Anyway, I stopped trying with run() and played with Infomap() instead:

=======================================================
  Infomap v2.6.0 starts at 2022-12-03 01:48:48
  -> Input network: 
  -> No file output!
  -> Configuration: cluster-data = infomap.initial.clu
                    assign-to-neighbouring-module
                    ftree
                    teleportation-probability = 0.3
                    variable-markov-time
                    multilayer-relax-rate = 0.3
                    seed = 1
=======================================================
  OpenMP 201811 detected with 16 threads...
  -> Expanding undirected links to directed...
Generating state network from multilayer networks with simulated inter-layer links...
-> 2 networks
-> Relax rate: 0.3
  -> Found higher order network input, using the Map Equation for higher order network flows
  -> Notice: Directed input found, changing flow model from 'undirected' to 'directed'
Calculating global network flow using flow model 'directed'... 
  -> Using unrecorded teleportation to links. (Normalizing ranks after 0 power iterations with error -0.00042589254) 
  -> PageRank calculation done in 200 iterations.

  => Sum node flow: 1, sum link flow: 1
Build internal network with 2144 nodes and 7687 links...
  -> Rescale link flow with variable Markov time
  -> Max node flow: 0.00185
  -> Max node in/out degree: 8/7
  -> Max node entropy: 2.807095778
  -> Entropy rate: 1.708013351
  -> One-level codelength: 10.9358244

================================================
Trial 1/1 starting at 2022-12-03 01:48:48
================================================
Read initial partition from 'infomap.initial.clu'... Traceback (most recent call last):
  File "my_prog.py", line 172, in <module>
    main()
  File "my_prog.py", line 168, in main
    args.func(args)
  File "my_prog.py", line 50, in binning
    im_multi.run(ftree=True)
  File "myhome/miniconda3/lib/python3.8/site-packages/infomap.py", line 5240, in run
    return super().run(args)
  File "myhome/miniconda3/lib/python3.8/site-packages/infomap.py", line 3609, in run
    return _infomap.InfomapWrapper_run(self, *args)
RuntimeError: Couldn't parse node key and cluster id from line 'NODE_29_length_289311_cov_79.104969 1'

I change the node key to integers:

RuntimeError: Couldn't parse node key from line '29 1'

added the flow value, nope:

RuntimeError: Couldn't parse node key from line '29 1 0.005333602000476374'

change it to tree file:

RuntimeError: Can't parse node name from line 2 ('1:1 0.005333602000476374 NODE_29_length_289311_cov_79.104969 29').

All broke at the same line, line 3609. same infomap.initial.clu file works with the web server somehow. Any idea what went wrong? It also works fine if i avoid using cluster_data.

Best
Xixi

[danieledler]

Hi Xixi,

Thanks for investigating the errors! You are right about the typo, will be fixed on next release. To read cluster data for multilayer networks, Infomap expects the same format as the state level clu output for multilayer networks. If you run with --clu to create one and then read that in with --cluster-data it should work. It expects the fields state_id module flow node_id layer_id, where it will ignore the state id from the file and instead look it up based on the additional node and layer id.

Does that help?

[u-xixi]

Hi Daniel,
thanks for your reply! Then I have a follow up problem. As we discussed in a previous thread, I only set the string name and numeric physical id of each node. The state nodes are created on the fly when links are added, so I won't know the state node id until the network is totally built and ready to be clustered. It looks like I need to add a follow up step to find out the state nodes for each physical one? If that's true, how should I do it?

A small question before I go yada-yada: I used im_multi.write_clu(args.im_clu) to write out the clu file, doesn't it achieve the same effect as what you've suggested? It outputs only the simple clu with node_id module flow

Back to the problem. From my application's side, the whole idea is, I've got the nodes preclustered, if they are unassigned by Infomap, I want to put them in the same top-module as their neighbours. But I think I do get it how it makes sense for Infomap. In the multilayer-network, the actual clustering happens on the state nodes, so we will need the state-node-oriented information instead of the physical ones.

If I look deeper, the issue is probably rooted in the way I design my Infomap-based program. I used Infomap to modify some preclustered data, and in order to fully integrate the precluster in the flow computation, I made each pre-cluster a grid network. They together make one layer. Then I build some extra layers using some other features, to improve the clustering. It worked well in general, but I noticed a minor problem. A few nodes can be dropped from the grid community and ended unclustered. Possibly because the extra layers are usually more sparse than the grid network layer. We have this trade-off: if the data indicates that the nodes shall be separated, then they shall stay separated. We don't want over-clustering. But at the same time, some nodes may have no data for the features that are used to build the extra layers, in this case they may not be clustered, then we are happy to place them according to their old assignment (the grid network layer). This is maybe against the nature of Infomap algorithm, but it makes sense in the biological problem. So i thought probably the best way to do so is by using --assign-to-neighbouring-module? Is it a misuse? Maybe you have some better solutions?

And finally an unrelated issue: is it possible to assign weights to the multilayer physical nodes? In the ftree output I see all nodes with the same weight. As said, the nodes are made internally when links are added, I can set the name but I don't know how to set the weight.

Thanks again (and sorry for the lengthy texts)
Xixi

[danieledler]

Hi,

Use write_clu(filename, states=True) to write the state-level clu file.

If you need to know the state ids before creating the network, you can use the matchable_multilayer_ids feature, which construct state ids from node and layer ids that are consistent across networks for the same max number of layers. Set to at least the largest layer id among networks to match. The state id is then calculated as stateId = physId << (numLayersLog2 + 1) | layerId, where numLayersLog2 = ceil(log2(n)) where n is the value of matchable_multilayer_ids.

Regarding keeping nodes separate, does the feature discussed in #317 about freezing some nodes help?

Weights can be added as a third column under *Vertices (https://www.mapequation.org/infomap/#InputPajek), which can be used as teleportation weights on first-order networks. I don't think they can be used as is for multilayer network. What do you want the weights for?

[u-xixi]

Hi

I tried the matchable_multilayer_ids but there seems to be some bug. maybe something related to issue #311?

Example:
I have a list of physical ids: [478, 945, 492, 504, 854, 2284, 41]
i set the matchable_multilayer_ids to 3, which means (numLayersLog2 + 1) should be 3, layerID is 1
but it outputs states ids like this:[959, 1891, 985, 1009, 1709, 4569, 83]
based on the output, it doesn't seem like physID << 3, but physID << 1. but that doesn't totally add up either. [945, 492, 504, 854, 2284, 41] all seems to work like physID << 1 | 1, but 478 is more like physID << 1 | 3.

And the partitioning is also messed up, suddenly the total number of top modules dropped from 68 to 40, I checked with the alluvial diagram, the new output is just nonsense. I deleted matchable_multilayer_ids, the output went back to normal again.

Regarding keeping nodes separate, variable markov time does the job!

And regarding the weights, if the teleportation weights only matters for the first-order networks then I shall not bother. I wanted to add it mainly because my nodes are genomic fragments, and the longer ones are more informative than the short ones (they can vary some order of magnitudes, from 1k to 1m). So my naive thinking was to give them more weight.

[u-xixi]

adding to that, i checked the state node ids generated with matchable_multilayer_ids, they are still all unique, so maybe the problem is the state nodes can't get associated with the correct physical nodes in the very last steps

[danieledler]

Hi, thanks for more valuable input. We have to look into the issue with matchable multilayer ids as soon as we have time. We will also look into the possibility of using physical node weights to influence multilayer dynamics later.

Just curious, how did you find out about variable Markov time, and can you describe a bit more about what problem it solves for you? We have a paper under development for this feature on arXiv.

[u-xixi]

Thanks! Looking forward to the future release then.

I actually saw that paper when it came out. Story is, I have been developing my program for a while. As said, my multilayer network is about genomic fragments. I have one base layer of preclustering data, then other layers based on some other sequence features. In this problem we care about completeness and contamination. It means bigger clusters are good, but only when they are not mixed with what's not supposed to be there. I used Infomap in hope that it can bring more nodes in. Then I've had a problem for a long time, that is, a few links can easily serve as a bridge between some pre-clusters, joining them into an even bigger cluster, which introduces contamination.

Say we have precluster X with 30 nodes, Y with 20 nodes, Z with 10 nodes, and let's say we have 3 nodes that don't belong to any pre-cluster, but they interact on a different layer with 4 nodes from X, 2 nodes from Y and 2 nodes from Z, then there seems a tendency XYZ will go together as one big top module with 63 nodes. This is typically undesirable, because such interaction doesn't happen to the majority of X, Y nor Z. So these clusters shall remain mostly untouched. It is also a bad thing that even a weak link seemed to have such an effect, especially when that node doesn't have stronger links for the competition.

I came to realize my problem is a garbage-in-garbage-out thing. Spurious links can trick the random walker. I shall have some quality control of the links (like the Bin3C people did if you are familiar with that project). But I shall not be too rigid about it, either, because if I delete all the links that i'm not very confident about, then I'll end up sabotage the overall topology of that layer's network and it hurts the clustering performance too. So along this line, it is beneficial if Infomap can be a bit more robust against these noisy links that happen occasionally.

Last month I was going through Infomap's algorithms, that was when I found that manuscript. I am a bioinformatician who is more the bio than informatician, and I didn't really totally get how the variable markov time algo works, but it seems what you described there suits my problem so I used it. Now the merging only happens when the interactions are prevalent among the preclusters.

Some side note: I made a layer with the preclusters because they are generated based on node similarity. I don't know how to make a layer using similarity matrix from scratch. Sure I can make pairwise links but a complete graph with thousands of nodes sounds awful.

[danieledler]

Interesting, thanks for explaining!

We have another development that will be implemented soon and that may interest you, regularization for multilayer networks.