Social Network Structure: Graphs

Summary

This script delves into the fundamentals of graph theory, emphasizing the importance of defining nodes and edges in a network. It discusses the significance of connectivity, paths, and the breadth-first search method for determining shortest paths and graph diameter. The script also highlights the role of pivotal and gatekeeper nodes, and introduces concepts like local gatekeepers and network components. It underscores the variability in network analysis based on the researcher's definition of an edge, using examples like the 'six degrees of separation' and the 'small world' phenomenon to illustrate the impact of edge definition on network structure and behavior.

Takeaways

• 📚 Definition of a Graph: A graph in Chapter Two represents a network, with nodes as objects/agents and edges as connections, defined by the creator of the graph.
• 🔗 Connectivity and Paths: The concept of connectivity within a graph is based on the existence of paths between nodes, which are sequences of connected nodes.
• 🌐 Connected Graphs: A graph is considered connected if every node is linked to every other node, forming a cohesive network.
• 🔎 Breadth-First Search: This algorithm is used to find the shortest path from a selected node to all other nodes in the graph.
• 📏 Graph Measurements: Key measurements include the diameter (longest distance between any pair of nodes) and the average distance across the graph.
• 🔑 Pivotal Nodes: These are nodes that lie on a path between two other nodes and can affect the distance between them, with gatekeepers being the most pivotal.
• 🚫 Local Gatekeepers: These are nodes that connect to neighbors who do not connect directly with each other, but may not necessarily be pivotal.
• 🌟 Components and Giant Components: Graphs can be broken down into components, with a focus on significant subsets of nodes for analysis.
• 🔍 Defining Edges: The definition of an edge is crucial as it determines how the graph appears and functions, affecting concepts like the 'small world' idea.
• 🌐 Small World Phenomenon: The concept of six degrees of separation is heavily dependent on how edges are defined within a network.
• 🔮 Predictive Modeling: Graphs can be used to predict future connections or 'flows' between nodes, such as in social networks, communication, or web page navigation.

Q & A

What is the primary concept introduced in Chapter Two of the transcript?

The primary concept introduced in Chapter Two is the definition of a graph, which represents a network with nodes and edges, and the importance of understanding the context and definition provided by the author of the graph.

What is the significance of nodes in a graph?

Nodes in a graph represent objects or agents that have the ability to act within the network, and they are crucial for understanding the connectivity and interactions within the graph.

What are edges in the context of a graph?

Edges in a graph represent the connections between nodes, and their definition can vary widely depending on the researcher's perspective and the context of the network being modeled.

What is the concept of a path in a graph?

A path in a graph is the sequence of nodes that are connected through edges, and it is fundamental to understanding connectivity and the shortest route between two nodes.

What does a connected graph imply?

A connected graph implies that every node is linked to every other node within the graph, indicating a complete network where all components are accessible from any starting point.

What is the purpose of a breadth-first search in graph theory?

The purpose of a breadth-first search is to determine the shortest path from a chosen node to every other node in the graph, which helps in understanding the overall connectivity and structure of the network.

What is the diameter of a graph?

The diameter of a graph is the longest shortest path between any pair of nodes, which provides a measure of how 'spread out' the graph is in terms of connectivity.

What is the significance of pivotal nodes in a graph?

Pivotal nodes are crucial in a path between two nodes, and their removal can increase the distance between those nodes or even disconnect them, highlighting their importance in maintaining network connectivity.

What is a gatekeeper node and how is it different from a pivotal node?

A gatekeeper node is an extreme type of pivotal node. If removed, it completely disconnects two nodes, making it impossible to find a path between them, whereas a pivotal node's removal might only increase the distance but not necessarily disconnect the nodes.

What is the concept of a local gatekeeper in a graph?

A local gatekeeper is a node that connects to its neighbors but does not necessarily make them pivotal. Removing a local gatekeeper might not change the distance to other nodes, indicating a less critical role in network connectivity.

How does the definition of an edge impact the properties of a graph?

