You are using a browser not supported by the Wolfram Cloud
Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.
I understand and wish to continue anyway »
WOLFRAM NOTEBOOK
Social Networks
Social Networks
Graph Recap
Graph Recap
A graph is a collection of objects sharing some form of relationship. These objects are referred to as vertices (or nodes) and the relationships as edges (or links).
Undirected, unweighted graph
Undirected, unweighted graph
Graph{sa,ad},
Out[]=
Directed, unweighted graph
Directed, unweighted graph
In[]:=
Graph{s->a,a->d},
Out[]=
Undirected, weighted graph
Undirected, weighted graph
Graph{sa,ad},EdgeWeight{30,10},
Out[]=
Directed, weighted graph
Directed, weighted graph
In[]:=
Graph{s->a,a->d},EdgeWeight{20,15},
Out[]=
Graph v.s Network
Graph v.s Network
◼
Note: Not the network that is the Internet
◼
Essentially the same. Graph used more in formal areas and Math. Network used more in applied areas.
◼
A network usually refers to a graph that has been derived from a structured process and often has meaning in particular contexts.
◼
A network can refer to a graph in which vertices and/or edges have properties.
◼
A typical network might be an edge-weighted graph where the weights of edges refer to costs, lengths or capacities.
Examples of Networks
Examples of Networks
Out[]=
Computer sciences | Database design, data mining, web mining, … |
Sociology | Social networks, … |
Physics | Models of phase transition, magnetism, … |
Ecology | Food webs, … |
Economy | Models of markets, sponsored search markets, … |
Business informatics | Organisation diagrams, event-driven process chains, … |
Bioinformatics | Models of epidemics, metabolic networks, … |
Social Networks represented by Graphs
Social Networks represented by Graphs
Graphs can be used to represent social networks
◼
Vertices are people
◼
Edges are relationships
In[]:=
ExampleData[{"NetworkGraph","FamilyGathering"},"LongDescription"]
Out[]=
A social network of close family ties among people at a family gathering. Two persons have a tie if they are related as a couple, as siblings, or as parent-child.
In[]:=
fg=ExampleData[{"NetworkGraph","FamilyGathering"}]
Out[]=
Graph Properties
Graph Properties
Graphs have properties that convey useful information.
In[]:=
fg
Out[]=
Number of vertices (number of people in this family):
In[]:=
VertexCount[fg]
Out[]=
18
Number of edges (number of distinct relationships):
In[]:=
EdgeCount[fg]
Out[]=
31
List all the vertices (members of the family):
In[]:=
VertexList[fg]
Out[]=
{Elisabeth,James,Anna,John,Dorothy,Linda,Michael,Larry,Carol,Nancy,David,Nora,Julia,Ben,Oscar,Felicia,Arlene,Rudy}
List all the edges (the relationships):
In[]:=
EdgeList[fg]
Out[]=
{ElisabethAnna,JamesAnna,JamesLinda,JamesLarry,JamesNancy,AnnaLinda,AnnaLarry,AnnaNancy,LindaLarry,LindaNancy,LarryNancy,JohnDorothy,JohnDavid,DorothyDavid,LindaMichael,LindaNora,LindaJulia,MichaelNora,MichaelJulia,NoraJulia,LarryCarol,LarryBen,LarryOscar,CarolBen,CarolOscar,BenOscar,NancyDavid,NancyArlene,DavidArlene,OscarFelicia,ArleneRudy}
The vertex degree for a vertex is the number of edges incident to .
List the number of edges incident to each vertex:
v
v
List the number of edges incident to each vertex:
In[]:=
VertexDegree[fg]
Out[]=
{1,4,5,2,2,7,3,7,3,6,4,3,3,3,4,1,3,1}
Number of edges associated with a particular vertex:
In[]:=
VertexDegree[fg,"Anna"]
Out[]=
5
Find the set of vertices with maximum vertex degree:
In[]:=
GraphHub[fg]
Out[]=
{Linda,Larry}
The greatest distance between any pair of vertices:
In[]:=
GraphDiameter[fg]
Out[]=
5
Shortest path between two vertices:
Cliques are special graphs. Each vertex is connected to every other vertex.
Small World Graph
Small World Graph
Human relationships—the social graph—form a graph now called a small-world graph, named after the expression, “It’s a small world!”
Small world graphs have certain properties:
◼
small diameter and typical path length,
◼
local cliques,
◼
densely connected,
◼
heavy tail
Small Diameter
Small Diameter
Any two people in the world are separated by short paths, on average about six steps.
People who may be very far apart physically and socially are still connected with relatively small paths.
People who may be very far apart physically and socially are still connected with relatively small paths.
This table is NOT meant to be precise, just to give you an idea of how slowly diameter grows.
Most person-to-person distances are smaller.
Most person-to-person distances are smaller.
◼
In late 2011, Facebook studied their network, which had around 720 million users at the time. Average shortest path length was 4.74 (Backstrom et al., 2011).
Is our family graph an example of a small world graph?
Is our family graph an example of a small world graph?
Six Degrees of Separation
Six Degrees of Separation
Popular ideas about six degrees of separation:
The Experiment
The Experiment
◼
In a 1969 study, researchers Stanley Milgram and Jeffrey Travers asked 296 people in Nebraska and Boston to send a letter through acquaintances to a Boston stockbroker.
◼
Only 64 of the letters reached the stockbroker.
◼
Of those letter chains that were complete, the average number of degrees of separation was 6.2.
Should we play the game “Six Degrees of Kevin Bacon”?
Should we play the game “Six Degrees of Kevin Bacon”?
Pick the movies Apollo 13. List the cast of the movie who can all be considered as his co-stars:
So there will be an edge from Kevin Bacon to Tom Hanks.
Vertices in the graph are the actors and edges represent the fact that they co-starred in some movie.
A graph of all of Kevin Bacon’s costars:
Number of actors Kevin Bacon co-starred with across his movies:
Now list Tom Hanks’s movies:
Number of costars across all the movies Tom Hanks has starred in (including Kevin bacon).
Pick the movie “Sully” for example. Aaron Eckhart is his costar in the movie.
So we can draw a graph with an edge from Kevin Bacon to Tom Hanks to Aaron Eckart and go on in this way.
I picked only 5 costars for each actor to grow my graph.
Social Networks as Small World Graphs
Social Networks as Small World Graphs
Social networks inherit properties of small world graphs and capture human relationship
◼
has dense local structure (a person’s friends tend to know one another)
◼
most of the graph is reachable in a small number of hops ( we are all connected)
◼
some nodes have high degree ( the influencers!)
Computing on Social Networks
Computing on Social Networks
Communities
Communities
Communities in a graph are clumps of nodes that are more connected to each other than to the rest of the graph.
Find a clique:
Recreate the graph with the exact same connections as the original, but with the nodes arranged to illustrate the “community structure” of the graph:
List the vertices:
Most connected vertices:
Vertices that are on many shortest paths of other vertex pairs--are important in maintaining the connectivity in the graph.
Graph Mining
Graph Mining
A network of books linked by the same buyers on Amazon.com:
Find sets of three books bought together:
Find the largest selection of books frequently bought together that includes The Clinton Wars:
Find the largest selection of books including The Clinton Wars that was frequently bought by buyers who previously bought a common book:
Storing and Providing Access to a Social Graph
Storing and Providing Access to a Social Graph
How do companies store and provide access to a social graph?
Facebook’s TAO architecture (perhaps “Total Association and Object”)
Facebook’s TAO architecture (perhaps “Total Association and Object”)
Edges of any type from any node
◼
are organized into lists
◼
and kept sorted from newest to oldest,
◼
which matches the viewing model (and user interest).
TAO keeps the graph
◼
cached in memory:
◼
fast, but expensive.
The graph is too big to fit on one machine, so TAO breaks it up into pieces.
Each Node and Associated Edges Map into One Piece
Each Node and Associated Edges Map into One Piece
◼
The social graph is split into many shards (pieces) ... perhaps millions.
◼
Each node maps into one shard, along with all edges associated with that node.
◼
Shards are mapped onto servers (perhaps thousands).
Full Copy of Graph in Each of a Few Datacenters
Full Copy of Graph in Each of a Few Datacenters
◼
The social graph is densely connected, so each shard has a lot of edges into other shards.
◼
To avoid latency (or more copies), Facebook puts more computers into fewer datacenters, and puts a full copy of the graph in each datacenter.
Datacenters Provide Data Fast at Expense of Consistency
Datacenters Provide Data Fast at Expense of Consistency
◼
Vast majority of operations (100× ?) on the social graph are reads—
◼
Facebook favors:
◼
fast, high-bandwidth reads
◼
over strong consistency (everyone sees the same thing at the same time).
Social Networks and Society
Social Networks and Society
Fake News Travels the Network
Fake News Travels the Network
◼
Social networks have been repeatedly spotlighted for their role in distributing and increasing the effectiveness of disinformation
Trust Issues
Trust Issues
◼
Assumptions about behavior fail in a social network
◼
Hacking and spoofing can be used maliciously
Some of the top influencers on Social Networks
Some of the top influencers on Social Networks
Reference
Reference
◼
Analyzing the Social Web by Jennifer Golbeck
◼
Center of Attention: How Facebook Users Allocate Attention across Friends by Backstrom et al.