Chapter 4
Characteristics of Special Networks
Acyclic Directed Networks
0
6
1
2
3
4
5
Uses directed links
Not undirected
No Cycles
0
1
2
Acyclic Directed Networks
0
6
1
2
3
4
5
Uses directed links
Not undirected
No Cycles
0
1
2
Is this graph acyclic??
Cycles in networks
In some networks, cycles will not make sense!
Descendent of relationship
Teacher student network
Rick
Shiv
Rahat
Griffin
Khan
Esteban
Dahal
Jack
John
advised
advised
advised
Khaled
Mike
advised
advised
advised
advises
advises
advises
advises
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Cannot find any node here! Graph has cycles
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Another graph. Restart the process
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Another graph. Restart the process
Select 6
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Another graph. Restart the process
Select 6
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Another graph. Restart the process
Select 6
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Another graph. Restart the process
Select 6
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Another graph. Restart the process
Select 6
Select 1
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Another graph. Restart the process
Select 6
Select 1
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Another graph. Restart the process
Select 6
Select 1
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
0
6
1
2
3
4
5
Another graph. Restart the process
Select 6
Select 1
No node can be selected that has no outgoing links and the graph is not empty
There is a cycle here!
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Determine if a graph has cycles
Otherwise, remove the selected node and all of is incoming links
Another graph. Restart the process
0
6
1
2
3
4
5
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Acyclic!!!!
Finally Node 5
Determine if a graph has cycles
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Finally Node 5
0
6
1
2
3
4
5
Lets Redraw! Take the nodes that we selected first
Determine if a graph has cycles
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Finally Node 5
0
6
1
2
3
4
5
Let’s Redraw! Take the nodes that we selected first
6
Always take the outgoing edges
Determine if a graph has cycles
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Finally Node 5
0
6
1
2
3
4
5
Let’s Redraw! Take the nodes that we selected first
6
1
Always take the outgoing edges
Determine if a graph has cycles
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Finally Node 5
0
6
1
2
3
4
5
Let’s Redraw! Take the nodes that we selected first
6
1
0
Always take the outgoing edges
Determine if a graph has cycles
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Finally Node 5
0
6
1
2
3
4
5
Let’s Redraw! Take the nodes that we selected first
6
1
0
Always take the outgoing edges
3
Determine if a graph has cycles
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Finally Node 5
0
6
1
2
3
4
5
Let’s Redraw! Take the nodes that we selected first
6
1
0
Always take the outgoing edges
3
4
Determine if a graph has cycles
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Finally Node 5
0
6
1
2
3
4
5
Let’s Redraw! Take the nodes that we selected first
6
1
0
Always take the outgoing edges
3
4
5
2
Determine if a graph has cycles
Select node 6
Select Node 1
Select Node 0
Select Node 3
Select Node 4
Select node 2
Finally Node 5
0
6
1
2
3
4
5
Let’s Redraw! Take the nodes that we selected first
6
1
0
Always take the outgoing edges
3
4
5
2
All edges point downwards sort of
Nicer visualization
Bipartite and hypergraphs
jack
Janice
Rahat
Alice
John
neighbors
Best
friends
Project
mates
teaches
teaches
teaches
teaches
Different type of links
Bipartite and hypergraphs
Different type of nodes
Also called bipartite graph
Or two mode network, affiliation network
Two type of nodes are present
No edges between between nodes of same type
Only across
Disjoint sets
People
Sports
Jon
Alice
Kate
Football
Hockey
Basketball
Bipartite and hypergraphs
Hypergraph represents the graph as
nodes being part of groups
Easy to convert a two-mode network to a one mode network
People
Sports
Jon
Alice
Kate
Football
Hockey
Basketball
Bipartite and hypergraphs
People
Sports
Jon
Alice
Kate
Football
Hockey
Basketball
Keep only one set of nodes
Jon
Alice
Kate
Only people
Create subsets based on the common nodes
Hockey liked by jon and alice
Basketball liked by jon and kate
Football is liked by jon only
This is a hypergraph network
Tree
Special kind of graphs with no loops
Example
Tree
Special kind of graphs with no loops
Example
Tree
0
1
2
3
4
5
6
Root is a single node at the top 🡪 node 0
Nodes with no children 🡪 leaves
Trees never have any cycles!
Minimum Spanning Tree (MST)
A
B
C
D
E
You have an undirected graph, possibly even have cycles
Suppose the edges have weights
1
7
5
9
2
4
3
MST is a subgraph that includes all the nodes in that graph
And sum of those edges is the lowest
And it’s a tree, so no cycles
A
B
C
D
E
1
5
2
3
1+3+5+2 = 11