Connectivity in Graphs

• Adjacent nodes/Edges,
Walk/Path/Trail/Tour/Cycle
Adjacent nodes and Incident Edges

Two nodes are adjacent if they are connected via an

edge
v1 v2

Two edges are incident, if they share on end-point

When a graph is directed, edge directions must match

for edges that are incident

An edge in a graph can be traversed when one starts

at one ofits end-nodes, moves along the edge, and
stops at its other end-node
Walk

Walk: A walk is a sequence of incident edges

visited one after another
- Open walk: A walk does not end where it starts
- Close walk: A walk returns to where it starts
• Representing a walk:
- A sequence of edges: e1, e2, …, en
- A sequence of nodes: v1, v2, …, vn
• Length of walk: the number of visited edges

Length of walk= 8
Path

• A walk where nodes and edges are distinct is

called a path and a closed path is called a cycle
• The length of a path or cycle is the number of
edges visited in the path or cycle

Length of path= 4
Random Walk

• A walk that in each step the next node is selected

randomly among the neighbors
– The weight of an edge can be used to define the probability of
visiting it
– For all edges that start at vi the following equation holds

𝑊𝑖𝑥 is the probability of visiting node x,

the summation of the probability visiting all the neighbors is 1

• Random walk is a good measure of nodes

similarity and node importance
Random Walk in Social Networks
v2 v2 1
2
v1 v1
v3 v3
3
1
5

v6 v4 v6 v4
1 2
v5 v5

Unweighted Graph Weighted Graph

Random walk is a good measure of nodes similarity

and node importance
• Intuitively, node v1 is more similar to v2 than v3 ifv1 is more
reachable to (has higher chance to visit) v3
• A node is more important if random walks are more likely to
visit that node
Random Walk and PageRank

PageRank is a system for ranking webpages

developed by Google founders Larry Page and
Sergey Brin at Stanford University. It's used to
give each page a relative score of importance
and authority

How to give importance score:

Basic idea: the more likely a webpage

is visited by a user, the more important
the webpage is
1. Treat WWW as a directed graph
Nodes: web pages, Edges: Hyperlinks
2. Perform techniques similar to
random walk to assign importance scores
Connectivity

• A node vi is connected to node vj (or reachable

from vj) if it is adjacent to it or there exists a path
from vi to vj.

• A graph is connected, if there exists a path

between any pair of nodes in it
– In a directed graph, a graph is strongly connected
if there exists a directed path between any pair of
nodes
– In a directed graph, a graph is weakly connected if
there exists a path between any pair of nodes, without
following the edge directions
• A graph is disconnected, if it is not connected.
Connectivity: Example

Connected Disconnected Strongly connected Weakly connected

Reason:
• With direction,
no path from v5 to v2.
• Without direction,
all nodes are connected
Components

• A component in an undirected graph is a

connected subgraph, i.e., there is a path
between every pair of nodes inside the
component

3 components
Components

• In directed graphs, we have a strongly connected

components when there is a path from u to v and
one from v to u for every pair (u,v).

• The component is weakly connected if replacing

directed edges with undirected edges results in a
connected component

3 Strongly- connected
components
Shortest Path

• Shortest Path is the path between two nodes that has the shortest
length.
– We denote the length of the shortest path between nodes vi and

• The concept of the neighborhood of a node can be generalized using

shortest paths. An n-hop neighborhood of a node is the set of nodes that
are within n hops distance from the node.
For v1:
1-hop neighborhood: v2
2-hop neighborhood: v2,v3,v4
Shortest Path: More Examples

v 1 and v3:

v1 and v5 :
Diameter
What is the diameter of Facebook?

Estimated average degrees of separation between all people on Facebook

in 2015 Much more links created than new users joined
Special Graphs
Trees and Forests

• Trees are special cases of undirected graphs

• A tree is a graph structure that has no cycle in it

• In a tree, there is exactly one path between any pair

of nodes
– two paths between two nodes will result in a cycle

• In a tree: |V| = |E| + 1

– Number of nodes = Number of edge +1
– How to prove?

• A set of disconnected
trees is called a forest
A forest containing 3 trees
Special Subgraphs
Spanning Trees
• For any connected graph, the spanning tree is a tree that
includes all the nodes of the graph
– There may exist multiple spanning trees for a graph.

• For a weighted graph and one ofits spanning tree, the weight of
that spanning tree is the summation of the edge weights in the
tree.

• Among the many spanning trees found for a weighted graph, the
one with the minimum weight
is called the
minimum spanning tree (MST)
Application of MST：Network design

• Road Network Design

– Nodes represent cities
– Each edge is a possible road to be built between two cities
– Weight of an edge denotes the cost of building the road
– Goal: build some roads so that there’s a path between two
cities, meanwhile minimize the cost

• Similar applications include telephone, electrical,

