G&N Units 5,6

Does this graph have an Eulerian path?

• Yes, because there are two nodes with odd degree

• Yes, because any connected graph has an Eulerian path

• No, because all the nodes shoud have a degree of 3 or more

• We can not know without calculating the eigenvector centrality

What is the meaning of the power n of an adjacency matrix?

• it gives the densities of the subgraphs with diameter n

• it gives the eigenvector centralities of the edges

• it gives the number of different paths of length n between two nodes

• it gives the number of incident paths of nodes of degree n

Shortest path to node 5, starting at node 0, using the Dijstra Algorithm?

• 0-1-2-5

• 0-3-4-1-2-5

• 0-1-4-5

• 0-3-4-5

What is the probability that a random walker reaches the node 8 at time t?

What is the difference between the Dijkstra and the A* algorithms?

• Dijkstra is a shortest path algorithm, whereas A* is a graph traversal algorithm.

• Dijkstra is a DFS based algorithm, and A* is a BFS based algorithm.

• Both compute shortest paths, but Dijkstra considers the minimum cost up to the current node, whereas A* adds an heuristic to estimate a lower bound o the future cost.

• There are no differences, it is the same algorithm that has different names in Europe and America.

In tf-idf what is the meaning of idf (inverse document frequency)?

• It counts the frequency of the terms in each document.

• It down-weights the terms that occur frequently, and increases the weight of ones that occur rarely.

• It increases the weight of terms that occur frequently, and down-weights ones that occur rarely.

• It merges the terms with the same root, conidering them as synonims in the dictionary.

Given two BoW vectors, which distance/similarity is most convenient?

• Cosine

• Euclidean

• Substraction

• Levenshtein

What of the following sentences is NOT TRUE with regard to the Page Rank algorithm?

• An internet page is ranked in terms of its degree centrality

• The relevance of a page is proportional to the probability of being visited by a random walker through the www

• An internet page is ranked in terms of its eigenvector centrality

• The relevance of a page depends on the relevance of its predecessors

This graph represents a passing network of a basketball team. Which player is more influential in the team game?

• Player 3 because he/she has the highest Page Rank

• Players 2 and 6 because they are the ones who throw the most to the basket

• Player 1 because he/she has the maximum weighted inbound degree

• Player 3 because he/she has the maximum weighted outbound degree

Which node in this graph has the second highest Page Rank value?

• 2

• 3

• 4

• 5