WOLFRAM NOTEBOOK

Social Networks

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

Graph{sa,ad},
Out[]=

Directed, unweighted graph

In[]:=
Graph{s->a,a->d},
Out[]=

Undirected, weighted graph

Graph{sa,ad},EdgeWeight{30,10},
Out[]=

Directed, weighted graph

In[]:=
Graph{s->a,a->d},EdgeWeight{20,15},
Out[]=

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

    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

    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

    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
    v
    is the number of edges incident to
    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

    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

    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.
    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.
  • 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?

    Six Degrees of Separation

    Popular ideas about six degrees of separation:

    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”?

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

    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

    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

    How do companies store and provide access to a social graph?

    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

  • 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

  • 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

  • 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

    Fake News Travels the Network

  • Social networks have been repeatedly spotlighted for their role in distributing and increasing the effectiveness of disinformation
  • 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

    Reference

  • Analyzing the Social Web by Jennifer Golbeck
  • Wolfram Cloud

    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 »

    You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.