hydraulic, TV cable, computer network design

Social etdwi rMki in ng Measures

Graphand Metrics
Essentials 29
Complete Graphs

• A complete graph is a graph where for a set of

nodes V, all possible edges exist in the graph
• In a complete graph, any pair of nodes are
connected via an edge, total number of edges are

|v|=1 |v|=2 |v|=3 |v|=4 |v|=5 |v|=6 |v|=7 |v|=8

Social etdwi rMki in ng Measures

Graphand Metrics
Essentials 30
Bipartite Graphs

• A bipartite graph G(V; E) is a graph where the

node set can be partitioned into two sets such
that,
– For all edges, one end-point is in one set and the other
end-point is in the other set.
– No edges within each set of nodes
Examples of Bipartite Networks

Student Classes
Regular Graphs

• A regular graph is one in which all nodes have

the same degree
• Regular graphs can be connected or
disconnected
• In a k-regular graph, all nodes have degree k
• Complete graphs are examples of regular graphs
Bridges (cut-edges)

• Bridges are edges whose removal will increase the

number of connected components

• Detecting bridges is important because it helps to

find communities

Social etdwi rMki in ng Measures

Graphand Metrics
Essentials 34
 Graph Algorithms

Social etdwi rMki in ng Measures

Graphand Metrics
Essentials 1
 Graph/Network Traversal
Algorithms

Social etdwi rMki in ng Measures

Graphand Metrics
Essentials 2
Motivation Example

• Consider a social media site say Twitter that has millions of

users and we are interested in computing the average age
of its users
– Basic idea: access each user and get each user’s age

• Available operation: given a user ID, the site can return the
user profile (including age) and the friend list of the user
• How can we do this if we have no idea of how many users are in the
social media site and we don’t have complete user ID list? We also want
to access each user exactly once
Graph/Tree Traversal

• Assumption: social media users are strongly connected

• The usual technique is to start from one user and

employ some traversal technique to browse his
friends and then these friends’ friends and so on. The
traversal technique guarantees that
– 1. All users are visited; and
– 2. No user is visited more than once

• There are two main techniques:

– Depth- First Search ( DFS)
– Breadth- First Search ( BFS)
Intro. to Stack and Queue

• Two important data structures (will not appear

in exam, just for understanding BFS and DFS)

• [Link]
YoI
Depth-First Search (DFS)

• Depth-First Search (DFS) starts from a node vi,

selects one of its neighbors vj form N(vi) and
performs Depth-First Search on vj before
visiting other neighbors in N(vi)

N(vi) is the set of neighbors

of node vi
Depth-First Search (DFS)

• Depth-First Search (DFS) starts from a node vi,

selects one of its neighbors vj form N(vi) and
performs Depth-First Search on vj before
visiting other neighbors in N(vi)

• The algorithm can be used both for trees and

graphs
– The algorithm can be implemented using a stack
structure
Depth-First Search (DFS): An Example

Initially v2
v1 v3

Gray: visited
Dashed: unvisited

v4
v5
v5
v3
v3

v6
v3
v7
Breadth-First Search (BFS)

• BFS starts from a node, visits all its immediate

neighbors first, and then moves to the second
level by traversing their neighbors.
Breadth-First Search (BFS)

• BFS starts from a node, visits all its immediate

neighbors first, and then moves to the second
level by traversing their neighbors.

• The algorithm can be used both for trees and

graphs
– The algorithm can be implemented using a queue
structure
Breadth-First Search (BFS)

Initially
Back Front
v1 v3 v2

Gray: visited
Dashed: unvisited
Solid: in stack

v7 v6 v5 v4
v5 v4 v3
Crawling Social Networks with BFS or DFS

• Use BFS or DFS to traverse a social network, say

Twitter

• When we visit a node, save its neighbors using

edge list or adjacency list

• The network can be reconstructed from edge list

or adjacency list
Crawling Social Networks with BFS: Example

Assume we randomly picked v1 as the starting node

1. Visit v1, get v1’s friend list v1 v2, v3, v4, v5, put unvisited neighbors in the
queue, mark v1 as visited
2. Visit v2, get v2’s friend list v2 v1, v3, v12, v14, put unvisited neighbors in the
queue, mark v2 as visited
3. Visit v3, get v3’s friend list v3 v1,v2,v5,v9,v8, put unvisited neighbors in the
queue, mark v3 as visited

4. ..
Comparison of BFS and DFS

Depth-First Search (DFS) starts from a BFS starts from a node, visits all its
node vi, selects one of its neighbors vj form immediate neighbors first, and then move
N(vi) and performs Depth-First Search on to the second level by traversing their
vj before visiting other neighbors in N(vi) neighbors
• Which one is better for crawling social network? Why?
– Hint: social networks are usually very large, we can only crawl a portion of it
with certain budget. Social media websites has constraints on crawling. We need
to crawl a representative subnetwork with certain budget.
– BFS is usually a better choice
 Dijkstra’s Algorithm

