Hi Jonathan -- thanks for this presentation. I was surprised by the amounts of symmetry present, but maybe shouldn't have been, after looking at graphs like slides 47-49.
Given this lumping, how is it actually used to get more insight into the network dynamics?
The lumping means that you can analyse the full state-space of the Markov chain, giving you the time evolving probability distribution of being in any given state. From this you can compute any statistics you like, e.g. the steady state distribution, average time until/probability of absorption. These are *exact*. Normally you have to make do with mean-field approximations which generally aren't accurate.
Hi Jonathan, really enjoyed that, thank you very much for the talk and for making it available in this online format (sorry I've probably missed a few points as a result)! Always good to have more interesting examples for students of why more insight into the mathematical structure might be a better way than just brute-forcing things.
Is there a nice visualisation of the 62 cases you mention in the abstract? I take it pages 53-60 are just some examples of these? Might be nice to see where the unlumped versions would land in comparison.
Given the network dynamics aspect, is there a nice way of preserving some of the structure that you found for one network and carry most of it over to a related network that e.g. just has one node added or deleted e.g. through temporal dynamics, or incomplete data collection?
Do you have any thoughts on how the classification of finite simple groups might help, given some more interesting group structure is unlikely to arise?
(Copied and paste from emacs and got lots of line break characters, comments without those)
Thanks for your comments Pierre-Phillipe.
Yes, the examples on slides 52-54 are of "significant lumping", i.e. cases where the full state-space couldn't be stored in memory but the lumped state-space can.
These significant cases live in the rectangle in the bottom right hand corner of the figure, so any markers in there correspond to significant lumping - there are 62 dots there. Many of those 62 cases are from animal social networks, so look qualitatively similar to the one that I illustrated on slide 52, and slides 53 and 54 show other types of example.
You can see where the unlumped versions would land in comparison - it's the diagonal line (the top edge of the shaded region). This corresponds to a state-space of size 2^N, where N is the number of vertices. So for the most significant cases, the full state-space would have something like 10^14 states but the lumped state-space only has 10^8 states. A lot of compression!
Good question about the classification of finite simple groups (CoFSG)! I have some thoughts, but I'm not an expert. To get a lot of lumping, the order of the graph automorphism group needs to be very large, in fact it needs to scale exponentially with the number of nodes (for a family of graphs).
It seems to me that most "minimal" permutation representations of many non-trivial finite simple groups have large degree (i.e. the number of points permuted), and you would need even larger numbers of vertices to represent these as graphs. So I think that actually the most significant lumping is going to come from symmetric groups and various types of products of symmetric groups, and not necessarily transitive of primitive representations.
This seems to be exactly the sort of symmetry that appears in these real-world networks, so real-world networks are possibly indicative of the sorts of symmetry you need to get highly significant lumping. There are some other interesting possibilities, for example "lexicographic products" of graphs https://en.wikipedia.org/wiki/Lexicographic_product_of_graphs.
Sorry, I think it was a little too late last night! Yes, that makes sense.
I guess most useful and robust symmetries would come from products of lots of little leaf factors and not one big group? Or at least that one big group would neither be very typical (cf Erdos Renyi) nor very robust e.g. under addition or deletion of a node?
Yes, that's exactly what we see in real world networks (products here meaning direct products - this is the "geometric decomposition" of the automorphism group on slide 33).
(Sorry, I don't have power point so haven’t listened to the voice over).
It looks like she’s using dynamics governed by ODEs on each node, but symmetry can be used to compress such dynamics on networks in a similar way - this has been looked at for synchronisation, e.g. by Lou Pecora. It looks like she might have directed graphs though, which tend to have less symmetry (apologies if I’ve misunderstood what they’re doing).
Hi Jonathan -- thanks for this presentation. I was surprised by the amounts of symmetry present, but maybe shouldn't have been, after looking at graphs like slides 47-49.
ReplyDeleteGiven this lumping, how is it actually used to get more insight into the network dynamics?
Hi,
DeleteI replied yesterday, but it doesn't seem to appear anymore, so just doing a test...
The lumping means that you can analyse the full state-space of the Markov chain, giving you the time evolving probability distribution of being in any given state. From this you can compute any statistics you like, e.g. the steady state distribution, average time until/probability of absorption. These are *exact*. Normally you have to make do with mean-field approximations which generally aren't accurate.
DeleteHere are a couple of papers I should have shared that give some more details of the lumping of network dynamics (but not of the data analysis):
Delete"A General Model of Dynamics on Networks with Graph Automorphism Lumping"
International Conference on Complex Networks and their Applications
COMPLEX NETWORKS 2018: Complex Networks and Their Applications VII pp 445-456
https://link.springer.com/chapter/10.1007/978-3-030-05411-3_36
"Exact analysis of summary statistics for continuous-time discrete-state Markov processes on networks using graph-automorphism lumping"
Applied Network Science volume 4, Article number: 108 (2019)
https://link.springer.com/article/10.1007/s41109-019-0206-4
Hi Jonathan, really enjoyed that, thank you very much for the talk and for making it available in this online format (sorry I've probably missed a few points as a result)! Always good to have more interesting examples for students of why more insight into the mathematical structure might be a better way than just brute-forcing things.
ReplyDeleteIs there a nice visualisation of the 62 cases you mention in the abstract? I take it pages 53-60 are just some examples of these? Might be nice to see where the unlumped versions would land in comparison.
Given the network dynamics aspect, is there a nice way of preserving some of the structure that you found for one network and carry most of it over to a related network that e.g. just has one node added or deleted e.g. through temporal dynamics, or incomplete data collection?
Do you have any thoughts on how the classification of finite simple groups might help, given some more interesting group structure is unlikely to arise?
Thanks again!
This comment has been removed by the author.
Delete(Copied and paste from emacs and got lots of line break characters, comments without those)
DeleteThanks for your comments Pierre-Phillipe.
Yes, the examples on slides 52-54 are of "significant lumping", i.e. cases where the full state-space couldn't be stored in memory but the lumped state-space can.
These significant cases live in the rectangle in the bottom right hand corner of the figure, so any markers in there correspond to significant lumping - there are 62 dots there. Many of those 62 cases are from animal social networks, so look qualitatively similar to the one that I illustrated on slide 52, and slides 53 and 54 show other types of example.
You can see where the unlumped versions would land in comparison - it's the diagonal line (the top edge of the shaded region). This corresponds to a state-space of size 2^N, where N is the number of vertices. So for the most significant cases, the full state-space would have something like 10^14 states but the lumped state-space only has 10^8 states. A lot of compression!
Good question about the classification of finite simple groups (CoFSG)! I have some thoughts, but I'm not an expert. To get a lot of lumping, the order of the graph automorphism group needs to be very large, in fact it needs to scale exponentially with the number of nodes (for a family of graphs).
DeleteIt seems to me that most "minimal" permutation representations of many non-trivial finite simple groups have large degree (i.e. the number of points permuted), and you would need even larger numbers of vertices to represent these as graphs. So I think that actually the most significant lumping is going to come from symmetric groups and various types of products of symmetric groups, and not necessarily transitive of primitive representations.
This seems to be exactly the sort of symmetry that appears in these real-world networks, so real-world networks are possibly indicative of the sorts of symmetry you need to get highly significant lumping. There are some other interesting possibilities, for example "lexicographic products" of graphs https://en.wikipedia.org/wiki/Lexicographic_product_of_graphs.
Sorry, I think it was a little too late last night! Yes, that makes sense.
DeleteI guess most useful and robust symmetries would come from products of lots of little leaf factors and not one big group? Or at least that one big group would neither be very typical (cf Erdos Renyi) nor very robust e.g. under addition or deletion of a node?
Yes, that's exactly what we see in real world networks (products here meaning direct products - this is the "geometric decomposition" of the automorphism group on slide 33).
DeleteSorry, I don't know why it's not signed me as Pierre-Philippe Dechant, as that's what it suggested it was doing!
ReplyDeleteHi Jon -- do you think "lumping" would be aplpicable to the gene network "condensation" Daphne talks bout in her presentation?
ReplyDelete(Sorry, I don't have power point so haven’t listened to the voice over).
DeleteIt looks like she’s using dynamics governed by ODEs on each node, but symmetry can be used to compress such dynamics on networks in a similar way - this has been looked at for synchronisation, e.g. by Lou Pecora. It looks like she might have directed graphs though, which tend to have less symmetry (apologies if I’ve misunderstood what they’re doing).