**Graph Theory:**

In my Internet?

In my Internet?

Facebooking & Googling with Eigenvectors

**What is a graph?**

collection of vertices (or nodes)

with edges between them

nodes-abstract

edges- relationship

Social Network

vertices-people

edges- social realtionship

Connectivity

Betweenness

Closeness

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

Remember

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

EXAMPLE:

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

**Conclusion**

Techniques work on any general graph

Social networks can charge premiums for advertisements

because they are able to target

influencers

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

Downside?

[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

**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