Graph Theory and Social Networks: Alexandru Costan

1
Graph Theory and

Social Networks
Alexandru Costan
2
Outline
•  Graphs problems and

representations
•  Structure of social
networks
•  Applications of
structural analysis
3
Source: Wikipedia (Königsberg)

What is a graph? 4
•  G = (V,E)
•  V represents the set of vertices (nodes)
•  E represents the set of edges (links)
•  Both vertices and edges may contain additional information
•  Different types of graphs:

•  Directed vs. undirected edges
•  Presence or absence of cycles
•  Graphs are everywhere:

•  Hyperlink structure of the Web
•  Highway system
•  Social networks
Some graph problems 5
•  Finding shortest paths

•  Routing Internet traffic and UPS trucks
•  Finding minimum spanning trees
•  Telco laying down fiber
•  Finding Max Flow
•  Airline scheduling
•  Identify “special” nodes and
communities
•  Breaking up terrorist cells, spread of
avian flu
•  Bipartite matching
•  Tinder
•  PageRank
6
Graphs are hard!
•  Poor locality of memory access
•  Very little work per vertex
•  Changing degree of parallelism
•  Running over many machines makes the
problem worse
•  Graph storage:
•  Flat Files: no query support
•  RDBMS: can store the graph with limited
support for graph query
•  State of the art today:
•  Write your own infrastructure
•  MapReduce – tends to be inefficient
7
Distributed Graph Processing
•  Google’s Pregel
•  Large-scale graph processing
•  Vertex centered computation
•  Apache Giraph
•  Open source
•  Iterative graph processing
•  Used at Facebook
•  Twitter’s Cassovary
•  In-memory computation
•  Used for: “Who to Follow” and “Similar to”
•  Very simple to use (no need for persistence, databases or partitions)
•  Neo4j Graph Database
•  Flexible schema
•  Powerful query language, ACID
Representing graphs 8
Two common representations:
•  Adjacency matrix
•  Adjacency list
Adjacency matrices 9
Represent a graph as an n x n square matrix M

•  n = |V|
•  Mij = 1 means a link from node i to j
2
1 2 3 4
1 0 1 0 1 1
3
2 1 0 1 1
3 1 0 0 0
4 1 0 1 0 4
Adjacency matrices: critique 10
Advantages:
•  Easy mathematical manipulation
•  Iteration over rows and columns corresponds
to computations on outlinks and inlinks
Disadvantages:
•  Lots of zeros for sparse matrices
•  Lots of wasted space
Adjacency lists 11
Take adjacency matrices… and throw away all the

zeros
1 2 3 4
1 0 1 0 1 1: 2, 4
2 1 0 1 1 2: 1, 3, 4
3 1 0 0 0 3: 1
4: 1, 3
4 1 0 1 0
Adjacency lists: critique 12
Advantages:
•  Much more compact representation
•  Easy to compute over outlinks
Disadvantages:
•  Much more difficult to compute over inlinks
Social graphs 13
14
Social graphs
•  Asymmetric follow
relationship: very
skewed graphs
•  Very valuable “interest

graphs”
•  Huge graphs:
15
What can networks tell us?
•  The strength of weak ties [Granovetter ’73]
•  Motivating question: How do people find

new jobs?
•  Through acquaintances rather than close friends
•  Surprising fact: discovery is enabled by weak ties
•  Understanding structure affords deep insights
•  Interplay between sociology and graph theory

16
Triadic Closure
Question: What are the mechanisms by which node arrive and depart
and by which edges form and vanish?
BC closes
the triangle
If two people in a social network have a friend in common, then there is

an increased likelihood that they will become friends themselves at some
point in the future
17
Triadic Closure
Over time…
… new edges are forming.
But not all due to triadic closure (e.g. DG)

18
Clustering Coefficient
•  The probability that two randomly selected friends

of A are friends with each other.
•  The fraction of pairs of A’s friends that are
connected to each other by edges.
•  For node A:
•  at a) 1/6
•  at b) 1/2
•  The more strongly triadic closure is operating in
the neighborhood of the node, the higher the
clustering coefficient will tend to be.
Reasons for Triadic Clousure 19
•  Opportunity
•  Trust
•  Incentive
20
Strength of weak ties
•  Definition: a bridge in a graph is an edge whose

removal disconnects the endpoints.
Bridges are presumably extremely rare in real

social networks!
21
Strength of weak ties
•  Definition: a local bridge in a graph is an edge

whose endpoints have no common neighbor.
22
Types of edges
•  Structural approach:
•  Local bridges or not
Challenge: how to link them ?
•  Interpersonal approach:
•  Weak or strong
23
Strong Triadic Closure
•  Strong Triadic Closure Property: if the node

has strong ties to two neighbors, then these
neighbors must have at least a weak tie between
them.
Local bridges and weak ties 24
•  Claim: If a node A in a network satisfies the

Strong Triadic Closure Property and is
involved in at least two strong ties, then
any local bridge it is involved in must be a
weak tie.
•  Consequence: all local bridges are

weak ties!
Strength of weak ties 25
26
Strength of Weak Ties
•  Discovery is enabled by weak ties

•  Surprising strength of weak ties!
•  Simple structural model explains this

cleanly
•  Applies to Twitter/Facebook
Tie strength on Facebook 27
Tie strength on Twitter 28
•  Stronger…
•  Directed tweets: @someone
•  … and weaker ties
•  Followers
•  The number of strong ties remains

relatively modest
•  Bellow 50 even for users with over 1000
followers.

Graph Theory and Social Networks: Alexandru Costan

Uploaded by

Copyright:

Available Formats

Graph Theory and Social Networks: Alexandru Costan

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Graph Theory and Social Networks: Alexandru Costan

Uploaded by

Copyright:

Available Formats

1

Graph Theory and

• Graphs problems and

Source: Wikipedia (Königsberg)

• Different types of graphs:

• Graphs are everywhere:

• Finding shortest paths

Two common representations:

Represent a graph as an n x n square matrix M

Take adjacency matrices… and throw away all the

• Very valuable “interest

• The strength of weak ties [Granovetter ’73]

• Motivating question: How do people find

• Understanding structure affords deep insights

• Interplay between sociology and graph theory

If two people in a social network have a friend in common, then there is

… new edges are forming.

But not all due to triadic closure (e.g. DG)

• The probability that two randomly selected friends

• Definition: a bridge in a graph is an edge whose

Bridges are presumably extremely rare in real

• Definition: a local bridge in a graph is an edge

Challenge: how to link them ?

• Strong Triadic Closure Property: if the node

• Claim: If a node A in a network satisfies the

• Consequence: all local bridges are

• Discovery is enabled by weak ties

• Simple structural model explains this

• The number of strong ties remains

You might also like

•  Graphs problems and

•  Different types of graphs:

•  Graphs are everywhere:

•  Finding shortest paths

•  Very valuable “interest

•  The strength of weak ties [Granovetter ’73]

•  Motivating question: How do people find

•  Understanding structure affords deep insights

•  Interplay between sociology and graph theory

•  The probability that two randomly selected friends

•  Definition: a bridge in a graph is an edge whose

•  Definition: a local bridge in a graph is an edge

•  Strong Triadic Closure Property: if the node

•  Claim: If a node A in a network satisfies the

•  Consequence: all local bridges are

•  Discovery is enabled by weak ties

•  Simple structural model explains this

•  The number of strong ties remains