Why are you less popular than your friends?
Download
Report
Transcript Why are you less popular than your friends?
Why are you less popular than
your friends?
MIDDLE COLLEGE
2013
Today’s plan: to answer the question as to why you are
less popular than average
Generate 3 networks; 2 random and 1 preferential
attachment
Calculate the measures of degree distribution,
clustering coefficient and path length
With 10 people how many connections can there be
in total?
Random Graph
n=5 p=½
1
1
2
3
4
5
2
3
4
5
X
X
X
X
X
Preferential Attachment Graph
The rich get richer
•Start with dyad, each end labeled 1,2
•Add node with 2 edges, one edge at a time, labeling ends sequentially
•Kite graph with 10 ends labeled
•Add 6 new nodes labeling the new ends as you add them
•Complete the Adjacency Matrix below and draw the network
Red Die
White
1
2
3
4
5
6
1
1
2
3
4
5
6
2
7
8
9
10
11
12
3
13
14
15
16
17
18
4
19
20
21
22
23
24
5
25
26
27
28
29
30
2 types of networks
Random
Formed when links occur with probability p
Hump degree distribution centred at np
Preferential attachment
Formed when ‘rich get richer’
Power law degree distribution
You have two networks
Clustering Coefficient
The probability that two randomly selected
neighbors of a node are connected to each other.
The proportion of the number of triangular
subgraphs among neighbors to the possible number
of triangular subgraphs.
The Formula
𝐶𝑖 =
2 𝑒𝑗,𝑘
𝑘𝑖 𝑘𝑖 − 1
𝑒𝑗,𝑘 =the number of edges between the neighbors of node 𝑖
𝑘𝑖 =the degree (number of neighbors) of node 𝑖
Example
𝑒𝑗,𝑘 = 1
𝑘1 =4
𝐶1 =
2(1)
2
1
=
=
4(4 − 1) 12 6
Degree is popularity
Pick a random node from your preferential
attachment graph (1-10)
Find the average degree of its friends
Compare to its degree
Is anyone more popular than average?
Why?
Triangle numbers
Where did the 45 possible edges come from?
What is the sum of the first n numbers?
Pascal’s Triangle
MIDDLE COLLEGE
2013
Blaise Pascal
French Mathematician
1623-1662 (died at the age of 39)
Invented the Mechanical Calculator (Pascaline)
while still a teenager.
Pascal’s Triangle
Each entry is equal to the sum of the two values
directly above it.
A formula can be obtained from the pattern in order
to find an appropriate set of values for any given row.
Patterns
Diagonals
Powers
Odds and Evens
Powers of 11
Prime Numbers
Hockey Stick
Fibonacci’s Sequence
The Triangle Entries
The entries are found by the combinatorial:
𝑛!
𝑛
=
𝑘
𝑘! 𝑛 − 𝑘 !
A factorial is the product of a natural number with all
of its successive natural number values.
𝑛! = 𝑛 𝑛 − 1 𝑛 − 2 … 3 ∗ 2 ∗ 1
Example:
5! = 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1 = 120
Creating the triangle using the combinatorial
1
0
2
0
3
0
0
0
1
1
2
1
3
1
2
2
3
2
3
3
And so on…
Binomial Coefficients
The triangle allows us to find the coefficients needed in
any binomial expansion:
𝑛
𝑥+𝑦
𝑛
=
𝑘=0
Think about it:
𝑛 𝑛 𝑛−1
𝑥 𝑦
𝑘
𝑥 + 1 3 = 𝑥 3 + 3𝑥 2 + 3𝑥 + 1
It is easy to multiply the perfect cubed binomial above. But
what if we have a much larger power? Do we really want to
multiply a binomial out 10 times? 15 times? 100 times?
Binomial Expansion
(a+b)1
(a+b)2
(a+b)3
Binomial Coin Flipping
Each person flip a coin 10 times, listing the heads and
tails
HHTHTTHTHH
How many different lists are there?
How many H do I expect?
How many lists have 0 H, 1H, 2H’s?
How many of the 210 lists have 5 H’s?
Binomial Coin Flipping
Say you did 4 coin flips.
How many H do I expect?
How many lists have 0 H, 1H, 2H, 3H, 4H’s?
See connection with a random graph?
If you flip 5 coins how many have 2H’s? Use your
lists from 4 flips.
Combinations
Say you have 3 books,
Harry Potter, Lord of the Rings and Differential Equations,
an Introduction
How many ways can I choose 2 books?
(1 book?)
How many ways can I choose 2 of 4 things?
How many ways can I choose 8 of 10 things?
Combinations
How many ways can I order 3 things in a row?
How many ways can I choose 3 of 10 things?
How many ways can I choose r of n things?
n! factorial
Proof by Induction
We want to prove that Pascal’s triangle gives you the
number of ways you can choose r from n items
Steps:
Show it’s true for the small numbers
Assume it’s true for a row in the triangle
Show it must be true for the next row.
Proof that every number is interesting?
Plinko
How many paths are there to each tube?
Notice the Gaussian curve forming
How much would you pay for the right to get $10 if
the ball ended up in a tube greater than 8?
What is the probability it ends up in tube greater
than 8?
Stocks and Options
What’s a stock?
Stocks can go up or down
See graph of real stock
What’s a call option?
Strike price
Graph the value of a call at expiry
How much should a call cost?
Pricing a call
Selling something short.
Eliminating risk
Consider a portfolio with 1 call option and Δ units of
shorted stock
V = C – ΔS
Today the stock is worth $100, tomorrow $104 or $92
with 50/50 chance
Binomial method of pricing
Build the formula to price a call given
u = 1+ a, d = 1- a
The stock is at $100 now, the call expires in 3 days
with an exercise price of $100.
a = 0.05
Sketch the payout at the time of expiry.
Price the call and then sketch the profit diagram