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).
Graph{sa,ad},
Out[]=
In[]:=
Graph{s->a,a->d},
Out[]=
Graph{sa,ad},EdgeWeight{30,10},
Out[]=
◼
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:
In[]:=
VertexCount[fg]
Out[]=
18
Number of edges:
In[]:=
EdgeCount[fg]
Out[]=
31
List all the vertices:
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 associated with each vertex:
v
v
List the number of edges associated with 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:
In[]:=
GraphDistance[fg,"John","Julia"]
Out[]=
4
In[]:=
GraphDistance[fg,"Nora","Felicia"]
Out[]=
4
In[]:=
FindShortestPath[fg,"John","Julia"]
Out[]=
{John,David,Nancy,Linda,Julia}
In[]:=
FindShortestPath[fg,"Nora","Felicia"]
Out[]=
{Nora,Linda,Larry,Oscar,Felicia}
Cliques are special graphs. Each vertex is connected to every other vertex.
In[]:=
c=FindClique[fg]
Out[]=
{{James,Anna,Linda,Larry,Nancy}}
In[]:=
HighlightGraph[fg,Subgraph[fg,c]]
Out[]=
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?
How about Kevin Bacon and his co-stars?
How about Kevin Bacon and his co-stars?
Graph of Kevin Bacon and his co-stars:
Vertices in the graph are the actors and edges represent the fact that they co-starred in some movie.
Number of actors Kevin Bacon co-starred with across his movies:
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.
Now list Tom Hanks’s movies:
Number of costars across all the movies Tom Hanks has starred in (including Kevin bacon).
Pick hte movie “Sully” for example. Aarom 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!)
Get the Data for the Graph
Get the Data for the Graph
Social network of an online community:
The online community represents a prototypical example of a complex evolving social network in which connections between users are established over time by online messages. An edge annotation EdgeWeight describes the number of messages sent from a user.
The online community represents a prototypical example of a complex evolving social network in which connections between users are established over time by online messages. An edge annotation EdgeWeight describes the number of messages sent from a user.
Source: https://datarepository.wolframcloud.com/resources/Online-Social-Network
Retrieve the graph:
Special note: A graph can be “disconnected” i.e. it has some nodes that have no edges to any other node in the graph.
List the summary properties of the social network graph:
List all its vertices(they are labeled simply with numbers):
What is the diameter of the graph?
Graph diameter of a disconnected graph is represented as Infinity.
What is the distance between two random nodes, say node #1 and node #800?
i.e. 13 is not connected to 196
Are there cliques in the graph?
Find all cliques with 5 vertices:
Find all cliques with 4 vertices:
What is the higest number of edges in and out of a vertex?
Which vertex has the highest number of conenctions?
What is its vertex degree?
What is its In degree - number of edges coming in to the vertex?
What is its Out degree - number of edges going out of the vertex?
Let’s look at the part of the graph around vertex 103:
Look at the part of the graph around node 196:
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.
List the edges:
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 a largest selection of books frequently bought together that includes The Clinton Wars:
Find a 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