• For finding shortest paths

in a graph

Social etdwi rMki in ng Measures

Graphand Metrics
Essentials 15
Shortest Path

When a graph is connected, there is a chance that

multiple paths exist between any pair of nodes
- In many scenarios, we want the shortest path between
two nodes in a graph
• Dijkstra’s Algorithm
- It is designed for weighted graphs with non-negative
edges (Q: why Dijkstra’s algorithm doesn’t work for non-
negative edges?)
- It finds shortest paths that start from a provided
node s to all other nodes
- It finds both shortest paths and their respective lengths
Dijkstra’s Algorithm: Finding the shortest path

1. INITIALIZE distances dictionary:

- Set distance[StartNode] = 0
- Set distance[All Other Nodes] = Infinity
2. CREATE a Set 'unvisited' containing all nodes in the graph
3. WHILE 'unvisited' is not empty:
a. CurrentNode = The node in 'unvisited' with the SMALLEST distance
(Note: If smallest distance is Infinity, stop; target is unreachable)
b. IF CurrentNode == EndNode:
BREAK (We have found the shortest path to the target)
c. FOR each Neighbor of CurrentNode:
Calculate NewDist = distance[CurrentNode] + Weight(Current, Neighbor)
IF NewDist < distance[Neighbor]:
distance[Neighbor] = NewDist # Update with the shorter path
d. REMOVE CurrentNode from 'unvisited'
(Mark as visited; we will never check it again)
Dijkstra’s Algorithm Execution Example

Find smallest distance in unvisited

Current Node: 0 D:4
• Dist[2] -> 2
• Dist[1] -> 4

Remove Node 0
D:2

Find smallest distance in unvisited

Current Node: 2
• Dist[3] -> 3
• Dist[1] -> 4
D:3

Remove Node 2
D:10
Dijkstra’s Algorithm Execution Example

Find smallest distance in unvisited D:6

Current Node: 3
• Dist[1] maintains
• Dist[4] -> 6

Remove Node 3 in unvisted

Find smallest distance in unvisited

Current Node: 1
• Dist[3] maintains
• Dist[1] maintains

Remove Node 1
Dijkstra’s Algorithm Execution Example

Find smallest distance in unvisited D:6

Current Node: 3
• Dist[1] maintains
• Dist[4] -> 6

Remove Node 3 in unvisted

Find smallest distance in unvisited

Current Node: 1
• Dist[3] maintains
• Dist[1] maintains

Remove Node 1
Dijkstra’s Algorithm Execution Example

Find smallest distance in unvisited

Current Node: 4
• Dist[5] -> 9

Remove Node 4 in unvisted

D:9

Find smallest distance in unvisited

Current Node: 5
Remove Node 5
Dijkstra’s Algorithm

• Dijkstra’s algorithm is source-dependent and

finds the shortest paths between the
source node and all other nodes. To
generate all-pair shortest paths, one can run
Dijsktra’s algorithm n times

• If we want to compute the shortest path from

source v to destination d, we can stop the
algorithm once the shortest path to the
destination node has been determined
Some Applications of Shortest Path

• Finding the shortest path/cheapest path in a road

network

• Finding the diameter of a network

– Diameter of a graph is the length of the longest shortest
path between any pairs of nodes in the graph

• Calculating closeness centrality

– A user is more influential if its shortest paths to other
nodes are small
– To be covered in network measure
Prim’s Algorithm

• For finding MST in a graph

Prim’s Algorithm: Finding Minimum Spanning
Tree

• It finds minimal spanning trees in a weighted graph

– It starts by selecting a random node and adding it to the
spanning tree
– It then grows the spanning tree by selecting edges which
have one endpoint in the existing spanning tree and one
endpoint among the nodes that are not selected yet. Among
the possible edges, the one with the minimum weight
is added to the set (along with its end-point)
– This process is iterated until the graph is fully spanned
Prim’s Algorithm Execution Example
Prim’s Algorithm Execution Example 2
Bridge Detection

• Definition of Bridge: removal makes formerly

connected components disconnected

• How to detect bridge?

– Remove edge one by one, test if the connected
components become disconnected
– Say (u,v) is removed, starting from u
• if we can use BFS or DFS to traverse to v, (u,v) is not a bridge
• Otherwise, disconnected, (u,v) is a bridge

• Why bridge detection:

– Can be used for community detection
Take-Away

• Understand how real-world networks can be

represented as graphs, matrix representation and
edge-list representation of graphs

• Understand different types of graphs and random

walk

• Understand BFS and DFS, and network crawling

• Be able to find shortest path wtih Dijkstra’s

Algorithm on simple graphs

• Be able to find minimal spanning trees with Prim’s

Algorithm on simple graphs