Explore
For Enterprise
Join for Free
Log In

Гуманитарные науки и искусства
Бизнес
Компьютерные науки
Наука о данных
Информационные технологии
здоровье
Математика и логика
Личное развитие
Естественные и технические науки
Социальные науки
Изучение языков
Степени
Сертификаты

Полный обзор Coursera

Обзор
Поиск
Для организаций
Войти
Присоединиться бесплатно

2.8: A Threshold Theorem (optional/advanced 13:00)

Loading...

Социальные и экономические системы: модели и анализ

Стэнфордский университет

4.8 (оценок: 440) | Зарегистрировано учащихся: 33K

Learn how to model social and economic networks and their impact on human behavior. How do networks form, why do they exhibit certain patterns, and how does their structure impact diffusion, learning, and other behaviors? We will bring together models and techniques from economics, sociology, math, physics, statistics and computer science to answer these questions. The course begins with some empirical background on social and economic networks, and an overview of concepts used to describe and measure networks. Next, we will cover a set of models of how networks form, including random network models as well as strategic formation models, and some hybrids. We will then discuss a series of models of how networks impact behavior, including contagion, diffusion, learning, and peer influences. You can find a more detailed syllabus here: http://web.stanford.edu/~jacksonm/Networks-Online-Syllabus.pdf You can find a short introductory videao here: http://web.stanford.edu/~jacksonm/Intro_Networks.mp4

Просмотреть программу курса

Получаемые навыки

Social Network, Game Theory, Network Analysis, Network Theory

Рецензии

4.8 (оценок: 440)

5 stars
368 ratings
4 stars
62 ratings
3 stars
8 ratings
1 star
2 ratings

MG

Apr 17, 2018

Great survey course for social network analysis. Dr. Jackson's lectures motivated me to buy the book, and I hope to come back to this course later to work more on the optional parts.

TC

Apr 30, 2017

An overview of concepts and models of how networks form. There are applicable with basic concepts from probability theory, statistics, and some light calculus astonishingly well.

Из урока

Background, Definitions, and Measures Continued

Homophily, Dynamics, Centrality Measures: Degree, Betweenness, Closeness, Eigenvector, and Katz-Bonacich. Erdos and Renyi Random Networks: Thresholds and Phase Transitions

2.1: Homophily10:05

2.2: Dynamics and Tie Strength 6:44

2.3: Centrality Measures 14:31

2.4: Centrality – Eigenvector Measures 13:07

2.5a: Application - Centrality Measures 12:50

2.5b: Application – Diffusion Centrality 6:46

2.6: Random Networks 10:10

2.7: Random Networks - Thresholds and Phase Transitions 7:09

2.8: A Threshold Theorem (optional/advanced 13:00)13:00

2.9: A Small World Model 7:26

2.10 Week 2 Wrap3:33

Преподаватели

Matthew O. Jackson
Professor

Текст видео

Okay, so I'm going to take you through a threshold theorem, for those people who

are interested in seeing a little more detail, exactly how these thresholds work.

And how some of these things are proven, just to give you a feel for

the type of proof that works in this setting.

And so the one that we're looking at is going to be

one of the more interesting theorems, coming out of Erdos and Renyi.

So what we're looking at is that a threshold function for

the connectedness of one of these.

Plus some of our GMP random networks is the point at which

the probability of forming a link is proportional to log(n)/n.

So if this then tells us that if p(n),

Is much larger than this, then so if p(n) is much larger than log(n)/n,

then we're going to have a connected network.

And if it's much smaller than this, then the network is not going to be connected,

and we're going to have different components in it.

Okay, so that's the theorem.

And what we're going to do is just sort of work through part of the proof which

basically carries the main intuitions of the proof.

And there's still some details that you have to work out, and

I'm not going to go through all of the details.

But this will give the essential bits of the proof.

And so one thing we can do is show that if p(n) compared to this threshold goes to 0,

so if that p is much smaller than this threshold,

then there's going to be isolated nodes with probability 1.

