Social Network Structure: Graphs
Summary
TLDRThis 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
📚 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.
🔍 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.
🌐 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.
Mindmap
Keywords
💡Graph
💡Node
💡Edge
💡Connectivity
💡Breadth-First Search
💡Diameter of a Graph
💡Pivotal Node
💡Gatekeeper
💡Local Gatekeeper
💡Component
💡Small World
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
Ver Más Videos Relacionados
Datasets: Analysing Using Networkx
ISIS Protocol-Session 1 - Dynamic Routing Overview (#Arabic -Version )
What Is Network Security? | Introduction To Network Security | Network Security Tutorial|Simplilearn
Introduction to Computer Networks
Projeto e Análise de Algoritmos - Aula 14 - Classes de problemas: Problemas P, NP e NP-completos
Bagaimana Cara Kerja Internet ?
5.0 / 5 (0 votes)