Introduction

Question 1

Graphs

Types of graphs based on types of connection?

Answer 1

Simple graphs: only single connections are allowed, no self loops.

• does not permit multiple edges between the same pair of nodes

Multi graph: multiple connections between the same pair of nodes are allowed, no self loops.

• can have more than one edge connecting the same nodes

Pseudo graph: multiple connections and self loops are also allowed.

• nodes can be connected to themselves.

Question 2

Graphs

What is a(n un)directed graph? What is a mixed graph?

Answer 2

In (un)directed graphs the links are (un)directed. Mixed graphs contain both directed and undirected links.

In directed graphs, each edge has a direction indicating a one-way relationship. In undirected graphs, edges indicate a two-way relationship between nodes.

Question 3

Graphs

Define a(n un)weighted graph.

Answer 3

Links have weight/are ‘binary’.

In weighted graphs, edges have values representing the cost or capacity of the connection. Unweighted graphs treat all edges equally without specific values.

Question 4

Graphs

What characterizes a bipartite graph?

Answer 4

Two types of nodes, links are allowed only between opposite types.

• e.g.: actor–movie
• same principle: tripartite graphs (e.g.: recipe–ingredient–compound)

Bi-partite graphs are often used to model relationships between two distinct sets.

Question 5

Graphs

What is an adjacency matrix?

Answer 5

Each row and column corresponds to a node: A(ij) = 1 if i —» j, A(ij) = 0 otherwise.

• rows/columns: outgoing/incoming links
• if the graph is undirected, A(ij) is symmetric
• for weighted graphs, A(ij) can take real values
• multiplying position vector from the left/right: proceeding forward/backward on the links
• such a matrix contains mostly zeros though

When the matrix is sparse, we can use a link list instead (for storing the network at least).

Question 6

Graphs

How is sparseness defined? The average number of connections?

Answer 6

A network (graph) in the N → ∞ limit is sparse if L ∼ N and dense if L ∼ N².

Average # of connections:

• sparse case: ⟨k⟩ = 2L/N → const.
• dense case: ⟨k⟩ = 2L/N ∼ N → ∞

N denotes the number of nodes, L the number of links.

2L because each link has two ends.

Question 7

Graphs

How can we decide whether a real network is sparse or not?

Answer 7

We have to compare the degree and the # of nodes: if ⟨k⟩ &laquo_space;N by several orders of magnitude smaller, then the network is considered sparse.

• most real networks are sparse (universal property of real networks!)

The degree is the # of neighbours for a given node.

Question 8

Graphs

What are the consequences of sparseness?

Answer 8

1. We use a link list instead of the adjacency matrix
2. ⟨k⟩ &laquo_space;N
3. For a randomly chosen pair of nodes, the probability of being linked is negligible (i.e., the probability converges to 0 if N → ∞).