So we need to figure out something different. There's no
sensible base case that gives us a good recursive definition.
What we're do, going to do instead is what's called a
relaxation algorithm. And the basic idea is pretty simple. We're
going to start with a guess and then we're going to have
some loop where we keep going. We'll just say, while
we're not done, we'll figure out how to decide when
we're done. We're going to do something that makes a guess better.
So, that's the basic idea. That we don't have a good
stopping point and we don't have a clear starting point of saying
Alice's popularity is one, and we're going to define everything in that.
What we're going to do instead is we're going to start with a guess,
and our guess could be, well, let's assume everyone's initial popularity
is one. And then we're going to keep refining the guess. We're going to
have some process that updates the guess based on what we've learned.
And each time we do this, we're going to get better and better.
And at some point we're going to stop and we're
going to say well that's the result we want. So let's
think about how to do that for popularity scores.
So, instead of just having one input to popularity now,
there's going to be two. It's going to take the
time step, that's the number of times we've tried to
guess. And it's going to take the person, and it's
still going to output a score. And now we can define
this in a way that we do have a starting
point, which is the equivalent to having a stopping point in
a recursive definition. We'll define what the value is at
step zero. For any person, we'll say that the score is
1. And it didn't work to have a base case,
in terms of the person, because there's no clear ordering of
the people. We had a graph, we had lots of different
friendship connections, there was no clear starting point. We're going to add
an extra parameter which is our, our time step, and
that's going to be our base case. And if we think
of our time step as our base case, it's easy
to say that time step zero is our base case. And
at step zero, we're going to say everyone's popularity score is
one. And now we can have our update rule, which
says, we can figure out the popularity at any time
step t, where t is greater than 0 for any person,
and we're going to define that as the sum
over all their friends. So we're going to pick a
friend in their set of friends. So we're
going to go through each friend summing up the popularity
score of the friend. But instead of at time t, we're going to use time t minus
1. So that means we're looking for the
popularity of the friend in the previous step and
we're using that to compute the popularity of
the person they're friends with in this step. So
let me write out that more in pseudocode. If
we think of this as the Python procedure, it's
going to be something where we're taking in two
imports now, the time and the person. And now
we have the base case, if the time is
0, we're going to return the score is always 1.
If the time is not 0, well, we can compute the score similar to how we did
before. We're going to have the score at 0, we're
going to sum over the friends. We're summing over the
friends, updating the score, by adding the friends' popularity
score at the previous step. And when we're done,
the value of score is the result. So now
we have our new definition. We have it written
in mathematical notation at the top, and in the
Python code here. So the question is, is this a
good recursive definition? And I don't mean to ask whether
it's a good definition of popularity, let's hope it's not.
What I mean to ask is, for all possible inputs,
so all values we can pass in as t and
p, does the way we've defined popularity give us a
result? So here the possible choices. So, yes, it's only
good if people can't be friends with themself. It's good
only if everyone has at least one friend. Hopefully, everyone
does. But it's only a good definition if that's the
case. Or only if everyone is more popular than Alice.