Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Graph Theory: Facebook


Jen Mathews

on 10 May 2010

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Graph Theory: Facebook

Graph Theory:
In my Internet?

Facebooking & Googling with Eigenvectors
What is a graph?
collection of vertices (or nodes)
with edges between them
edges- relationship
Social Network
edges- social realtionship

Measurements of Social Influence
The betweenness of a node P is the average number of
shortest paths between nodes which contain P.
The closeness of a node P is the average length of the shortest
path from P to all nodes which are connected to it by some path

The degree of a node is the number of other
nodes to which it is connected.

In a graph where social relationships are the edges, then the degree corresponds to the
number of friends
Degree Centrality
Jen Mathews
Influence function - Id
If p is a person, then
Id(p) = measure of their influence
Id(p) = deg(p) = # of friends of person p
single person with high degree
single person with low degree
but high connectivity
Using Eigenvalues
person's influence is proportional to
total influence of the poeple to whom
they are connected, lets call this Ie
How do we calculate λ?
Aij = 1 if p1 and p2 are joined by an edge
Aij = 0 otherwise
considers more than 500 million variables and 2 billion terms.

Pages that we believe are important pages receive a higher PageRank and are more likely to appear at the top of the search results.

PageRank also considers the importance of each page that casts a vote, as votes from some pages are considered to have greater value, thus giving the linked page greater value.

"We have always taken a pragmatic approach to help improve search quality and create useful products, and our technology uses the collective intelligence of the web to determine a page's importance." Google Corporate
Experimental Measurement
Xi = number of people "influenced" by Pi
Pi = the ith person in our network
Calculate the expected value of Xi
only accounts for topology
Techniques work on any general graph

Social networks can charge premiums for advertisements
because they are able to target

Better measurement allows organized marketing to increase

Need to explore specific influence
Works Cited
[1] "20 bits", Jesse Farmer
Let G be a graph with n vertices ,
V= {V1,......Vn}

The adjacency graph of G is
the nxn square matrix A(G) =
Id(p) = row sum of row p
Adjacency Matrix
[1] Brin, Sergey and Lawrence Page, The anatomy of a large-scale hypertextual web search engine, Computer Networks and ISDN Systems, Stanford University

[2] Corporate Information" <http://www.google.com/corporate/tech.html>

[3] Chung, Fan. "Graph Theory in the information age", University of California, San Diego, based on lecture given January 2009

[4] Farmer,Jesse. "20Bits", Nov. 2 2007, Graph Theory : Part III (Facebook)

[5] Parker, Laura. "The evolving face of social networks", Oct 7, 2009

[6] Wilf, Herbert S."Searching the web with eigenvectors", University of Pennsylvania, Philadelphia, PA, April 13, 2001
"I want to be able to calculate the relative level
of a person's friends and use that measuremment
to weigh whether their newsfeed items get
displayed for their friends"
Social network diagrams
PageRank diagrams
Suppose x1, x2, ....xn are the importances of all n of the websites

"We want the importance of each website to be proprotional to the sum of the
importances of all the sites that link to it" Wilf [6] so then a system of
equations could look like:"

x1= K( x86 + x75 + x309 )
x2= K( x1900 + x2010 +x40987 )

X1= n∑ j=1 (ai,j xj) (i= 1,...,n)
K= constant of proportionality

matrix A whose (i,j) entry is either 1 or 0
Page Rank Technology
WebPage Importance
Football teams!
Xi = strength of ith football team

Xi is proportional to the sum of the strengths
of all the teams they have defeated

X1= n∑ j=1 (Ai,j Xj) (i= 1,...,n)
How do we find the "top Ten"?
So find eigenvectors and look for the one in
which all the entries have the same sign ( all 1s)
Largest entry = highest ranking team
This represents six football teams
team 1 defeated teams 2 and 5,
team 2 defeated teams 1 and 5, etc.

The eigenvector of this matrix whose entries are all positive
is (.31, .31, .22, .57, .50, .43)
{ 0 1 0 0 1 0 }
{ 1 0 0 0 1 0 }
A= { 0 0 0 1 0 0 }
{ 1 0 1 0 1 1 }
{ 1 1 1 0 0 1 }
{ 1 1 0 0 1 0 }
As we get better at measuring what happens within social networks, I could see a lot more organized marketing efforts on social networks as well as as organized influence campaigns
Full transcript