week 8

Question 1

distance

Answer 1

length of shortest path

Question 2

eccentricity

Answer 2

maximum distance to any other vertex

Question 3

radius

Answer 3

minimum eccentricity of any vertex

Question 4

diameter

Answer 4

maximum eccentricity of any vertex

Question 5

effective diameter

Answer 5

smallest number greater than the maximum eccentricity of any vertex of a large fraction of the graph

Question 6

small world property of a graph

Answer 6

average path length scales logarithmically

Question 7

scale free property of a graph

Answer 7

the degree distribution of the graph follows a power law
zooming in on any part of the degree distribution yields the same power law

Question 8

centrality

Answer 8

degree centrality
eccentricity centrality = least eccentric vertex is the most central one, minimize maximum distance
closeness centrality = minimize average distance

Question 9

betweenness centrality

Answer 9

number of shortest paths that travel through x
edges with high betweenness are called weak ties
how to compute:
0.BFS
1.each label gets assigned how many parents it has
2.each leaf gets a credit of 1
3.each non-leaf gets credit of 1 + credit of each child / nr of parents computed in 1st step
4.repeat this for each node (each node gets to be parent)
5.divide final credits by 2
6.highest credits = weak links

Question 10

spectral clustering

Answer 10

laplacian matrix = degree matrix - adjacency matrix
compute eigenvectors/values of laplacian matrix, split into clusters based on highest eigenvalue
if more than 1 cluster => recursive (above) / cluster multiple eigenvectors