Graph Applications Flashcards
1
Q
What are graphs?
A
- Common data structure
- Used to represent a range of different problems
- Such as finding the shortest path from one location to the other
2
Q
What is Dijkstra’s Algorithm?
A
- Used to find the shortest path
- Between a starting vertex and every other vertex
- A to A
- A to B
- Etc
- In a weighted graph
- Where all the weights are positive
3
Q
Explain how this works
A
4
Q
What is the denotation for Dijkstras Algorithm?
A
5
Q
What is the importance of graphs in sorting?
A
- Topoligical Sorting
– We can utilise graphs to compute the ordering of a list of tasks - Where some tasks depend on others
6
Q
What is topological sorting?
A
- Ordering the vertices of a directed acyclic graph
- Through the use of stacks
- Such that for every directed uv from vertex u to vertex v
- U comes before V in that ordering
7
Q
How does this work?
A
8
Q
What are tological sort use cases?
A
- Software needs to install dependencies
- Order of installation needs to be computed using topological sorting
9
Q
What is the importance of graphs through webpages?
A
Graph Uses Through HITS
- Needed to compute the rank of web pages
- Given a set of web pages and how they link to each other
10
Q
What are HITs?
A
- Hubs and Authorities algorithm
- Authorities - root web pages which are the most relevant pages
- Hubs - pages that link to authorities
- Used to rank web pages
- Given a representation of the relation between web pages
- Through a directed graph
11
Q
Give a basic outline of how HIT process works
A
- Start by Hub and Autorities being set to 0
- Vertex Authority score = the sum of hub scores of all vertices linked to it
- Vertex Hub score = the sum of authority score of all vertices linked to it
- K = the iteration/loop we are in
- This considers two iterations only
12
Q
How does Authority Calculation work in HIT
A
13
Q
How does Hub Calculation work in HIT
A
14
Q
```
~~~
How does Hub Normalisation work?
A
15
Q
How does Authority Normalsation work in HIT
A
