Okay. Good afternoon, everybody. So welcome to welcome to this afternoon's colloquium.
It's a great pleasure to welcome Mark Newman to give the colloquium today.
So Mark was in fact an undergraduate student here, 1988,
and then he stayed on Stories Dphil and David Sherrington, who I think I saw somewhat coming in because I did,
and he worked with David on sort of neural network type type problems,
which is how he got started in these complex network problems after and after leaving after leaving Oxford.
He was a post-doc at Cornell and then a and then a post-doc at the Santa Fe Institute.
Um, then he was an assistant professor at the University of Michigan, but basically he's been ever since.
And he recently made the Anatol Rappaport, distinguished University professor of physics at the University of Michigan.
So he's had a very distinguished career in the theory of networks and things like that.
And I think it's an interesting illustration of how physics has spread out over the last 30
years from being part of the hard core stuff that people of my generation did in their youth.
So to actually finding physicists, tackling all sorts of problems which are of interest to other and applicability to other parts of of science.
And really, that's the definition of physics these days. If it's physics, if a physicist can make a useful contribution.
And so so it's a great pleasure to welcome Mark today, who is going to talk for us on the Physics of Networks model.
Thank you very much, John. Nice introduction. Hello, everybody. It's a pleasure to be here to be back here again after 30 years.
So I'm going to talk about networks today, not, as John says, a traditional topic for a physicist to be working on,
but physics has actually made very substantial contributions in this area in the last 15 or 20 years, some of which I'd like to tell you about today.
So a network for the purposes of this talk is a bunch of dots joined together by lines in the jargon of the field is called a node or a vertex,
and the lines called an edge. I will use that jargon throughout this talk.
There's a long history in mathematics of studying networks as pure mathematical objects,
but physicists have been interested more in the applications of using networks as a
mathematical representation of the structure of many real world systems of interest to us,
including technological networks like the Internet, which is a network of computers.
The nodes are computers and the edges are data connections between computers.
Other technological networks include transport networks like the rail network or this network of gas pipelines in Europe.
Another big class of networks, more abstract, and that is information networks,
which are networks that represent the structure of some body of information.
The classic example here would be the World Wide Web.
If you take a Web page like this, it's got things on it that you can click on, and when you click on them, they get you to some other page.
So there's a link between the first web page and the second web page, what we call a hyperlink in the web jargon.
And you can represent that as a network. You can make a network with the nodes, a web pages and the edges are the links between them.
This is a picture of just a small portion of the web.
The whole thing has tens of millions of nodes in far too large to make a picture of it on just one slide like this,
probably the largest network of any kind that we study.
And its structure presumably represents somehow the structure of the body of knowledge that's stored in the World Wide Web.
So its structure is an interesting thing to look at. Another example of an information network is a citation network where the nodes represent
science papers and the edges represent one scientific paper citing another one,
something that we all do when we write papers again. Presumably this the structure of this network somehow reflects the structure of
the scientific knowledge that's stored in the body of scientific literature.
And by looking at that structure, we could hope to learn something about the structure of our knowledge.
Biological networks, another large and important class of networks.
There's a lot of excitement about, and biologists are very excited about work in this area at the moment.
Here's one example. This is a metabolic network.
So the nodes in this network are chemicals in the cells, metabolites and the edges, metabolic reactions that turn one metabolite into another one.
So it's a network representation of the biochemical machinery of a cell.
Here's another biological example. This is an ecological network.
So note here represents species in an ecosystem. The edges represent the ecological interactions between species.
In this case, predator prey interactions. One species, it's another species.
There's an interesting little twist here for this network.
See that airing over there? That's what they call a self edge.
That's an edge that connects a node back to itself. That's allowed. You can have that.
So so that in this case, that's the graph theoretical representation of cannibalism.
That's the species that eats itself. But a lot of my work is focussed on social networks these days.
If you say the word social networks to a lot of people, they think of Facebook or LinkedIn, online social networks.
But in the scientific literature,
the word social network just refers to any network where the nodes are people and the edges are any kind of connections between people.
The study of social networks in this broader sense goes back way farther than their online incarnations, back to the 1930s.
In fact, sociologists probably have the longest history of the quantitative study of empirical networks.
Here's one example. This is a friendship network of of pupils in high school and American high school.
So the nodes represent the students in the school and the edges represent whose friends with whom.
Here's an example from my own work. This is a collaboration network of scientists.
The nodes represent scientists and the edges represent who's written a paper with whom.
Here's an example I got from my friend Valdas Krebs. This is a network that comes from a study he did that was on the spread of tuberculosis,
and it represents a network of close physical proximity between people.
One of the reasons why social networks have attracted a lot of research funding recently is because they are
implicated in the spread of disease diseases spread between people when they have contact with one another.
So the network of who has contact with whom governs the way diseases spread.
If you want to understand how diseases spread and potentially how to stop them spreading, then you need to understand the structure of these networks.
And I'll touch a little bit later on on the epidemiological aspects of this.
So. So there's some examples of the kinds of networks that we're interested in looking at.
One very basic question that you can ask in this field is just what is the structure of these things?
How do you characterise the structure things? They're very big, complicated objects with potentially billions of nodes.
How can I say something meaningful about what their shape is? So it has been a lot of work done on that basic question.
A lot of it focuses on what you might call small scale structure in networks, things like degrees and path lengths and some graphs and so forth.
So these are things which you can measure just by looking at a single node in the network at a time or maybe a small group of nodes,
the very easy to measure. There's really no complicated math here.
You just have to be able to count. But nonetheless, these are useful measures of network structure.
They can tell you a lot. Let me give you just two quick examples.
Perhaps the two best studied, best known examples of this kind of structure networks.
One is degree distributions. So the degree of a node in a network is just the number of other nodes it's connected to.
So if I'm talking about Friendship Network, it's how many friends I have in the network.
And if you measure the degrees of all of the nodes in the network and then look at their distribution, make a histogram of them,
almost invariably you find something which is very strongly right skewed meaning there are a lot of
nodes that have low degree for you connections and there are a few nos that have high doing this.
This plot here is for a network of collaborations amongst mathematicians who's written a paper with who.
And so what it's telling you is that there are a lot of mathematicians that only have one or two collaborators, but there are few that have very many.
So pull at us. For example, the famous 20th century mathematician, he was legendary,
have an extraordinary number of different collaborators, over a thousand collaborators during his lifetime.
So he would be way out in the tail of the distribution somewhere over here.
There are not many people like that, but it turns out that they have a profound effect on the behaviour of these systems.
Even though they're small in number, they have an outsize effect.
They're typically referred to as the hubs in the network for obvious reasons, and I'll talk about them a little more too later on.
Another example of a well-known property of networks is the thing called the Small World Effect.
That was a famous series of experiments done in the sixties by this chap here.
His name is Stanley Milgram. He was an experimental psychologist at Harvard.
He did these experiments where he got people to pass letters from one person to another in a
sort of cooperative game that involved trying to get the letter to an intended target person.
And his finding was that typically took only about half a dozen steps to get the
letter from some randomly chosen starting person to anyone else in the country.
And this is the origin of this semi mythical result that you are only six handshakes away from anybody else in the world,
sometimes referred to by the phrase The Six Degrees of Separation, which is a title of a successful play,
later made into a movie in the nineties in which they discussed Milgram's work.
So this result in particular is now very famous. It's sort of passed into legend.
Almost everybody seems to know about this. It's it's the topic of party games.
It's the topic of satirical headlines on the Internet.
And every it's a part of the mythology.
So these are examples of sort of small scale things that one can easily measure.
And that was still very useful, though. Just because they're easy to measure doesn't mean we should turn our noses at them.
However, that's not what I want to talk about today. What I want to talk about today is large scale structure in networks.
What's the big picture? If I take this whole network of millions of nodes, what is it sort of overall structure?
How does it divide up? How are the different pieces linked to one another?
This is a much harder question to answer, much harder to characterise large scale structure because, well,
it has to involve taking information from all over a network and somehow combining it to tell you something useful.
And that's going to be a more difficult thing than just looking at one at a time.
There are a range of different techniques that we use to do this kind of analysis, but the ones I want to talk about today are spectral methods.
So spectral methods means methods that are based on matrix representations of networks.
So you can take any network like this small one here.
So suppose it has N nodes and it's got a number, the nodes from one to N in any order, it doesn't matter.
And then I construct the so called adjacency matrix, which is the matrix that has a one.
You stick a one in the matrix to represent an edge.
So a one means that there's an edge between the corresponding to an outer network, like there's an edge here between node one and two.
So I put a one in the one two element of the matrix and zeros everywhere else.
Well I also put a one in the to one element because if that's Node one No.
Two, then obviously that's nice. Clean up two in that one as well. So it's going to be a symmetric matrix.
Binary value, just zeros and ones. Symmetric is important because that means its eigenvalues will be real.
This may. Rex plays a role sort of analogous to the role played by the Hamiltonian in a quantum mechanical system.
So its eigenvalues are sort of analogous to energy levels in its eigenvectors or analogy, analogous to the wave function of the network.
Actually, I should be a little bit careful here. The the adjacency matrix is analogous to minus the Hamiltonian of a quantum system,
because its highest line eigenvalue is the one that plays the role of the ground
state and the ones immediately below that play the role of the first excited state.
So if you take a network, any network like this one here, this is a real network.
It's a social network that I got from the social networks which and you calculate its matrix and then you calculate its spectrum,
you typically get something that looks like this. This is very typical of what you find.
That's the ground state at the top.
Then there's a few excited states well separated below it, and then there's a band of closely spaced states below that.
This turns out to be what you see in many cases. And as we'll see, there's a reason for that, why you would expect that to be this sort of structure.
Just like in quantum systems, we tend to focus most of our attention on the ground state and on the first few excited states.
That turns out to be where most of the useful information is.
So the claim is that by looking at the eigenvalues and eigenvectors, we can learn things about the large scale structure of this network.
There are deep connections between these wave function like eigenvectors and large scale structure networks.
Let me start by giving you two just very simple examples of that kind of connection.
So here's one central ity is any measure that gives scores to the nodes in a network in an attempt to work out which ones are most important.
Obviously, there's many different definitions of what you might mean by important nodes in a network,
and there are correspondingly many central key measures. But a simple one is just what we call degree central or just plain degree.
Again, that's the number of connections that a node has. It's just how many friends you have.
So by this measure, the person who has the most friends is the most important person.
Okay, so, you know, that's not totally stupid.
That's quite a useful measure. It's really easy to calculate, but it has some shortcomings, too.
In particular, basically all it's doing is it's giving you one point for everybody that you know.
You just count up the number of people you know.
But in real life, of course, not everybody, you know is equally important for connecting you to the rest of the world.
If I know the Prime Minister, then that instantly makes me a more important person,
sort of by reflection, because I have the ear of the Prime Minister.
So it's not just how many people you know. It's also who, you know that matters.
So a more sophisticated central to measure is one where instead of just getting one point for everybody I know,
I get a number of points that's proportional to their score.
My score is the sum of the scores of the people I know, and that's the sum of the scores of people they know and so on and so forth.
So I can create a measure where I so I'm supposed suppose I'm Node I in the network
my score is going to be denoted by and is proportional to consider proportionality,
which I write minus one for reasons that'll become apparent times the sum of the scores of all the people in my immediate neighbourhood.
That means all the people around me in the network. So this is my neighbourhood in the network.
And just summing average or another way of writing that would be the sum of all nodes.
J But stick an element of the adjacency matrix in here.
AJ is an element of that matrix. That's one if there's a connection to Node II, A.J and zero if there isn't.
Right. So this automatically just picks out the scores of my neighbours and sets all of the other ones to zero.
So I can rearrange that equation and write it in matrix form and it's just matrix a change vector x equals L.A. Times x,
where back to x is the vector that has all these entropy scores.
So in other words, your central to your importance in the network is just an element of an eigenvector of the adjacency matrix which.
Eigenvector should it be? Well, if you want your scores to be positive, then there's only one choice.
It has to be the leading eigenvector. Perhaps the most famous theorem in linear algebra.
The intravenous theorem tells you that there is only one eigenvector with all elements positive subject to some conditions,
and that's the one with the highest eigenvalue.
So this is the ground state of the network and it represents the centrality of nodes in network.
So famous example of the use of this kind of sense charting measure is the Google search engine.
They use a slight variance on this idea to decide which web pages are important and which web pages are not important when you do web searches.
So apparently you can make a lot of money by doing this kind of stuff. Here's another example.
Only slightly more complicated. Percolation is a process, of course, well known to lots of physicists.
It's the process where you fill in or occupy at random some fraction of the sites or bonds on a lattice or the nodes and edges on a network.
So he has a network and I've coloured in some of the edges in this case.
All the network percolation is used in physics, for instance, to model actual percolation like the population of fluids through porous materials.
For instance, in networks, it's used, for instance, to model the spread of disease.
I've touched on this before. You can imagine here my I'm a person in a social network.
I have some friends. And I was I get the flu. I could give the flu to my friends, but I probably don't give it to all of them.
I just give it to some of them, you know, depending on circumstances.
So I can represent that by sort of colouring in the edges at random,
with some probability we'll call it P to represent the probability that the
disease is transmitted along those edges and then not along some other edges.
So then if if I'm the red dot in the middle there, who gets the flu, it's only going to spread along the coloured in edges,
meaning the disease spreads to a cluster, a percolation cluster of connected nodes within the network.
So in other words, the percolating clusters in the network represent the sizes of potential outbreaks of the disease.
And so if I can calculate those sizes, then I can say something about the parents disease.
Perhaps the most famous property of percolation systems is that if you just start occupying sites or bonds at random,
what you get is clusters of occupied sites which grow as you occupy more and more of them.
Eventually they start to sort of gel together and eventually they all stick together to form one big cluster that spans all the way across the system.
There is a sharp percolation threshold at which that transition happens and which you
go from separate clusters spread out to percolating all the way across the system.
And in the epidemiology context, that corresponds to the so-called epidemic threshold,
where you go from a regime where the disease is never going to spread very far,
it's only going to spread to a small local cluster,
to a regime where it can in principle spread all the way across the entire system and cause an epidemic outbreak.
So the epidemic threshold,
the way the epidemiologists talk about it and the percolation threshold where physicists talk about it are essentially the same thing.
So might ask, for instance, where does that percolation threshold happen?
What is the critical value of this probability? P At which percolation happens on a network?
So I can address that by doing a calculation like this.
Suppose I'm in the regime where there is this giant cluster, this percolating cluster in my network,
and I want to ask, what's the probability that I belong to it?
Actually, I'm going to define use of I to be the probability that I don't belong to a giant cluster, which turns out to be easier to do it that way.
So usually by as the problem is, I don't belong to the percolating cluster.
So now consider his me. I'm Node I. In order to not belong strictly in cluster, I have to be not connected to it via any of my neighbours.
If I'm connected to it even one of my neighbours, then I'm in the percolating cluster too.
So what's the probability that I'm not connected with a leading cluster via my neighbour J.
Well, there's two ways that can happen. One is that that edge between us could be not occupied, meaning the disease never gets transmitted to me.
That happens with probability. One minus p p is the occupation. Probably one minus P is the occupation poverty.
The alternative is that edge could be occupied, but J itself is not a member of the giant cluster.
Right. That happens would probably p fetch me occupied and use of j.
By definition is the probability that J is not in the joint custody.
So one minus p plus p times u is the total probability that my neighbour J doesn't
give me the disease that I'm not connected to the joint cluster via them.
And then the total probability that I'm not going to join cluster via any of my neighbours is just take the product of that over all my neighbours.
So this gives me a self conditioned self-consistent condition that I can solve to find these probabilities.
So now imagine lowering the percolation, the occupation probability, the probability of transmission of the disease.
At some point you go through the train, you go through the population transition, and your giant cluster disappears.
When that happens, all of these probabilities you must equal one you as the probability of not being
in the gene cluster if there is no giant cluster and everybody is not in it. So all of the probabilities are one.
So that's the the thing that you how, you know, you've got to the transmission all of these problems these go to one.
So we're going to do is we're just going to expand around that point. I'm going to write you as equal to one minus some small epsilon.
It has to be minus because you as a probability has to be between zero and one.
And I'm going to take that substituting this equation here, expand to leading order in Epsilon.
And you get this equation here, which can be rewritten in matrix form as a vector of epsilon equals PC.
The critical population. Probability times adjacency matrix.
Times epsilon. So this immediately tells you that one over the critical population probability is an eigenvalue of adjacency matrix,
which eigenvalue it's again the leading one because epsilon is a vector of probabilities, they all have to be positive.
There's only one vector that does that for you, the leading one.
So by just looking at the leading eigenvalue, the ground state energy of this adjacency matrix,
I can tell you the percolation threshold or alternatively, the epidemic threshold for this network.
Okay. So there are some examples of why these are useful things to look at.
So what I want to do is understand the relationship between the values of these things,
these eigenvalues and eigenvectors, and the structure of the network.
And the way I'm going to do that is very sort of physicist type approach.
I'm going to make simple models of networks, and then I'm going to calculate the eigenvalues and eigenvectors of those simple models,
and I'm going to see what they do as a function of the structure of the model network.
Before I do that, however, I want to make it an important point. How would I go about actually calculating these things?
Suppose, for instance, I wanted to calculate the leading eigenvector. So a simple way of doing that is just repeated multiplication.
I can calculate the leading eigenvector matrix just by taking a random starting vector.
It doesn't matter really what it is and then just multiply repeatedly by the matrix.
If I do that, then the components in the direction of the leading eigenvector will get multiplied by the leading eigenvalue, the biggest one.
Everything else will get multiplied by something smaller.
And if I just keep doing this for long enough, I end up with a vector that's pointing in the direction of the leading argument.
It's called the power method. Very simple, but actually quite a good practical way of doing this.
So now here's the question how long is this going to take?
How long it's going to take depends on the separation between that leading eigenvector and the next one, right?
If they're far apart, it won't take long.
But as they get close together, it's going to take more and more multiplications to separate those two apart.
And if they actually cross over, then the time to do it is going to diverge, as you see in this picture here.
So if you're someone who studies phase transitions, this looks very familiar.
It looks like the thing that we call critical slowing down in a phase transition.
If you study phase transitions numerically on a computer, for instance,
you'll be familiar with a phenomenon where the time the algorithm takes to run diverges as you pass through a phase transition.
So a wild conjecture might be that when the levels cross in the adjacency matrix that you have phase transitions going on in networks.
This is again kind of like in quantum mechanics, right? When when energy levels cross in quantum systems, you get quantum phase transitions.
So it's a similar kind of idea and indeed it turns out to be true.
And it's sort of interesting because it means that we can identify places where phase transitions should take place by looking for these crossings.
I'll give you a few examples where that happens and we know what the phase transition is for.
Interesting thing is there are lots of other examples where we get these crossings happening,
but we don't know what the corresponding corresponding phase transition is.
We believe there is some kind of phase transition now, but we don't actually know what it is.
So let me give you some examples. I'm going to start with a very simple example.
This is almost the simplest model network that you can imagine making.
It's called the random graph. So it's it's really simple.
You just take in nodes and you throw down edges completely at random.
So every possible edge is present with probability P or not with probability one minus.
That's it. That's the whole model. It just has two parameters and nodes and P.
The probability of edges has been studied for a long time, first proposed in the 1950s.
A lot is known about this model. An important quantity here will be the average degree.
So degree again remember is the number of connections you have. The average degree of a node in this random network is just the number of nodes,
times the probability of connection there are and nodes you can be connected to. You've got probability of being connected to each one.
So enzymes P is your expected number of connections.
So there's a well-known phase transition that happens in this model, very similar to the percolation transitions that we were just talking about.
If P is zero, then you have no edges at all and everything's sort of separate, like this appears one.
It all gels together into one big connected clump, what we call a component in the network.
And in between these two extremes, there is known to be a percolation type phase transition.
The clusters sort of get bigger and bigger as you increase P and at some point they gel together and you get a spanning cluster that spans the system.
So above that transition that the structure of the network is as follows A component in a network just means a clump of connected node.
Each of these is a component, so you expect to have one percolating component,
the giant component, so called, and a bunch of little ones is scattered around the edge.
That's the general structure that we expect to see. And there's a phase transition.
That phase transition happens at the point where the average degree C is equal to one.
That will be an important point in a moment. So so now what I'm going to do is calculate the spectrum of this thing.
And the claim is that there will be a crossing of the eigenvalues. Exactly.
At the point where this phase transition happens. We already know about this phase transition.
This is just sort of a demonstrative example to show you that crossing of eigenvalues corresponds to phase transitions.
So I don't want to spend a lot of this talk going through mass in detail.
But I did want to run just briefly through this one calculation to show you the kinds of techniques involved.
This is actually a very old calculation. It goes back to the 1950s as well.
It's essentially equivalent to calculations you'll find in any graduate level textbook on random matrix theory.
It's a this this kind of stuff has been done for a long time.
So I'm going to calculate the spectrum of this random graph, in other words, this adjacency matrix.
We do it in two steps.
First of all, we're actually going to calculate the spectrum of the centred adjacency matrix, which is just the adjacency matrix minus its mean value.
The mean value of any element in this matrix is just p the probability of an X.
So that's the same as saying adjacency matrix minus p subtract p from every element which
I right this p times one one transpose where both one is the uniform vector of all ones.
So that's actually the first step is to be to calculate the spectral of that.
And by the spectrum I mean the density of states, which is just the usual thing.
It's just the function that has a delta function spike at every eigenvalue of the matrix.
So it's a thing that looks like this. It's a bunch of spikes.
It's the function where if you integrate it over any region, it'll just count the number of eigenvalues in that region.
That's a difficult function to handle. It's got these spiky things in it,
so we regularise it by putting some broadband function on each spike in this particular
case will use a laurentian also called a cushy distribution by mathematicians.
And then we're going to take the limit as those dimensions width goes to zero to recover our density of states.
So here's my in six states,
here's my Laurentian and as with etre I can write it as this thing normalising coefficient divided by x squared plus u two squared and I think Mm.
It goes to zero.
I can factor is that denominator as x plus eight times x minus eight and write it also in this case imaginary imaginary part of one over x plus.
Either is another way of writing it. So this is one of the standard forms of the doubt function.
So what I do is I take that, I substitute into here, I get this expression for the density of states.
Notice that it has an x plus i eta in the denominator.
A common thing to do at this point is just to generalise this to the complex plane.
Instead of thinking of this as function on the real line, let's just go into the complex plane,
make it a function of X plus eight, which is called Z here.
So here's a row of complex Z. It's the same thing.
It's just got a Z here. And just remember that at the end what we want to do is take the limit.
E2 goes to zero. I the limit as you go back to the line. Then after that it's just arithmetic and boring.
We just do a series expansion of this function and we end up with a sum over powers of eigenvalues.
The powers of eigenvalues here and sums of powers of eigenvalues can be written in terms of traces of powers of the original matrix.
So you end up with this formula for density of states down here. So well-known things could still just run formula.
And the only difficult thing here is calculating the trace of this matrix. But it's made easier by the fact that this is a random model.
So what I'm going to do is just average over the random.
Calculate the average of this density of states, in other words, the average of this trace here, and that turns out to be an easy thing to do.
It turns out if you sort of sloppy about it, then it just vanishes. You can persuade yourself that all terms in the straits are actually zero.
But this is wrong. You have to be a little more careful and realise that there are some traces where the same matrix element occurs
twice and then you get the variance of that matrix element and that can give you terms that are non-zero.
So you get a term that depends on a power of the variance times.
However many terms there are that don't vanish. So this becomes just a counting problem.
It just becomes a question of working out how many times he had done vanish. I won't go through the geometry accounting problem,
but it turns out that the number of terms here is just equal to something called the Catalan number, which a well-known thing in number theory.
And so I can rewrite my expression in terms of the sum of these Catalan numbers.
And that can be done in closed form. It has this expression here, take that substitute back into the formula I started off with,
and you get this nice expression for the density of states.
This is a famous, well-known expression, so-called semi-circle spectrum, originally derived by Eugene Vigna in the in the 1970s.
It looks like that it works really well. That histogram there is an actual random graph that I generated on my computer the day before yesterday.
Diagonals. Did you get a nice semicircle? The blue line is the prediction of the theory.
So it works well, but we're not quite done yet because that was that centre adjacency matrix where we subtracted the mean.
So you have to add the mean back on. Meaning we're really solving an igen problem if it looks like this one here.
And you do a series of sort of boring negotiations and you end up with a neat little equation which this average over here can be done in closed form.
You get this thing here, this can be solved and you get a value for the eigenvalue here.
Bottom line is basically when you add that shift back on, you add the mean back onto the matrix.
Nothing changes. You still have your semi-circle distribution except for one thing one of the eigenvalues breaks off and moves up to here C plus one.
Where C again is the adversary of the network. So this is your final answer for your spectrum.
It looks like this and you can calculate the whole thing. The average they expect is spectrum and analytically in this case.
So now look at this spectrum. Here's here's my eigenvector central t that's my ground state, state, my leading eigenvalue.
And then here's the band that I was talking about. There's a continuous band of eigenvalues, and there's a band gap here.
And the thing is the size of that bank out depends on the average degree I one parameter the average degree the network because
this the bandage here goes like square to see the the ground state goes like see so I can change the size of that gap.
If I change it enough, I can make those two eigenvalues crossover.
Where do they crossover? Well, solve two root secrecy plus one you find.
The answer is they cross over when C equals one. Exactly the point at which that phase transition.
So this is not proving anything, but it's again suggestive.
When you get crossings of these eigenvalues, you get phase transitions happens.
There's not a new phase transition. We we knew about this phase transition already we haven't discovered anything here was
illustrative that crossings of the levels in these things correspond to phase transition.
So now let me give you two other examples.
A little bit less trivial than this one of phase transitions that happened in these networks.
So the first one is just a slight extension of the model I already described.
So I mentioned that a lot of these networks have hubs in they have a few nodes like the pull ad or node that has an awful lot of connections.
So what's the effect of that going to be on my network?
So I can model that by taking the same model as I had before, the random growth model, and I'm just going to add one extra node to it,
that red node there, which is going to be my hub and it's going to have a very high degree.
So it's going to have some probability. Q of being connected to every other node in the network.
And I quote, I'm going to write this Neapolitan meaning hit the average degree of that no is going to be D and I'm going to make D big.
So it's a hub. It's the one node in the network that has a lot of friends.
I'm going to ask, what does that what effect does that have on the spectrum?
So I won't do the calculation again, but you can it's not terrifically hard to do.
You can do this calculation. What happens is that most of the spectrum stays the same,
but you get one new eigenvalue with this particular value here d upon the squares d c
where d is the average to be the hub and C is the average screen the rest of the network.
So in other words, the spectrum looks like this.
Semi-Circle and edge gap two states at the ground state and first excited state out outside the band that.
So now I have two parameters D and C, and I can move those two eigenvalues around, and if I want, I can make them crossover.
So claim is something interesting happens when they cross over.
Where do they cross over? Well, that's easy to set.
Do you have a square or do you mind C equals C plus one solve and I get D is equal to basically the square of the degree in the rest of the network.
So clean is when the average degree of the hub is sort of order of magnitude, the square of the degree, the rest of the network.
Something interesting will happen, and that's a situation that could easily happen in real networks.
The hubs that we see in real networks easily, often the square of the average to the rest of the network.
So it's a not an uncommon situation at all. So indeed there is a transition that happens there and it's an interesting one.
It's a localisation transition.
So we're looking at the ground state, we're looking at the leading eigenvector, the thing that gives us the eigenvector sensuality of the nodes.
And normally if you just make a plot of it here, here's a figure.
My student, Travis, made these the heights of these little tents represent the Eigenvectors Central.
These there's the hub in the middle.
It's got the biggest one, which is perhaps not surprising, but there are plenty of others that have got quite high central cities as well.
Now you go through that transition where the levels cross and you get this suddenly what happens is all the weight condenses onto that hub.
It behaves very like a defect in a condensed matter system.
You get localisation around that defect and all the weight dies away from everything else.
In effect, this means that that eigenvectors central city used by Google and other people to analyse networks has failed because now
all it does is identifies the one defect and it is no good at distinguishing between any of the other nodes in the network.
So there's a failure mode of the eigenvector centralising.
If you want to see more evidence that this really is a phase transition, here is the order parameter for this phase transition,
something called the inverse participation ratio basically measures what fraction of the weight is deposited on the defect node,
and it's basically zero. It's a vanishing fraction until you get to the phase transition and then suddenly it
becomes some significant fraction of all of the weight is deposited on the defect node.
And in these numerical studies, the positions of these transitions coincide nicely with the theoretical predictions marked by those dotted lines that.
Okay. So there's two fairly simple examples of cases where the crossing of these levels in the
network corresponded to interesting structural phase transition going on in the network.
So in the remaining time, I wanted to talk in a little more length about a third example,
which is something that we've been working on in my group for some time now,
and it concerns what we call community structure in networks, which is structure that looks like this.
A lot of the networks we look at have this kind of structure where there's a clump of
nodes and there's another clump of nodes and there's lots of connections within clumps,
but there's relatively few connections between hubs.
So in a social network, this might be a group of friends and this might be another group of friends,
and they all know each other and they all know each other. But there are not many connections between two groups.
So one very basic question that you could ask about structure like this in a network is, can I find it?
If you give me a big network, can I find the groups, the communities in the network?
If a network looks like this friendship network that I showed you earlier, then of course you can.
It's easy. It's very easy to figure out what the groups are in this network. But if it looks like, say, this network, then it's a bit harder.
All that comes from this network.
You could maybe convince yourself that, well, maybe there's a clump over here, maybe is another one over here, but it's not entirely clear.
So what we like is some automated way of teasing apart the structure of the network.
So there are many ways, in fact, of doing this that have been proposed.
But the most widely used by far is something called modularity maximisation,
which is based on it's an optimisation method based on something called modularity.
Modularity is a quality function.
What it does is you give me a network and you give me a candidate division of that network into parts, into communities,
and it gives a score to that division, which is good if it's a good division in a way that I'll define and bad if it's a bad division.
And then modularity, maximisation is just let's look through every possible division of the network
and find the one that gets the highest score and that's the best division. So it's turning it into an optimisation problem.
So the whole trick here is to define the score, right?
So what makes a good score is if you look at a picture like this,
a good division of network is one that puts most of the edges inside the groups in the network.
So you're giving me the candidate division of the groups I go to count up how many the edges are inside the groups.
So so a very simple example of a score that I could use is just what what number of edges or what fraction of edges for inside groups.
However, if you think about it for a moment,
this is not a very good score because it's clear that the global maximum of that is let's just put everybody all in one big group together, right?
Then 100% of your edges are inside groups and you'll get absolutely nothing.
But so that's not quite the right thing, but it's nearly the right thing. It's basically the right answer.
So the score that does work is so-called modularity thing, which is number of edges within groups,
minus the expected number of edges that would fall within groups if you just placed the edges at random.
In other words, you're asking, are there more edges in groups than I would expect on the basis of chance?
If there are, then I found something here. So in order to actually define that, I have to say how I'm going to randomise the positions of my edges.
And there's more than one way you could do that. But in the simplest case, for instance, you could just randomise them uniformly.
Just take all your ideas and just move them around completely uniformly at random.
Okay. So you're comparing actual number of regimen groups with the number that you would get after you randomise things.
So there's a nice matrix formulation of this.
So we've already defined the adjacency matrix, which is 1 to 0, depending if there's an edge between I and J.
So AJ and ultimately JCC Matrix tells you the actual number of ages observed to fall between no danger.
It's either one or zero. There's either. It's there.
Whether you want to subtract from that the expected number of edges that would fall there if the edge positions were randomised.
So that's the thing I'm quoting here, P.J., in the simplest case,
that would just be equal to the overall probability of an edge if you just uniformly randomise them.
But for whatever randomisation procedure you define, there's some PJ which is the probability that an edge.
So actual minus expected number of edges B nodes I and J is AJ minus PJ.
And then the modularity itself is just the sum of that over all pairs of those that fall in the same group.
So consider, for instance, the simple case where I'm just dividing the network into two groups.
I'm going to do that. I'm going to turn that into something that I know about by putting an ising spin on every node of the network.
So spin up or spin down to represent. Well, I'm in group one or in group two.
I'm just dividing into two. So plus or minus one, I've got some spin variable SRB, which is plus one athletics.
I've lost one and minus one if it was 30. So now it turns out I can write this modularity very simply in terms of that.
I just do some arithmetic and I end up with this expression here, which says A leading constant that I don't care about.
Ignore this one over four and then some over spins on J by sister.
So these are the spin variables by J is just this thing we had before.
It's just AJ minus PJ. So those are both matrices that I know.
Right. So this thing looks very like some sort of disordered spin model that we're used to.
And my goal is to maximise this. So you give me a network that fixes this matrix by some of what's called the modularity matrix.
And my goal is to maximise this by finding the spins that give me the largest
value of the modularity that gives me my division of the network into two groups.
So I can't do that. Really. That's a hard problem.
If there's any spins, there are two to the end possible configurations of spins, too many of them to look through exhaustively.
So I'm going to use an approximate strategy. I'm going to write my modularity in matrix terms here as vector SX times matrix B times vector.
So matrix B is again this modularity matrix that we have.
If we previous transparency and vector s is just the element vectors vector that has the ising spins in it, the plus and minus ones.
So the goal is you give me a B, I want to find the S2, maximise its number, right.
So the way I do that is it's a hard maximisation. It's discrete maximisation I can't do.
So I'm, I relaxes, I use a relaxation method in which instead of confining the spins to be only plus one or minus one, I let them be any real number.
Okay, so this is fairly standard thing in statistical physics language.
I'm using a circle model instead of using an easy model that then becomes now an easy problem to solve
because there are continuous variables and I can just differentiate to find where the maximum is.
And it turns out the maximum is given by the leading eigenvector of this matrix, the modularity matrix.
That's only an approximation to the true answer, but it turns out it's an approximation that works well.
Here's one fun example that I got from all this again. This is a network of books.
So nodes in this network represent books. They're all books about US politics, and they're all written around 2004,
the time of the last US presidential election won the election between George W Bush and John Kerry,
and they're conveniently colour coded blue and red here.
For some reason in America, blue means left wing and red means right wing.
I have no idea why. It's just the opposite to everyone else in the world. But so blue and red.
So like over here on the red side, you have the face of George W Bush, and over here you have the lies of George W Bush.
So Augustus went through these all and decided whether they were left wing books or right wing books by reading the blurb.
And and then what are the edges in this network?
The edges are frequent co purchasing on the online bookseller Amazon.com.
So you go on Amazon, you know, the thing that says people bought this book, bought these other books.
So it's that. Right? He just looked up all of these books on Amazon, made this network.
So the point here is that everybody is just preaching to the choir.
People who buy blue books by other books. People who buy read books by other read books.
In other words, we believe that there is strong community structure in this network to communities,
Democrats and Republicans, and indeed feedback through this spectral algorithm.
And you find two very nice communities that correspond very closely to the the classification of the books, build a did based on things.
So I'm only telling you purchasing information, I'm telling you nothing about the titles, the contents, the authors, anything about the books.
And yet you can very clearly see through the polarisation of politics into left and right just by looking at the structure of this network.
Okay. So fine. This is a nice algorithm.
Works well in practice for actually finding structure.
Widely used method for finding community structure networks.
What I want to ask though is. How do we expect it to behave?
I want to understand how it works. And again,
I'm going to do that by looking at a simple model of a network that has community structure in it and asking what the spectrum is going to look like.
So the model that I use in this case is only a little bit more complicated than the other models I've been talking about.
It's something called a stochastic block model. It's a it's a well-known model that goes back to the 1980s.
The definition is I take some number of nodes. I divide them up into groups.
And then I throw down edges at random, just like I did in the random graph.
But now with two different probabilities for edges pins the pin is edges inside groups and P out is edges between groups.
I'm going to make P and bigger than P out, so I'm going to get more edges inside the groups, a few edges between the groups.
In other words, I'm going to get a network that looks very like the ones I sketched before.
It's got traditional community structure, dense clumps of nodes in the network.
This model is still sufficiently simple, however,
that we can actually calculate the entire spectrum of the matrix for it so we can understand how this algorithm is going to work.
So again, I won't go through the calculation in detail, but more around the matrix theory.
End result is semicircle like before and an outlying eigenvalue here, and we can calculate where the band edge is and where the fat lies.
The parameters here see in and see out and just re scaled versions of those
probabilities p and and p out rescale by the number n of nodes in the network.
So in calculate the entire spectrum.
And again, my conjecture is that if two of these eigenvalues cross over, like, for instance, if this one meets the band edge, then get close to zero.
I'm going to get some interesting structural phase transition in my system.
And indeed that turns out to be true. So.
So the argument goes something like this if if there were no community structure in my network at all.
In other words, if C in was just equal to C out, then this eigenvalue would disappear altogether.
And I would just have the semicircle.
The way to see that is that this matrix B that I'm using here is precisely the shifted adjacency matrix that I talked about before.
It's the adjacent matrix minus its average value is the expected value.
So I get just the semicircle and nothing else.
When I do that calculation. So if there is no community structure, I expect this value to disappear.
Right? So the presence of that value reveals to me that I have structure in my network.
That's. That's how I can tell that it's there. Right. So so now what I do is I'm going to vary the values B, C and C out,
make them closer together, which makes the structure in my network weaker and weaker.
And when they actually meet, it's going to vanish altogether. But the interesting thing is that that eigenvalue disappears before that point.
It meets the edge of the band and so disappears into the band.
You'd think it might happen when there was no community structure in the network, when it was just equal to C out.
But it actually happens before that. There is an earlier point where there's still community structure in the network.
We know it's there because we put it there. Right. C and see how still different from each other.
So the structure is there, but the spectrum doesn't reveal it.
It just disappears and it happens. And this phase transition point here, you can calculate where the transition is.
All right. So I won't go through this in detail maybe, but you can calculate.
So the order parameter in this case is basically how many nodes do we get, right?
Right. So the problem is I give you this network which has, say, two planted communities in it.
I know who belongs to which communities because I made up everything.
Right? I created the network myself. And then I feed it into this algorithm and I ask, does it get it right?
How many nodes is it classify right? So that's my order parameter in this particular case.
And it turns out I can calculate that. So the idea basically is you look at the eigenvectors of this.
You look at the elements of this leading eigenvector,
and you classify the nodes into one group or another, depending on whether they're plus one or minus one.
Right. Spin up or spin down. Well, they're not exactly plus one or minus one, because remember, we relaxed the problem.
We made them real numbers. So they're actually not a bad approximation. A bunch of them are plus and a bunch of them minus.
So in this particular case, the first 500 nodes were group one and the second 500 Group two.
However, some of the nodes, it gets wrong and you can see that those are the ones where the line crosses zero.
Right. And classifying them into one group or the other, depending on whether they're positive spins or negative spins.
So if they cross the zero line and a positive one becomes negative.
You got it wrong. So it's the number of places where it crosses the zero line.
That's your estimate of how many spins you classify wrongly.
Okay. We can actually calculate that exactly. Again, by doing some random matrix theory.
We can get an exact expression for the number of spins we expect to classify correctly.
So here's what the order parameter looks like. It actually doesn't go to zero.
It goes 2.5 because point five is complete failure.
In this case, I've got two groups of nodes I could get.
I could classify things correctly at the 50% level just by tossing a coin.
Right. So the worst you can do is 50%, not zero here.
So this is fractions correctly classify nodes. When the structure in the network is very strong, you actually get 100% of the right.
But there is a sharp phase transition at which you fail completely.
Solid lines. Here are the theoretical calculation and the dots, numerical calculations on real networks.
And they agree pretty well, except for some sort of fuzziness around the phase transition.
So what this is saying is in this region, over here to the left, there is structure in the network, but you cannot detect it.
In fact, it turns out that the result is even stronger than this.
There is some beautiful recent work by a group in France for really In the Cell and collaborators in Paris,
which shows that not only does this spectral algorithm fail to detect the structure in the network below this phase transition,
but every algorithm must fail below this transition.
This is, I think, a really deep and interesting finding.
It says that there exist networks that have a structure in it, but it's fundamentally impossible to detect it.
No algorithm will detect it.
It's kind of like the incompleteness theorem, which shows that there are results that are true, but you'll never be able to prove that they're true.
It's a similar kind of thing. These networks, they're artificial.
You know, we're not really interested in the stochastic block model. But it's interesting as an existence proof.
It tells you that there are certain kinds of structures in networks which you will never be able to detect.
And this is a new understanding that we didn't have before.
You know, we might have hoped, you know, just how like how Bertrand Russell hoped that you could prove everything in mathematics.
We might have hoped that if there is structure in a network, we will always be able to come up with some way of detecting it.
This result tells us that that is not true, that there are some kinds of structure in networks which will always be undetectable, that they're there.
We know that in this case because we put them there and yet no method can detect them.
I'm just about out of time, so I should stop talking now. Before I do, I just want to say thank you to my terrific collaborators on this work.
First, three students and former students in my group lost to a faculty collaborators.
These folks gave us money. Thank you for your attention. That's it.