So if there's isolated nodes, then certainly the network can't be connected.

Whereas if p(n) compared to t(n) goes to infinity,

then there can't be any components with less than half the nodes.

So all components have to have more than half the nodes, and basically,

that means they have to be one giant component.

So the idea here is going to be to show that if you're much smaller than this,

you're going to get some isolated nodes.

And if you're much bigger than this,

you're not even going to get any isolated components.

And what I'll do is really concentrate on the fact that showing that there

are isolated nodes, or there aren't isolated nodes is at this threshold.

And the idea that showing that a small component can exist or

not exist is more or less just a small variation on this proof.

Okay, so first of all, just to remind you of some useful approximations of

the exponential functions, so in case you're calculus,

or your pre-calculus is a little bit rusty.

So definitions of the exponential function, two forms

that'll be very useful in this course in terms of understanding properties.

It's going to be one is it.

If we look at e of zx we can also think of that as just looking at the limit

of a process where we do 1 + x/n raised to the nth power.

So think of this as continuous compounding of interest.

It looks like e to the x.

So the limit is n becomes quite large if 1 + x to the n/n equals the exponent.

Another is a Taylor series approximation for the exponential function.

We can write the exponential function as the sum of x to the n/n factorial.

[COUGH] So that's another way of getting that, and

you can go through your Taylor series approximation if you like.

But that'll be a useful approximation.

And here what we're going to do is approximate probabilities of these events

happening.

And then using these approximations, we'll be able to get things back in

terms of exponentials, and then logarithmic functions.

Okay, so what we're going to show now is that

right at the point where you're expected number of connection looks like log(n).

So this is going to be the point where P is proportional to log(n)/n, right?

So the expected degree is just multiplying up by n minus 1, or roughly n.

This is the threshold above which we expect each node to have some links, and

below which we expect nodes to be isolated.

And in fact, this is the threshold above which we expect nodes to have many links.

And once each node has many links,

the chance of having disconnected components vanishes.

So basically the logic is we're going to show that this part of it,

and the rest is a fairly simple variation, okay?

So first thing we're going to do is we're going

to write the expected degree as some function r+log(n), okay?

So the expected degree is actually some r+log(n).

And what we're going to then do is now is do calculations for

the probability that some node is isolated.

Okay, so how is that going to depend on this expected degree?

So the probability that some link is not present.

So I look at a given node, and I ask what's the probability that it's isolated?

Well, it's the probability that it has no links.

What's the probability that it doesn't have one of its links?

Well, that's 1- p.

What's the probability that it has none of its links?

Well, that's the probability that none of them formed.

So 1-p times 1-p times 1-p times, raised to the n-1 power.

So this is the probability that some node is isolated, okay?

And so what we want to do is to then show that the probability, if p is small

enough, then you are going to have a high probability of these nodes being isolated.

And if p is large enough,

then you're not going to have any probability of this happening.

So the probability that you're isolated is 1- p to the n -1 power.

So probability that some node is isolated is this.

And now from the way we wrote the p, remember,

we wrote that the expected degree was r + log(n).

The expected p is just that divided by n- 1.

So this is the p.

So (1- p) to the n -1 is just 1- r plus log(n) over n- 1 raised to the n -1, okay?

So now we've got an expression for this.

And now we're going to use our approximation that we went through before.

I just told you the approximation for an exponential function.

So recall that, if we have some x running n off to infinity,

1- x/n, over n to the n, approximates e to -x.

Okay, so and that's true if x/n is small, so vanishing.

And in particular,

what we're going to need is r + log(n) to be small relative to n-1.

Now what I'm going to do is just assume that that's going to be true.

And the compression of the proof here for people who are really interested,

if r + log(n) is large relative to n, then this is a monotone property.

If it holds when it's small relative to n,

it's even going to hold more easily when it's large, right?

We're just adding more links.

So that part of the proof is quite easy.

So the case that's really going to be tough is when it's small relative to n.

And so what we're going to do now is look at this.

So now we've got an approximation.