The definition of an edge significantly impacts the graph's properties, including its connectivity, diameter, and average distance, as it determines how nodes are connected and what constitutes a valid connection within the network.

What is the concept of 'small world' in graph theory and how does it relate to the definition of an edge?

The 'small world' concept refers to the idea that nodes in a network are connected by a small number of intermediary nodes, often associated with the 'six degrees of separation'. The definition of an edge plays a crucial role in determining the 'small world' number, as it dictates what constitutes a connection between nodes.

Outlines

00:00

📚 Understanding Graphs and Network Concepts

The first paragraph delves into the fundamental concepts of graph theory as presented in Chapter Two, emphasizing the definition of a graph and its components—nodes and edges. It discusses how the graph represents a network, with nodes symbolizing objects or agents capable of action and edges representing the connections between them. The paragraph also touches on the variability in defining nodes and edges, which can alter the graph's interpretation. It introduces the concept of connectivity, explaining the significance of paths between nodes and the idea of a connected graph where every node is linked. The paragraph further explains breadth-first search as a method for determining the shortest path between nodes and how it can be used to calculate the diameter and average distance of a graph. It concludes with a note on the impracticality of applying breadth-first search to very large graphs due to computational constraints.

05:03

🔍 The Importance of Node Characteristics and Graph Components

The second paragraph focuses on the characteristics of nodes within a graph, highlighting the concepts of pivotal nodes and gatekeepers. Pivotal nodes are essential in paths between other nodes, and removing them can increase the distance between connected nodes. Gatekeepers are a special type of pivotal node, whose removal can sever connections entirely. The paragraph also introduces the concept of local gatekeepers, which may not be pivotal but still play a significant role in local connections. It discusses the idea of graph components and the practicality of focusing on specific subsets of nodes for analysis, rather than attempting to analyze an entire 'world graph.' The paragraph underscores the importance of defining edges in a graph, as this definition can greatly affect the analysis and interpretation of the network. It provides examples of how different edge definitions can lead to different interpretations of connectivity, such as in the case of co-authors or the 'six degrees of separation' concept.

10:05

🌐 The Impact of Edge Definitions on Network Analysis

The third paragraph explores the profound impact that edge definitions have on network analysis, using the concepts of 'small world' numbers and degrees of separation as examples. It discusses how the definition of an edge can vary widely, affecting the perceived closeness of connections within a network. The paragraph provides examples such as the 'Bacon number' in film networks, where the definition of an edge as co-cast members leads to a surprisingly small average distance between actors. It also touches on the Milgram experiment, where the edge was defined by personal acquaintance, and how this can vary culturally. The speaker emphasizes the importance of researchers defining edges based on what is useful for their analysis, likening edges to potential flows of information or interactions. The paragraph concludes by encouraging an understanding of edges as representing not just current connections, but also the likelihood of future interactions.

Keywords

💡Graph

A graph in the context of this video represents a network, consisting of nodes and edges. Nodes are objects or agents with the ability to act, while edges are the connections between these nodes. The definition of what constitutes a node or an edge is determined by the researcher or author of the graph. The graph is central to the video's theme as it serves as a model for various types of networks, such as social, informational, or economic systems.

💡Node

A node is a fundamental element of a graph, representing an object or an agent within a network. Nodes have agency, meaning they can act and influence the network through their connections. In the video, nodes are used to illustrate the concept of connectivity and the roles different elements play within a network, such as pivotal nodes or gatekeepers.

💡Edge

Edges in the video are the connections between nodes in a graph. They represent the relationships or interactions between different elements of a network. The definition of an edge is crucial as it determines the structure and connectivity of the graph, and it can significantly impact the analysis of the network, such as in the small-world phenomenon or the six degrees of separation concept.

💡Connectivity

Connectivity refers to the extent to which nodes in a graph are linked by edges. A connected graph ensures that there is a path between every pair of nodes, which is a key concept in understanding how information or influence can spread within a network. The video discusses different types of connectivity, including connected and disconnected graphs.

💡Breadth-First Search

