3 | network properties and types

Question 1

What do network properties do?

4 examples of network properties?

Answer 1

Network properties measure certain aspects of the network

Examples:
- order (number of nodes)
- size (number of edges)
- diamater
- chromatic number

Question 2

Does a network property depend on the particular drawing of a graph? If so/not, what is this quality known as?

Answer 2

A network property does not depend on the particular drawing of the graph

–> this is why it is also called a network invariant

Mathematically: property is preserved in an isomorphic network

Question 3

What is a graph (network) isomorphism?

Answer 3

Two graph 𝐺 and 𝐻 are isomorphic if
- there is a bijection (one-to-one mapping) 𝜑: 𝑉(𝐺) → 𝑉(𝐻)
- such that {𝑢, 𝑣} ∈ 𝐸(𝐺) if and only if {𝜑(𝑢), 𝜑(𝑣)} ∈ 𝐸(𝐻)

Question 4

What classifications of network properties are there?

Answer 4

Properties can be classified into:
- local
- global
- local-global

Question 5

What are the criteria for determining the classification of a network property?

Answer 5

Criteria for classification:
- does it pertain to:
- a subset of nodes or edges VS
- the entire network
- information needed to calculate/determine the property:
- only local information about node/edge VS
- global information about the entire network

Question 6

What is a local network property?

Answer 6

(network classification)

A local property:
- pertains to: a subset of nodes / edges
- requires information for calculation: subset only

Question 7

What is a global network property?

Answer 7

(network classification)

Global property:
- pertains to: the entire network
- required information for calculation: entire network

Question 8

What is a local-global property?

Answer 8

(network classification)

Local-global property
- pertains to: a subset of nodes / edges
- required information for calculation: entire network

Question 9

What is meant by the degree of a node in an undirected graph?

Answer 9

Given an undirected graph 𝐺:
- degree of node 𝑢 is the number of edges incident on 𝑢.
- degree is denoted by 𝑑(𝑢)

Question 10

What is meant by the degree of a node in a directed graph?

Answer 10

In a directed graph 𝐺:
- indegree of node 𝑢, d^-(u) = number of incoming edges
- outdegree of node 𝑢, d⁺(u) = number of outgoing edges.

Question 11

In a directed graph 𝐺, what is d^-(u)?

Answer 11

indegree of node 𝑢 = number of incoming edges

Question 12

In a directed graph 𝐺, what is d⁺(u) ?

Answer 12

outdegree of node 𝑢 = number of outgoing edges

Question 13

If d^-(u) = 0 then u is a _______.

Answer 13

source (no incoming edges)

Question 14

If d⁺(u) = 0 then u is a _______.

Answer 14

sink (no outgoing edges)

Question 15

A node that is neither a source nor sink is ________.

Answer 15

internal

Question 16

What is an internal node?

Answer 16

one that is neither a sink not a source.

Question 17

What is a balance graph?

Answer 17

A graph in which for every u, d⁺(u) = d^-(u).

Question 18

What classification is node degree?

Answer 18

A local property

Question 19

What is the degree sequence of a graph/network?

Answer 19

Degree sequence:

Given an undirected graph 𝐺, the degree sequence is a non-increasing sequence of node degree

Question 20

If a degree sequence is graphic, what does that mean about the graph?

Answer 20

A non-increasing sequence 𝑆 of non-negative integers is called
graphic if one can find a simple graph which has 𝑆 as its
degree sequence.

Question 21

When is a sequence of non-negative integers graphic?

Answer 21

A sequence of non-negative integers 𝑑₁ ≥ ⋯ ≥ 𝑑_𝑛 is graphic if and only if:

“handshaking condition”:
Σ_{1 ≤ 𝑖 ≤ 𝑛} 𝑑_𝑖 (sum of node degrees) is even

“Complete graph condition”:
Σ_{1 ≤ 𝑖 ≤ 𝑘} 𝑑_𝑖 ≤ 𝑘(𝑘 − 1) + Σ_{𝑘+1 ≤ 𝑖 ≤
𝑛}min(𝑑_𝑖, 𝑘) holds for every 𝑘, 1 ≤ 𝑘 ≤ 𝑛

Question 22

What theorem describes what a graphic sequence is?

What is useful about this theorem?

Answer 22

Erdos-Gallai theorem (1960)

With just n numbers (degrees of all nodes), we can determine if a simple graph exists.

We can use it to generate graphs, given a degree sequence (Havel Hakimi)

Question 23

Can a degree sequence be graphic if all degrees occur with multiplicity of 1?

Answer 23

No.
There must be two nodes of the same degree.

Proof: For a graph on n node, consider the degrees n-1, …, 0

Question 24

What is the Havel Hakimi algorithm?

Answer 24

Solves the graph realization problem:

Given a finite list of nonnegative integers in non-increasing order (degree sequence) ,

is there a simple graph such that its degree sequence is exactly this list?