We're approximating this by e to the minus, right?

So we've got e to the minus r + log(n)

as an approximation for this.

So the probability that some node is isolated begins to look like this, right?

And now we've approximated that using our exponential function.

So it looks like e-r-log(n), bring the log(n) out,

and we end up with the probability that some node is isolated.

Looks like e-r/n.

Well remember, r was our how much our p differed, or

expected degree differed from login.

Okay, so now we've got a simple formula for

the probability that some node is isolated for large n.

So if each one is isolated with a probability e-r over n,

then the expected number of isolated nodes is just n times this,

since nodes are identical in this world.

And so the n's cancel out.

And we get the expected number of isolated nodes as e to the minus r.

Okay, now we're pretty much all the way there.

If r is going to infinity, if r is getting quite large,

then the expected number of isolated nodes goes to 0.

If r goes to minus infinity,

then that tells that the expected number of isolated nodes becomes infinite, right?

So basically, what we're getting here is a function of r.

If it's either getting very largely positive,

meaning that the threshold is exceeded by p, or if it's getting very negative.

So that p is much smaller than the threshold, then we're either seeing

the expected number of isolated nodes going to 0, or going to infinity, okay?

And so basically, the expected number of nodes,

isolated nodes goes to 0 if r(n) tends to infinity,

and to infinity if r(n) tends to minus infinity.

So the expected number of isolated nodes tends to 0.

If that's tending to 0,

then the probability of having one has to tend to 0, right?

You can't have the expected number be 0, and

have the probability of having one be positive.

So significantly higher than 0.

So the probability of having 1 is going to have to tend to 0.

And so this tells us now that basically,

if we're sitting in a situation where r(n) goes to minus infinity,

then the expected number of tends to 0,

the probability of having one tends to 0.

So basically, if p is much bigger than this t(n)

being log(n) over n, then we've got a situation

where the expected number of isolated nodes goes to 0.

And the probability of having an isolated node goes to 0.

Vice-versa, if it's going to infinity,

then an extra step, play with the variance.

You can't get the expected number going to infinity without having

the probability of having at least one go to 1.

So it's impossible to have the expected number go to infinity,

and not have a probability going to 1 of actually having 1.

So that's an extra step that I'm not going to go through, but

it's a fairly easy one to do in terms of Chebyshev's inequality.

Okay, so this was just one example.

I don't expect you to digest all of this under first pass.

You can go through book in much more detail if you want to see

one of these proofs worked out in full detail.

But what I wanted to communicate to you through this derivation is

just the type of reasoning it goes through.

So what you do is you want a certain probability, you can get that probability

in terms of approximations based on exponential functions often.

That approximation then, now we know if for large n,

it becomes fairly accurate, and that gives us bounds on probability.

So we can say that the probability of something is either it has to be tending

to 1, or it has to be tending to 0,

based on what these functions have to be converging to as n becomes very large.

And those threshold functions

come from identifying where is it that these expressions either go to 1 or to 0?

And whether we're talking about isolated nodes, or we're talking about the first

link appearing, etc, it's going to be a different threshold.

And so the proofs tend to have the same kind of structure to them.

They're just going to differ in the particular expressions,

depending on whether we're talking about one type of threshold in one property, or

a different property in a different threshold.

But this type of analysis is what underlies a lot of random graph theory,

and a lot of the proofs behind the scenes in terms of establishing properties

of random graphs in large settings.

Okay, so that's just one example.

Now we're going to take a look at some other types of random network models, and

other kinds of things that we might be to establish when using them.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play

Coursera
О проекте
Руководство
Карьера
Каталог
Сертификаты
Сертификаты MasterTrack™
Степени
Для организаций
Для правительственных организаций

Сообщество
Learners
Partners
Developers
Beta Testers
Translators

На связи
Блог
Facebook
LinkedIn
Twitter
Instagram
YouTube
Технический блог

Еще
Условия
Конфиденциальность
Помощь
Доступность
Пресса
Контакты
Справочник
Филиалы