network
Graph Theory
Recap from the last week
Importance and definition of a network
Two levels of understanding:
(1) at the level of structure Graph theory
(2) at the level of behavior Game theory
The next three weeks’ topic
What is a social network? Relations among People
https://ocw.mit.edu/courses/sloan-school-of-management/15-599-workshop-in-it-collaborative-innovation-networks-fall-2011/lecture-notes/MIT15_599F11_lec04.pdf
What is a Network? Relations among Institutions
https://ocw.mit.edu/courses/sloan-school-of-management/15-599-workshop-in-it-collaborative-innovation-networks-fall-2011/lecture-notes/MIT15_599F11_lec04.pdf
Basic concepts of the graph theory
Graph: A graph is a way of specifying relationships among a collection of items
Node: An object, an actor, a point
Computers, telephones
Persons, employees
Companies/business units
Articles/research projects
Neighbors: If the two nodes are connected
Edge
Edge: A link that connects a pair of nodes
Ties, edges, arcs, lines, and links
Types of social relations
Friendship
Acquaintance
Kindship
Advice
Hindrance
Sex
Allow different kind of flows
Messages
Money
Diseases
An edge may contain a direction when a direction is asymmetric
Paths and Cycles
Path: a sequence of nodes with the property that each consecutive pair in the sequence is connected by an edge.
containing not just the nodes but also the sequence of edges linking these nodes
Cycle: A “ring” structured path
A path with at least three edges, in which the first and last nodes are the same, but otherwise all nodes are distinct.
Q1. Why is this redundancy necessary?
Or what is the advantage of a ring structure as opposed to a star structure?
https://www.geeksforgeeks.org/difference-between-star-and-ring-topology/
Roles of Graph
Mathematical models of network structures
Represent how things are either physically or logically linked to one another in a network structure
Connectivity
Connectivity: The state of a graph in which every pair of nodes is connected via a path
The example (Figure 2.6) is built from the collaboration graph at a biological research center.
Nodes: researchers
Edge: co-authored publication
What is the most prominent node? (Centrality)
Who knows the most actors? (degree centrality)
Who has the shortest distance to the other actors?
Who controls knowledge flows?
What happens if this most prominent central node is removed?
Figure 2.6 Collaboration graph
Connected components (or just components)
A subset of the nodes such that: (i) every node in the subset has a path to every other; and (ii) the subset is not part of some larger set with the property that every node can reach every other.
(i) components are internally connected
(ii) a component is a free-standing
Q2. How many connected components do you see in Figure 2.6 in the previous slide and in Figure 2.5 on the right in this slide?
Figure 2.5
Giant Components
A connected component that contains a significant fraction of all the nodes.
In Figure 2.6, what is a giant component?
When a network contains a giant component, it almost always contains only one. Why?
Two giant components’ coexistence in history
What happens in human history when two giant components co-existed?
Guns, Germs, and Steel by Diamond
One in Americas and the other in Europe
(0:51-4:00)
When the two giant components clashed, what happened?
Q3: When the two giant components clashed, what happened? Did the two giant components continue to co-exist? Or did one dominate the other? Based on this video, explain why it is very rare, if not impossible, to see two giant components coexist.
Giant component and its implications
Figure 2.7 shows the romantic relationships in an American high school over an 18-month period
The fact that this graph contains such a large component is significant when one thinks about the spread of sexually transmitted diseases
A high-school student may have had a single partner over this time period and nevertheless — without realizing it — be part of this large component and hence part of many paths of potential transmission.
Distance
Length of a path: The number of steps it contains from beginning to end
Distance between the two nodes: The length of the shortest path between them
Breadth-First Search
Small World Phenomena
The idea that the world looks “small” when you think of how short a path of friends it takes to get from you to almost anyone else.
Six degrees of separation
All people are six, or fewer, social connections away from each other.
Kevin Bacon number
How do we measure “Real” social networks?
Interpersonal relationships, intensity of relationships, subtle acquaintance – impossible to measure
We need to define a link in an observable way (e.g., email exchanged, business transactions made, ”friends’ lists” on FB, Instant Messages exchanged)
What are some other limitations?
Lack of participation
Dishonest answers
The size and scope of network
Therefore, we need help from digital tracing and computational method to measure the networks
A partial reason why SNA has grown very fast in the past few years
Figure 2.12: Ron Graham’s hand-drawn picture of a part of the mathematics collaboration graph, centered on Paul Erd ̈os [189].
Growth of SNA since late 1990’s
Main sources of large-scale network data
Collaboration Graphs
Who talks to Whom graphs
Information linkage graphs
Technological networks
Q4: Pick one of the examples above and describe what problems, challenges, and limitations you would encounter if you were to generate a graph. For instance, if you were to draw a collaboration graph among all MSU faculty members, what problems would you encounter?
Exercises – Recitation Session on Thursday
A pivotal node
Gate-keepers
Do the exercise questions!
Be prepared to create some of these using NetLogo