Breadth-first search is an algorithm mentioned in the video for determining the shortest path from a selected node to all other nodes in a graph. It is used to measure distances within the network and helps in understanding the network's structure, such as calculating the diameter or the average distance between nodes.

💡Diameter of a Graph

The diameter of a graph is the longest shortest path between any two nodes in the network. It provides insight into how 'spread out' the network is and is an important metric when analyzing the efficiency of information transfer within the network. The video uses this concept to discuss the properties of different types of graphs.

💡Pivotal Node

A pivotal node is a node that lies on a path between two other nodes. Removing this node or its connecting edge can increase the distance between the two nodes it connects. The concept is important in the video as it highlights the importance of certain nodes in maintaining the connectivity and efficiency of a network.

💡Gatekeeper

A gatekeeper is a type of pivotal node that is so crucial that removing it would break the connection between two nodes entirely. Gatekeepers are the extreme form of pivotal nodes and represent control points within a network, as illustrated in the video with examples like co-authorship graphs.

💡Local Gatekeeper

A local gatekeeper is a node that connects to its neighbors but does not necessarily play a pivotal role in the connectivity of the entire network. The concept is discussed in the video to differentiate between nodes that are pivotal on a larger scale and those that are only important within their immediate neighborhood.

💡Component

In graph theory, a component refers to a subgraph in which any two nodes are connected to each other by paths, and which is connected to no additional nodes in the supergraph. The video emphasizes the importance of focusing on components to make sense of large and complex networks, such as the world graph.

💡Small World

The 'small world' concept, as discussed in the video, refers to the phenomenon where most nodes in a network can be reached from every other node through a small number of steps or connections. This idea is closely tied to the definition of edges and is exemplified by the six degrees of separation theory.

Highlights

Definition of a graph as a representation of a network with nodes and edges defined by the creator.

Nodes in a graph represent objects with agency, capable of acting within the network.

Edges signify connections between nodes, with various ways to define these connections.

Connectivity in graphs involves the concept of paths and the sequence of nodes connected by edges.

A connected graph implies every node is linked, whereas a disconnected graph has unlinked nodes.

Breadth-first search is introduced as a method to determine the shortest path from a node to all others.

The diameter of a graph is the longest distance between any pair of nodes.

The average distance in a graph is calculated by averaging the distances between all pairs of nodes.

The impracticality of performing breadth-first search on very large graphs due to excessive computation.

Characteristics of nodes, including pivotal nodes and gatekeepers, which play crucial roles in connectivity.

Gatekeepers are pivotal nodes that, if removed, disrupt all connections between certain nodes.

Local gatekeepers are pivotal within their immediate neighborhood but do not affect overall graph connectivity.

The importance of defining components in a graph to focus on relevant subsets of nodes.

The significance of defining an edge in a graph, as it greatly influences the graph's structure and interpretation.

The concept of 'small world' and its dependency on the definition of an edge, as illustrated by the six degrees of separation.

The variability in defining edges, such as including directors or producers in a movie network, affecting the 'small world' number.

The importance of considering cultural differences when defining an edge, like the meaning of knowing someone on a first-name basis.

The idea of edges representing potential future connections or flows, such as information or transactions.

The concept of edges as a statistical probability of future interactions, emphasizing their predictive nature.

Transcripts

all right so I'm gonna talk here about

chapter twos first I'm gonna talk about

the basic vocabulary and the concepts

you need to know out of Chapter two

the first main idea in Chapter two that

you need to understand is the definition

of a graph so chapter two they go

through a whole bunch of graphs and

they're putting nodes and they're

putting edges between them and what you

need to make sure you understand is the

graph itself so whatever graph you're

seeing is a representation of this

network and the network definition is

defined by whoever created the graph so

everything you see there is something

that the author whoever chose to put

there so in this context here I mean the

context of that graph you need to think

here about the nodes in that graph being

some sort of object and usually that

object needs to have some sort of agency

meaning they have sort of a will or an

ability to act in the network and

