Recording of Network Science Colloquium Series Cristopher Moore

本站添加: 2026-06-03

[00:00:00]great so I'm going to uh get us going here this morning uh good morning good afternoon good evening wherever you are um on behalf of the network science Society once again I welcome welcome you for our monthly NY copium uh we have another exciting topic on our in our on our agenda today and uh a fantastic speaker and very happy to introduce today's speaker Dr Chris Moore uh Dr Moore was trained in physics and math at North Western University got his bachelor's degree there in 1986 and then went on to get a PhD in physics at Cornell 1991 starting with uh his post-doctoral work he began a a long-lasting affiliation with the Santa Fe Institute which really has lasted at the present day uh starting there as a research faculty member in 1998 he joined the ranks of the University of New Mexico uh and became a full Professor there in 2008 um and since 20 12 he's been a full-time resident professor at the S Institute uh he's also held various visiting positions in newpor Institute they call poly technique in Paris Northeastern University of Michigan and Microsoft research his work is as many of you know is highly interdisciplinary covering parts of physics math computer science Network science obviously statistics uh his many well over 100 close to 200 Publications cover topics in uh various Fields classical mechanics Quantum Computing social networks epidemiology as you hear today uh and statistics of of networks many of you are familiar with uh Chris's work made some waves I think at the time on power laws in in networks and also um on designing robust hierarchical clustering algorithms among his many honors he's an elected fellow of the American physical Society the American mathematical society and the American Association for the advancement of science he is also the inaugural member if not the originator of the Zachary karate club this is a uh unique uh honor I think to have I I have the karate club club the karate club club that's right it's the it's it's it's a very it's very M very postmodern it's a club about a club and uh you were the originator of that I'm dying to hear the story sometimes Maybe not today but uh that is a one of those things in network science that many of you are heard about but he is the actual founder of the of this madness um well let's let's be Eric Hagberg at Los Alamos was the founder okay I was the first embarrassed recipient because is that right okay you there were several years when every Network talk mentioned the karate club so Eric decided that the first person at a conference who mentioned the karate club should should be handed this Trophy and then should hand it on to the person at the next conference that mentioned it first if you look at the list of recipients of this of this award or this prize uh it's a very illustrious list I I welcome uh you checking that out on Wikipedia um before we begin um a couple of reminders the talk will be recorded and posted uh shortly afterwards on the so's website and uh we invite audience members to ask questions uh please enter these questions typee them into the Q&A feature not the chat please but the Q&A the end of the talk I will try to monitor discussion uh in some rational fashion uh and we'll call upon you to ask your question and person so without further Ado uh thank you very much Chris for for doing this and over to you it's 8:00 in the morning and you've got your coffee next to you so uh uh we look forward to your talk well thank you very much for inviting me this is a great colloquium series I feel quite honored to be invited to speak with you all with the the network science Society um those of you who know me can measure my respect for the network science Society by the fact that I got up at this hour to give this talk so I'm actually very excited to present this work um it is joint work with uh the two people you see on the screen most of all with Alexander Mercier uh who was a an undergraduate at the University of South Florida at the time and a uh research experience for undergraduates intern a summer intern at the Santa Fe Institute when this work was started and a lot of the ideas here are his and we also teamed up of course with Sam scarpino who I'm sure you know one of the leading figures in network epidemiology and during covid he was my chief uh Guru about hey Sam I want to say something about but so many people are trying to say things about Co can you please let me know if this actually makes any sense um so he's been very good at grounding our our work in uh in real epidemiology so um this talk is about sparsification of networks so what is that well the idea is that we have some dense weighted graph and we want to turn it into a sparse weighted graph and in the version that I'm going to be talking about uh we're going to keep all of the vertices but just a small fraction of the edges um now why would you why would you do this well first of all you want this sparser graph to preserve important properties of the original graph whatever properties are important to you and as we'll talk about that's application dependent um you might want to preserve topological properties like uh Community structures for instance and there's a long history in network science of trying to find network backbones which are somehow representative of the overall structure of the graph in this talk though we'll be interested in preserving Dynamic properties so you can imagine wanting to preserve to in some sense how do random walks on this graph work uh how does the heat equation or uh you know coupled oscillators work or in in particular how do epidemic work on this graph and it might be strange to think about well how can I do that if I'm only keeping a small fraction of the edges but we'll see that that that can be done in certain senses now why why do you want to do this again you I think there there are two main uh two main motivations one is a kind of practical one which is that many graph algorithms and many for instance event driven simulations of d iCal systems on graphs have a computational cost which grows with the number of edges so in a practical sense by reducing to a small fraction of edges uh you might greatly reduce the amount of computation you need to do but I think for us what quickly emerged was a more conceptual or scientific motivation which is we want to understand which edges are important in the network which edges really contribute to this dynamical process and so if you can succeed in preserving an important dynamical process with only a small fraction of the edges presumably you've done a good job at picking out which edges are really important so here which edges are most important to the spread of a disease so you can imagine several reasonable ways to define the importance of an edge um one would be well let's keep the high weight edges you know and we learned from Sam that in a lot of bioinformatics applications uh in say genetic regulatory networks and and others it's still a pretty common heuristic to take your weighted Network for instance perhaps formed by the uh the uh The covariance Matrix of the activities of of different genes and to Simply declare a threshold and to keep the edges whose weights are above that threshold and throw the other ones out now I don't think this is a good approach for that for those problems or for this problem uh for several reasons one is that well in this little triangle here you can you see that you could cross from one vertex to the other along that high W High weight Edge or you could take a little path of length too well if there are many such paths many short paths that give you alternate ways to get from one end point to the other of an edge maybe that edge is not so important even if it is high weight so we'll talk about how that might work also of course throwing away the low weight edges kind of flies in the face of one of the slogans and network science and sociology about the strength of weak ties that even a low weight Edge can play a functionally important role for instance if it connects two otherwise distant parts of the network which brings us to the idea of betweenness so there's been a lot of great work on betweenness and uh so for instance here in this little graph there's that low weight Edge there but you can see that every every shortest path indeed because this is a tree every path from those uh from the two vertices on the uh on the left to the two on the right will have to go through that low weight Edge so if we were to not include it in our sparse graph we would really be disconnecting those two parts of the graph which would presumably be a bad thing um and so uh or we might be approximately disconnecting it if the other alternate paths are quite long uh looping around elsewhere in the graph so betweenness however has some disadvantages as a way of defining the importance of an edge one is that the classical versions of it uh are can be somewhat expensive to calculate with uh computational cost growing like say n cubed where n is the number of nodes and we're going to be interested in networks with millions of nodes noes one of the reasons why those traditional things are uh definitions of betweenus can be expensive is that they really focus entirely on the shortest paths and this is another another objection to them so if I want to understand the importance of an edge maybe I don't just care about whether it is included in the shortest paths to get from point A to point B um that's a kind of very discreet optimization minded thing to do what if it appears in many of the of the reasonably short paths uh after all lots of things flow on networks through all sorts of paths not just the shortest ones and so you want some kind of more soft or continuous waiting of different paths perhaps to assign importance to an edge so some combination some compromise between weight and betweenness and maybe some smoothing of the idea of between this perhaps that's what we're going after so before I sort of get to the punchline of the first part and tell you about effective resistance which is uh how we're going to Define importance let me describe to you a broad family of sparsification algorithms which can be applied really to any definition of edge betweenness so the idea is to sample edges from the original graph randomly to include in your sparse graph which may sound strange and haphazard but in computer science actually many randomized algorithms are the best ways we know to solve certain problems and our algorithms based on random sampling are often very beautiful mathematically and often are very simple and elegant to analyze so suppose you assign every Edge in the original graph of probability pie of B proportional to its importance whatever you think importance is um and uh then if you want a new graph G prime a sparse graph just sample s edges independently from the original graph according to that probability distribution uh if you we're going to do this uh as the statisticians say with replacement so you could sample the same Edge multiple times um that's okay and if that happens we're just going to add up the weight uh of that edge in the sparse graph each time we sample it but now there's going to be a sweet little twist here so if I sample an edge in the sparse graph uh and and include it in the sparse graph I might want to give it a larger weight than it had in the original graph to compensate for the fact that we're sparsifying things and for instance that the The Chosen Edge might be standing in as a kind of Representative of a bundle of edges and so we want to give it a weight so that it can kind of represent that entire bundle so here's how we do this if the original weight of the edge was W sub its new weight WP Prime sub will just be W subb divided by S the number of uh samples we're taking times P of B the probability that we would choose it so this this looks maybe a little curious at first because it means that if if we do choose an edge which has a very low probability of being chosen we would give it in the sparse graph a rather large weight which might sound strange but the reason we do this is that so its expected weight in the sparse graph will be equal to its original weight so on average it will have the same weight in the new graph as in the old one and that's because the average number of times you're going to choose it is s the number of samples times pie of be the probability that you would choose it so you multiply that it cancels and you get the original weight because each time we choose it we just it uh it contributes further to its weight now um okay so the average weight is preserved but uh so what else does that preserve well it preserves the total weighted degree of each vertex it preserves the weighted adjacency Matrix and it also preserves the weighted lassan um if you're not familiar with the graph laian it's a very useful linear operator which comes up in the uh the heat equation for instance and the flow of probability in random walks or spread of information lots of important uh linear dynamical systems and it equals the M The Matrix D which is a diagonal matrix of the vertex degrees minus the adjacency Matrix and if you're familiar with partial differential equations like the heat equation or the sound equation in continuous settings it really is uh the analogous operator to the standard liian involving second derivatives um okay so this General sampling and reweighting scheme will preserve all of these uh all of these quantities all of these linear operators in expectation the IE on average but of course it's a little funny to say we're preserving the average because the whole point is that most of these weights are going to be zero in the new graph because the new graph is going to be sparse so of course we don't just want to preserve averages we want to somehow be close to the average but the weights are mostly going to be zero so they're not going to be close to their averages what do we want well for instance we might want the graph laian and its spectral properties to somehow be concentrated around those of the original graph so that dynamics of various kinds will act like that on the original graph so that's the idea um but although any Edge importance in the sample and reweight scheme will preserve the average maybe only the right notion of importance will preserve uh with high probability some spectral properties and really get close to the average so this brings us to effective resistance so how do we Define this and by the way this has been rediscovered a zillion times by different people in different communities and I'll name a few of them later uh we're going to take that weighted graph and view it as an electrical Network a network of resistors and on each Edge we're going to put a little resistor whose resistance is one over the weight of that edge so the weights are the conductances and the reciprocals are the resistances now that's little RCB but the effective resistance big RCB is the resistance I would get if I took my my ohm meter and plugged one of the end points of the edge into some voltage and the other into some ground and I looked at the overall flow of current from one end point to the other now when I do that of course I'm getting some flow across the edge itself but I'm also getting a bunch of flow across all of the alternate paths all of the alternative paths in the network from here to there which could loop around in various ways going through other edges now um remember that resistances add in parallel sorry conductances add in parallel um which means that uh the reciprocals of resistances add in parallel remember your electrical engineering class if you had one and so uh if this one Edge is the only way to get from here to here its effective resistance will be its resistance one over its weight but to the extent that there are many alternative paths that are not too long or that involve edges of reasonably large weight then this will reduce the effective resistance and make it less than one over its weight okay so you can see that this is a sort of compromise between weight and a sort of betweenness except now we're counting all of the paths in a certain way not just the shortest ones so that deals with one of my complaints about between this from before because of course electricity will flow to some extent along every possible path from this vertex to this vertex but it will prefer shorter higher weight paths so our actual measure of importance is not just the resistance it's the weight times the resistance and now let's think about that quantity well again if this Edge is is the only or nearly the only way to get from here to here well I'm sorry I'm going a little bit slow but uh it's appropriate for me because it's early in the morning um the effect of resistance again is one over the weight we multiply by the weight we get one okay so this measure of importance is one which is its maximum possible value if this Edge is the only way to cross between its end points on the other hand um if there are many alternative paths then W * R will be significantly less than one okay so you can already see we're assigning a high importance to edges which are bridges or nearly Bridges between otherwise distant parts of the network and we're and we're assigning them that high importance whether they are high weight or low weight okay which I think is also very helpful all right so this quantity has many beautiful mathematical properties first of all it's related to First passage times and random walks I can't resist reminding you that if you are on a one dimensional line of the like the integers and you take a random walk stepping left or right with equal probability you will return to the origin an infinite number of times if you do this in a two-dimensional lattice you will return to the origin a just barely infinite number of times the the integral just barely diverges and if you do it in a three or more dimensional lattice a random walk will in fact return to the origin only a finite number of times perhaps not at all before it wanders off to Infinity well this is because if you have a one-dimensional chain of resistors of say 1 ohm each then the resistance from the origin all the way out to Infinity is infinite and so the Walker can't get out there before coming back to the origin many times in two Dimensions now you have many different paths to infinity and those add up in parallel they're conduct Es at in parallel that reduces the resistance to Infinity it's still infinite but just barely uh I think it grows logarithmically or something and then in three or four or higher Dimensions there are so many paths to Infinity that even though each one is infinitely long the total resistance of the circuit between the origin and the shid infinity is in fact finite and that's why a random Walker can escape to Infinity before visiting the origin many times so there's a lovely monograph about all about all this by Doyle and Snell which I I highly recommend so that's one beautiful fact about the uh about this picture of effective resistance another beautiful fact is that well we can compute this and uh we can compute it by taking the graphlan and inverting it well you don't quite invert it because the graphlan uh always has some zero igen values but so you use the pseudo inverse where you invert it on you know you know you know what I mean and then once you do that pseudo inverse then if an edge has end points u and v if you take a vector which is one at U and minus one at V and zero everywhere else and put it on either side of that inverse Lan I guess one side should be transposed whatever that will give you the effective resistance now um you might be thinking well wait if I actually invert this Matrix that takes a long time typically n cubed steps uh yes that's true in the algorithms we use in which Alexander implemented we actually use an approximate inverse based on a low rank approximation and a random projection into the uh you know into a low rank space I won't tell you more details about that but it turns out that in nearly linear time you can compute an approximate uh inverse of the Lan and therefore you can compute approximate effective resistances very quickly um anyway so defining using effective resistance to define the importance of an edge or in some cases a node by the effective resistance of that node to all the other nodes has come up many times in it's been called information centrality current flow centrality resistance distance it's related to statistical leverage when you're trying to uh figure things out about a multivariate gaussian model um it's also called spanning tree between this including at people who who are or have been at Indiana this last thing is I think one of my favorite facts about it so why would we call this spanning tree between this well imagine that you chose a spanning tree of a graph randomly but with probability propor to the product of all the weights of the edges in the spanning tree okay so this would be equal probability of all spanning trees if all of the weight's the same um otherwise it's weighted toward higher weight edges how often will this random spanning tree include a particular Edge well it will include that edge with probability proportional to its weight times its effective resistance EXA and this is an exact relationship it's really the same thing that comes from the L because you can count spanning trees you can compute the partition function if you will of the spanning trees using the graph laian and so this is really the same fact uh and again it's because if an edge is a bridge between two otherwise disconnected parts of the network then every spanning tree has to include it so that quantity will be one and so on okay so I better uh speed up a little here so this paper from computer science by Spielman and surasa which follows some previous papers by Spielman and Shang haen um is about sparsification using the sampling method and using the effective resistance times the weight as our definition of importance and they prove a beautiful theorem which is that if you sample some constant which might be 10 or something times n log n edges from this graph using method then with high probability the lassan of the sparse graph will be very close to that of the original graph in the following sense for every Vector X if you put that Vector on either side of the lassan treating it as a a bilinear quadratic form the result will be multiplicatively close to what it would be on the original graph it will differ it will be sandwiched by 1 plus Epsilon and 1 minus Epsilon times its value on the original graph and the bigger C gets the smaller Epsilon gets so you can make Epsilon as small as you want and still have just order n log n edges and of course you know this is a a small fraction of edges if in the original dense graph we had order N squared edges now this this definition is quite powerful it means that not just the igon values but also the igen vectors of the new graph are close to those of the old graph so if you had an IG Val an igen Vector of a certain igen value uh and of the lassan then this equation tells you that same Vector is nearly an igen Vector with nearly that igen value on the sparse graph and the canonical example which they give in their paper oh sorry I should say that and remember that the lassan really drives lots of linear dynamical systems the heat equation diffusion uh the diffusion of probability in random walks and so on so the canonical example of this is well a an aish Renu graph a flat random graph with this many edges you could view as what you would get from this random sampling of the complete graph now the complete graph is obviously very good at diffusing in a single step probability everywhere but indeed a you know if you have this airish Renu graph which is dense enough to be connected if C is bigger than one uh such a graph is connected with high probability then the resulting graph will also be spectrally close to the complete graph it will be an expander if you know what that means it will be you know anyway diffusion will work very efficiently on it just as it would on the original complete graph all right but so where did we come in and you know this was an idea that Alexander brought with him from Florida to his uh to his internship well epidemics are nonlinear stochastic processes I mean uh yes there are linear versions of them we often linearize them when we think about calculating their the epidemic threshold for instance but once they actually get going and you have a significant number of infected nodes in an epidemic it is not a linear process and so we got curious about well will this same approach uh of sparsification also work for epidemics is this also a good notion of edge importance for disease spread just as it is for linear Dynamics all right so why might that be the case well so we're going to look at the sir model susceptible infected recovered and we're going to look at it in continuous time and we're going to say that if you have an infected Edge U it infects each of its susceptible Neighbors at a rate which is some overall constant beta times the weight of the edge between them and also recover at weight at rate gamma now remember the weights are like the conductances and their reciprocals are the resistances and so the idea that conductances add in parallel well that makes perfect sense because if you and I have uh if we have a multi-graph and we have multiple edges between us because we work together we also go to church together we also play pickle ball together then the total weight of the connection between us will be the sum of the weights of those graphs I could infect you at any of those places and so it makes sense that the conductances would add so in that sense this electrical analogy makes sense and this also works about if we have two communities in the graph and we have a bunch of parallel edges between them ways to cross from this community to the other um you know again the total the total weight should add what about the idea that resistances add in series well let's say that we have a path from me to you of a bunch of edges of different weights how long on average will it take the infection to travel from me to you well it be the it will be the sum of the expected times and each of those expected times is proportional to one over the weight or the resistance and so those resistances add in series if you're extremely alert you might be thinking well yeah the problem is here that for crossing a single edge we have a geometric distribution of times for it to cross so what you're saying is true about the average time the average time will add as long as nobody recovers along the way but the actual distribution of times at which at which it will end is not a geometric variable if there are several steps it's the sum of geometric variables also known as a gamma distribution um and uh you're right so because it's it's nonlinear so there are some things to think about here I should mention that before us there was a paper uh in a conference by swarup L where they pointed out some of these analogies uh and said that maybe resistance would work well for epidemics and uh they used they did some numerical experiments which were quite different from ours using hemming distance um but anyway they they did have some of the same thoughts okay so onto our experiments on the left is a very dense Network it is a network of commuters in the United States there are 73,000 nodes one for each census tra in the United States 26 million edges the weight of each Edge is the average amount of commuting that took place between those two uh locations in the year 2016 and uh Alexander compiled this from US Census Data in our sparsification we're going to keep 10 or five or 7% say of the edges and this will reduce to about you know fewer than two million edges it will reduce the average topological degree from over 700 to about 50 so it's still a fairly dense graph but much less so and now just to be clear here so certainly Mobility graphs have played a major role lately in thinking about Network epidemiology including as a way of telling whether people are staying home during co uh we're not literally saying that each node in this network which could be an entire small town for instance uh we're not saying each node is collectively susceptible infected or recovered uh you could use this graph that way you could do some compartmentalized model with a population at each mode at each node we really just chose it because we wanted a representative dense graph that's coming out of modern data science modern data sets and we wanted it to be highly heterogeneous and you can see especially on the right well that of course this graph has a lot of interesting structure there are population uh concentrations on the east and west coast there are lots of short range edges there are a few long range edges uh from one Coast to the other corresponding to airplane flights and so on so we wanted it to have a lot of different kinds of structure we didn't want to stick to uh synthetic models like my favorite the stochastic block model or whatever so we did simulations or rather Alexander did simulations on this using a continuous Time Event driven sir model and we tried this from a couple different initial conditions one of them is there is an infection at JFK at the airport in New York um you know the zombies have arrived and it's going to you know that's where the uh apocalypse will spread out from and we also looked at a dispersed initial condition where 1% of the nodes around the country uh are infected although we we chose which 1% was probability proportional to their population and so we just compared the you know how faithful to the behavior of the s model on the original network is the sparsified network with different methods of sparsification so we did effective resistance we also tried sampling with probability proportional to the weight uh with just using the weight as the definition of importance we used we tried uniform sampling where every Edge has the same probability of being included in the sparse version and we also use this kind of clunky naive method of just thresholding the weights and throwing out everything below a certain weight or where you adjust the threshold according to how many edges you want to keep all right so now a lot of us in this business and I alluded to this before have calculated epidemic thresholds I love calculating thresholds you often get to use cool linear operators and you can use the non-backtracking Matrix and you get to use generating functions and it's great but you know on a real Network there is no one threshold after all it depends on whether the infection starts in a dense area or a less dense area uh and besides we don't just care about thresholds we care about the actual history of the network and so what I'm going to show you are quite fine grains definitions of accuracy we're not just going to look at the fraction of the population at a given time which is susceptible or infected we're going to look at for each individual node the probability that it gets infected in the stochastic process over many independent runs and if it does when does it get infected so we really want to know if the sparsified graph is is preserving the Dynamics on individual nodes in important ways so here we go what are these graphs so this is the probability that each node gets infected so again we have you know all of these uh you know what was it 73,000 nodes or whatever now uh let's look at the upper left graph here the xaxis so each node is a point on this graph the x axis is the probability over a th independent runs that it gets infected by the sir model on the original graph this is with the dispersed initial conditions and the Y AIS is the probability that that same node gets infected in many independent runs on the sparse graph okay so if the sparsification process preserves the probability that an that a node gets infected everything will lie on the diagonal yals X and on the upper left there you we have for that fer there that's sparsification using effective resistance and you can see it does quite well the uh you know the nodes at the upper right are get are quite likely to be infected at the lower left quite unlikely you can see that the doing uniform sampling on the upper right uh has somewhat more spread using the weight as a definition of of importance has somewhat more spread uh away from the line yal X and then thresholding the weights just kind of destroy the structure and moves everything down um it does preserve some of the high likelihoods but it certainly does not stay on the diagonal now to be fair with a dispersed initial condition where the infection is already all over the place then you would say well come on the probability that you're going to get infected is pretty much proportional to your weighted uh degree because there's a good chance that one of your neighbors is one of the initially infected ones and you're right so let's also look at it with the uh concentrated initial condition uh where the zombies have arrived at JFK airport um and you know have filed off the plane and are now spreading throughout the country so now again there's more heterogenity here we have a nice Continuum of probabilities of infection and it looks again like effective resistance does a good job of maintaining that equilibrium uh to be fair using the weight as a definition of importance does almost as well a slightly lower correlation coefficient uniform sampling has more spread and again weight thresholding does not preserve this very well at all okay so that's cool I think um what about when nodes get infected so we also wanted to preserve what Sam taught us to call the arrival time of the epidemic so if you are going to get infected when is that going to happen and this distribution could vary a lot from node to node it could happen early it could happen late it could be a concentrated distribution it could be quite Broad and so on so here are four representative nodes and what you see are here are the conditional distributions conditioned on them getting infected when does that happen and actually here you see that all of the sampling methods um both effective resistance uniform sampling and weight-based sampling do a pretty good job of preserving the shape of these distributions uh we'll see in a moment that effective resistance does a little bit better in according to a certain measure but this is also important information so again let's let's pause here for a moment right we're only keeping a small fraction of the edges but we remember we are reweighting the edges that we do keep we're giving them a higher weight uh to you know to make up for the fact that they they represent in some sense a lot of other edges that we didn't Preserve in the sparse version now that higher weight means that they're that they're transmitting the infection faster okay so it's interesting that this sparsification method does seem to preserve the overall time scale of the uh sir model very well so you know locally it doesn't right I mean locally you know maybe what I had was a very low weight edge here which would take a long time typically to transmit the disease uh and so we replace that with a high a high weight Edge where it does so very quickly but somehow once we look at the effect of all this in a large Network the time scale is preserved so I think this is very interesting um we defined a total measure of error Alexander suggested this thing called the arrival time error score we you know we we we wanted to kind of combine the effect of uh getting the probability you get infected wrong with getting when you get infected wrong and so here's this measure uh if you do get infected it is the so-called waserstein or earth mover distance between the two distributions of times at which you get infected and if you're not familiar with that it's a nice measure of distance between probability distributions it's the total it's the average time shift that you would need to apply to change this distribution of infection times to that distribution of infection times um so it takes into account it's not just the difference between the means for instance um and you can calculate it in one di for onedimensional things like time you can calculate it easily uh using an integral of the cumulative distribution functions now if in the original graph you had a non-zero probability being ined and in the new graph you had a zero probability of being a zero probability of being infected then we give you a big penalty in this error score equal to the you know longest time we did in our simulation okay so when you do this now on the x- axis you see what fraction of edges we we kept on a logarithmic scale and you see that the the red uh my apologies if you're color blind but the the red curve is the lowest one the best one and that's effective resistance and you can see that even if we keep about 1% of the edges this is still quite small for both the localized and dispersed initial conditions the other sampling methods do quite do reasonably well but not as well as effective resistance and then weight thresholding is that line on the right which doesn't do very well at all um and one of the main reasons this happens is simply that effective resistance is better at keeping the graph connected and not having nodes drop off the network because again if you drop off then you'll never be infected and then you get a big error score for never getting infected um and so here we're simply plotting the fraction of nodes that get disconnected from the giant component and again here you see that even at 1% 10us 2 of the edg's effective resistance has very few nodes getting disconnected whereas the other sampling methods disconnect more more uh so anyway that seems to work well now because this network is very heterogeneous and because there was a lot of of discussion during covid about the heterogeneity of the social network and as a result the massive in many cases tragic inequalities in how hard Co hit different demographic groups here in New Mexico for instance early on in the pandemic people living on Navajo land who are members of the Navajo or D had a terrible terrible uh rates of mortality um now you know because they were living in multigeneration homes they had to go long distances to get fresh water all this advice about wash your hands all the time was not so easy for them to follow and um so they're living in in close quarters uh with multiple generations and they had a very high rate of mortality I'm very impressed by the fact that the Indian Health Service by the time the pandemic was over did better than most other parts of the country at vaccinating people they didn't have any of the antia nonsense that uh many of many other demographic groups were infected by in any case again this isn't really paper about covid but covid was happening so it was on our minds um so we wanted to make sure that the sparsification method worked in all of the different kinds of parts of the network the urban Parts the rural parts the small towns the parts that are very dense the parts where people uh mostly have short-term commutes the parts where they have long-term commutes and so on we didn't want we didn't just want it to work on average you know if you're you know imagine being an epidemiologist in one of these parts of the country you want it to work in your part of the country so um Alexander did some more fantastic work here where he used the classification of census tracks by the US Census Bureau and there's this 10p part classification there's Metropolitan which is big cities micropolitan which is small cities then there's small towns there's also um there's rural there's also core and high commuting and low commuting areas some people you know some areas virtually everybody there Works close to home some areas maybe they're I don't know flying to La all the time to work on movies or something so here again is that overall measure of error that combines the probability of infection with the with the uh the was steam distance in when you get infected red on the left in each category is effective resistance and then there's uniform resistance and and uh sorry uniform sampling and weight based sampling and you can see that across all of these different types of sensus tracts effective resistance is doing well um and here it is even doing better in the dispers initial condition and why is this and I I'm almost done why would effective resistance work so well in quite different parts of the network well let's go back and I I know I'm being a little redundant here but in tree likee regions right again the weight times the effective resistance resistance is one in any tree likee region where uh an edge is the only way to get from its between its end points or nearly the only way because the alternative paths involve long Loops whereas uniform sampling it might choose this Edge but there's a good chance that it won't in weight-based sampling it's unlikely to choose this edge of it's low weight or for that matter if this part of the network is generally a small part or a low weight part then uniform sampling and weight-based sampling will put most of their attention elsewhere whereas effective resistance will consider all of these highet Edge is important whether they're high weight or low weight uh in particular imagine a low weight Edge from New York to LA maybe it has a low overall uh uh rate of transmission on the other hand it could be very important to the spread of the zombie apocalypse by getting the zombies from New York to Los Angeles so that's another example of a kind of long range and therefore hide between this Edge we don't want to ignore that edge even if it is low weight on the other hand what about dense loopy regions well here somehow effective resistance again makes good choices and a good compromise between the weight and the topology because even if a even if an individual Edge has high weight if there are many other alternate ways to cross between its end points effective resistance might say actually it's not so important because even if we remove it there are lots of other ways to to make that Crossing and so uh anyway so it seems that effective resistance does make this good compromise between weight and topology okay so I'm almost done two slides left I think one is and this is a a quick slide I would like to prove this right I mean I enjoy one of the wonderful things about Network science is that we have everything along the the Spectrum from uh numerical experiments on on real data to experiments and physics style calculations on synthetic networks of various kinds to real theorems in uh you know theorems that use techniques in Rim from from graph Theory and so on so I would like to prove that this works now how might we do that so again as far as linear dynamical systems are concerned Spielman for have already proved that effective resistance is works very well um so what about epidemics and other sorts of nonlinear Dynamics well if you know about the many uses of the graph lassi in in network Theory you know that one thing you can do is take a bunch is take a subset of the nodes and construct a vector by putting ones on the subset and minus ones on its complement and in that case what the lassan gives uh is the total weight of all the edges Crossing from one side to the other so leian sparsifiers that preserve things in the sense of Spielman and surasa are in particular cut sparsifiers which was an earlier slightly weaker idea from computer science which means you preserve all the cuts between sets and their compliments um now with SI and R we have three sets and not just two but but with a few lines of algebra you can show that as long as there is a fairly large overall rate of uh of infection which again remember that the uh we infect with probability at a rate proportional to the weight so indeed the overall rate of infection is the total weight of all the edges uh connecting infected to susceptible nodes so we can show that that this is probably preserved uh as long as that rate is high enough and I think it's easy to show then that if you were tracking the fraction of susceptible or infected individuals using a differential equation uh then it would be quite close you would have a very close trajectory on the sparse Network that you did on the original network but again we want more we want to know that each individual node or that most individual nodes have roughly the same probability of getting infected in both Networks that the arrival time distributions are similar and so on I don't know how to prove that yet I don't think it's impossible uh but I think it would be a lovely a lovely chance to really show this rigorously open questions well what about other sparsification algorithms so this idea of random sampling it's very beautiful mathematically um it is also what we call a non-adaptive algorithm right we calculate these effective resistances once from the original Network and then we sample with uh those Pro with probabilities according to the weight times the resistance but we don't change those weights we don't adapt them as we sample and you might imagine well maybe we can do better like more accuracy with even fewer edges and therefore doing a better job at focusing on the most important edges with an Adaptive algorithm that says well you already chose these edges over here this type of flow in the network or this region of network is fairly well represented now maybe you should shift your attention increasing the sampling probability to some others over here so an Adaptive algorithm would be harder to analyze mathematically but it might do better and in fact there are some follow-up algorithms in computer science which greedily say at each moment take the edge and give it the weight which moves the lassan closest in that spectral sense to the lassan on the original graph so there are several other ideas here about sparsification which would be good to try another question is well what other physical or dynamical systems on networks are preserved what about coupled nonlinear oscillators for instance again telling whether the synchronized state in a the kuramoto model kuramoto model or other models of coupled oscillators telling whether it is uh locally stable or not is a linear algebra question but the real dynamics when once you get going and have all these complicated chical States that's a very nonlinear system is that kind of behavior preserved by sparsification what about ising models and sping glasses are their thermodynamics preserved when you do this uh physically if you take the original coupling Matrix and you choose a few uh edges and give them a strong interaction but reduce most interactions to zero another motivation which we're still very interested in working on is telling which links are real so you know this is a real problem in a lot of bioinformatics and connectomics and genetic regulatory networks um where you know you're measuring some huge covariance Matrix between a bunch of Time series uh and so you learn from that that yes this thing is correlated with that thing but you don't know that that's because this is directly affecting that thing or the other way around and you can try to do these transfer entropy things with time shifted time series there's lots of things you can try to do um distressingly apparently what people often do is just throw away the covariances that are below a certain weight which again I've tried to tell you that type of thresholding doesn't seem to be a good idea if you care about the Dynamics um but there's this whole there's this whole area that some people are interested in called direct coupling analysis how can we in a principled way figure out that A and C are not directly connected it's just that they're both directly connected to B how do we do that perhaps in a basian way with a strong prior that the network is is uh sparse there are people in the graphical models world that have worked on this there's this thing called the inverse ising model where I give you many samples from uh the bolt spin distribution of an ising spin glass and then you try you have to figure out the topology and the weights of the connections so you know maybe sparsification can help here too and in the case of multivariate gaussians there are there are some rigorous results along this direction finally well Chris you did this funny thing of you know you only kept a few edges on the other hand you kept all the nodes and yes for certain applications that might make sense if you live in a small town you might know what what's the chance that the zombie apocalypse will get to your town and how how long do you have to prepare but of course we often want to combine nodes into Super nodes we want to Clump the nodes together um for instance we want to know in a food web uh when do certain species of predator or Predators or certain groups of species of prey when can when do they really play enough of a similar functional role that you could Clump them together when in a power grid could you say well yes every individual generat is different every individual consumer or load of electricity is different but especially in regions where the power grid is fairly well connected maybe they basically act in Aggregate and we can lump them together and still do good simulations and of course an epidemiology uh when is it okay to use these classical compartmentalized models where people living in a given region of a given a demographic group of a given age all get clumped into one population for the purposes of a differential equation model when can we do that without losing Fidelity so there's this work um it's ongoing I'd be happy to talk about it more and thank you again very much for inviting me to give this colloquium thank you Chris so much for your talk which was beautifully clear and uh in your on your open question slide there were many issues that that came up uh in in my mind as I was following along uh and we having some questions coming in through the Q&A I want to encourage the audience to to keep on typing those questions I'd like to uh use my uh the microphone that I currently have and and ask you Chris one conceptual question just to kick kick things off sure um spcification uh you've mainly discussed it in the context of algorithms and uh you know with a with an eye towards um simplifying or perhaps streamlining the data analysis and modeling process but there's also you could you could look at it also from an evolutionary perspective or from a real world perspective where the network has some physical reality to it where links actually have some cost attached and right is in fact impossible for the system to maintain all connections all at once and there is a need for sparity what can you learn on the algorithmic side from uh uh from uh constraints or or or or procedures or mechanisms implemented on the other side of real world networks or biological networks to keep networks spse yeah that's a great question I mean for instance as we all know a lot of brain development later in life consists of pruning rather than growing uh we are also told by our friends who work on neural networks that if you train a neural network it often still works very well if you remove many of the internal links um and I think the so a couple things to say I mean one is that of course in an evolutionary setting you you know ultimately you have your definition of the importance of a link would have to do with your Fitness or your accuracy for a neural network uh so but that might be expensive to calculate so I think it's a good question how could you come up with a simple heuristic something you can calculate quickly which is going to be strongly correlated with the importance of that edge in the sense of the fitness or accuracy you would lose if you removed it um and I have no idea honestly uh if effective resistance would be a good such one but I like that meta question very much uh and so I and um you know and I also like the idea of reweighting again I I think it's a very nice aspect of these algorithms that you don't just remove a bunch of edges you also make the remaining edges higher weight to make up for it in kind of just the way and you can imagine doing that in a neural network as well increasing the weights of the edges you keep yeah I think it's for me an important open open question in this in this area