Exam, complex brain networks

Question 1

If G=(V,E) is a connected graph, what do we know about E?

Answer 1

|E|>|V|-1

Question 2

When is a directed graph G=(V,E) acyclic?

Answer 2

When there are no cycles in G

Question 3

If G=(V,E) is represented by an adjacency list, what do that say about G, V and E?

Answer 3

After a first search of G the time is proportional to |V|+|E|

Question 4

What would you use to evaluate the prestige of a vertex with respect to prestige of other vertices in a graph?

Answer 4

Eigenvecor centrality

Question 5

What would you use to evaluate the influence of a vertex in the flow of information in a graph?

Answer 5

Betweenness centrality

Question 6

If G=(V,E) is a directed and acyclic graph. What is the eigenvector?

Answer 6

The eigenvector centrality is 0 for all vertices

Question 7

Similarities between neural networks and real networks?

Answer 7

1. You cannot observe a binomial distribution for vertex degrees in neural networks
2. Neural networks are better modelled as scale-free graphs

Question 8

Let G=(V,E) be a scale-free network under a target attack starting with nodes with highest degree. How many nodes should we remove to destroy its giant component?

Answer 8

• Scale-free networks are being quite vulnerable to targeted attacks.
  —> only to remove a small fraction of its the nodes to destroy its giant component

Question 9

what is a giant component?

Answer 9

In network theory, a giant component is a connected component of a given random graph that contains a constant fraction of the entire graph’s vertices.

Question 10

What is a small-world network?

Answer 10

A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a small number of hops or steps.

Question 11

Let G=(V,E) be a graph. What is the degree of a vertex v?

Answer 11

It is the number of edges connected to v.

Question 12

A graph G=(V,E) is connected if?

Answer 12

There is a path between every pair of vertices.

Question 13

If G=(V,E) is represented by an adjacency matrix, what do that say about G, V and E?

Answer 13

After a first search of G the time is proportional to |V|^2 independently of |E|

Question 14

what is the adjacency matrix?

Answer 14

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

Question 15

what is the adjacency list?

Answer 15

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.

Question 16

what does adjacent mean?

Answer 16

close to, adjoining, common vertex and so on

Question 17

What would you use to determine the popularity of a vertex in a graph?

Answer 17

Degree centrality.

Question 18

What would you use to determine how close a vertex is to all other vertices in a graph?

Answer 18

Closeness centrality.

Question 19

What can we say about the diameter of graph G=(V,E)?

Answer 19

It may be infinite

Question 20

Let G=(V,E) be a scale-free network under RANDOM FAILURES. How many nodes should we remove to destroy its giant component?

Answer 20

• Large scale-free networks are very robust with regard to random failures.
  —> We must remove almost all of its nodes to destroy its giant component

Question 21

what is a scale-free network?

Answer 21

A scale-free network is a network whose degree distribution follows a power law