choosing to activate these edges and the

edges being the connections between the

nodes there's lots of different ways to

define the nodes and lots of different

ways to define the connections so again

the definition here is up to the

researcher or whoever produced the graph

when you talk about connectivity from

Chapter two the idea that's most

important in this sense is this path

idea and if we're going to say you know

we're following a path between two nodes

in my graph you know this path is the

sequence of nodes that are connected the

connection or the connectivity of the

graph

has something to do with the way the

whole graph works together so if we're

going to say a connected graph meaning

the researcher drew a graph here and

every item or every node is linked that

means your graph you're showing is

nected I'll talk in a minute about a

disconnected graph and why you would

graph that so we had the different ways

of sort of measuring distances and a few

other things so the first idea was this

breadth-first search and you can see

here you know i've kind of put it in the

slide but the breadth first search is

where you pick a node in the graph and

you measure a distance from that node to

every other node it's got to be the

shortest path here so a distance is

always the shortest path I mean aren't

taken you know sort of there's no long

scenic route between two nodes

there's the shortest path and that's

what the breadth-first search needs to

find for us once we've done a breadth

breadth-first search for every node

every pair of nodes in our graph we then

can figure out or you and then we can

determine what the diameter of the graph

is so the diameter of the graph is gonna

be the longest distance between any pair

of nodes in the graph and then the

average distance would be if we averaged

every distance between every pair of

nodes in a graph that would be the

average distance hopefully you're

already thinking right now if we see

these really large graphs with thousands

and thousands of nodes you actually

would not ever do even a breadth-first

search and determine any you know every

distance in the graph it's just too much

computation we'll talk about that issue

in a little bit or yeah so usually

wouldn't do it all right speaking of

nodes so nodes do have characteristics

and that was actually the main focus in

this chapter so we had some terms here

the ones you need to be clear on and I

think these are clear and the exercises

the main point here is a pivotal node

that is you have a pivotal node if we

have a path between two pairs of nodes a

pivotal node falls on that path and if

you take that pivotal node out or remove

an edge to the pivotal node that would

increase the distance between those two

it's a gatekeeper is basically a type of

pivotal node that is so pivotal that if

you take it out you have no possible way

of connecting those two nodes again so a

gatekeeper is basically the extreme type

of pivotal node and that you know again

would make it so you can't connect to

nodes or there's some nodes that

wouldn't be connected and in that case

going back a couple here we're talking

about a graph if that's no longer

connected if you and again it's not

necessarily removing the gatekeeper it's

removing one of the edges between a

gatekeeper and other nodes a local

gatekeeper is sort of the junior version

of a pivotal node a local gatekeeper

does connect to its neighbors its

neighbors don't connect directly with

each other but in the case of a local

gatekeeper it's possible that they're

not a pivotal node that is if you take

out an edge to a local gatekeeper you

can still reach the other node and the

distance could be the same length okay

so it's possible to be a local

gatekeeper and not a pivotal node now so

that's basically what you know that's in

the chapter and that stuff that exercise

is kind of emphasized I want to go

through a couple of things now that

needs are two different emphasizing that

I think in the book this book is by

economists and we're here to kind of as

technologists and social scientists

trying to get graphs to work for us so

when here we talk about components and

giant components again you're the one as

the researcher that's defining what's

relevant it's really pointless to think

about a network graph of everything or

everyone in the world because you would

never be able to analyze that graph so

focusing on a component is very normal

so you're gonna break the graph up

you're going

do a subset of nodes and focus on that

set of nodes so it's possible also once

we're focusing on a set of nodes that we

can actually say we have various

components in what would be considered a

quote world graph maybe and in that case

it's possible to graph the components

separately meaning we zoom up a level

okay we aren't necessarily going to do

that much I mean at this point it's

we've got a lot going on but that's kind

of one of the options here to reduce the

complexity of what's going on the next

thing that's super super important is

how they define an edge defining an edge

is a huge deal and I mean what your

graph is going to look like everything

about it certainly how you define a node

is something but it's really enough to

start saying node is a object slash

agent and at that point you know people

is easy enough to make a node so here we

had a graph this was a graph of the what

was this this was co-authors so people

that appeared on the same paper together

and you look at the graph over here and

you can see there's actually a sort of

large central component in the middle

and then there's these three other sort

of isolated nodes together now I want to

emphasize here the reason this is all

drawn together is because whoever the

researchers is think of all these nodes

as being connected in another way

already okay now I think these are

people who work at the National

Institutes of Health's and a few

different research centers what I

emphasize here is this is people that

have co-authored an article together the

sub underlying graph the implied

connections might include people that

ate lunch together people that had

coffee together people that met each

other in the parking lot I mean there's

a whole lot of ways that our nodes might

be connected behind the scenes

which is actually why we're seeing this

graph here with these two or really

three different components

with two that are really tiny and one

that's really big so defining an edge is

a huge yield so switching over to their

small world idea in the book and boy

they sure love that one the idea of the

six degrees of separation entirely

depends on your definition of an edge so

if you think about the bacon number

that's actually a pretty low number and

if you remember that from the book I

think it was something like most of them

are less than five the bacon number edge

definition is castmembers so that means

this is someone who appeared in a movie

and maybe appears in the credits they

spoke something or in some way acted and

got included in the credits so just

based on that all the people of all

these movies are very you know closely

connected they have a very short

distance to each other the Milgram

experiment was a similar thing well not

similar I mean they defined their edge

they defined it in a different way

the idea there was someone you know on a

first-name basis so what I want you to

think about right now is if we're gonna

think about the network of movies you

would change the bacon number if you

just simply added the directors of

movies for example so if it included

cast member and director it would might

be a different number if you included

cast members and producers and not

directors so there's a lot of

variability in here on how you might

come up with your quote small world

number meaning your average distance

similarly the Milgram experiment this

idea of someone you know on a first-name

basis and I know this as an American

what that means knowing someone on a

first name basis I actually know people

that would you know consider themselves

very prominently that I can address on a

first name basis but I know in other

countries this is someone I would never

address by their first name you know for

example I know one of the city council

members of our city here and I address

her by her first name which is you know

that's just what I do

and so we think about you know sort of

my connection my degrees of separation

from you know just some random not

random if I pick to say Barack Obama and

how many steps would it take me to get

to Barack Obama is probably via this

woman who I'm quote on a first-name

basis it's a very short distance where

you know if I wasn't comfortable

addressing her on a short name basis all

of a sudden you know the distance

expands by probably 10 so defining an

edge is a very very important thing and

you as a researcher are the one who is

going to define the edge and it's based

on what's useful to you so I like to

think of this as flows some people don't

like the idea of flows but to me we're

activating an edge so usually

information is going to flow so we

talked about nodes being agents so

having something they want to do and

that means the nodes are activating the

edges sort of consciously so if we went

back to some of the examples in the book

one of them is about instant messaging

who talked to whom with that sort of

model we're going to say you know

knowing who talked to whom what we're

trying to do is say what's gonna happen

later what happens next who is going to

talk to whom and so we might be trying

to predict you know when a very and when

a video goes viral where does it go who

is going to engage those edges it's the

same with these will get to these as we

go later in the book that's you know as

you make transactions who's trading with

whom this is the idea of you know who

traded in the past with whom can be

modeled who is going to transact with

whom this also and I want you to think

about this one too if you think about

web pages so we have a web pages that

have links to other pages you can use

those to predict what links that user

will follow but we understand that just

because a link appears on the page it

doesn't mean that they're actually ever

going to be used and I think that's the

most profound example here about an edge

so an edge here a link here is a an

availability or a likelihood of a future

connection okay so our edges when we as

researchers model these edges what we're

trying to say is this is something that

might happen that might be used and we

need to be conscious of that that

there's sort of a statistical

probability that going on here

so hopefully that'll get you kind of the

interesting things going on here we'll

do the exercise and hopefully that will

illuminate things further