Summary Network and Graphs

Network and Graphs

Contents
Lectures..............................................................................................................................................3
1. Introduction .............................................................................................................................. 3
2. Foundations .............................................................................................................................. 4
Formalities .................................................................................................................................4
Graph representations ...............................................................................................................4
Connectivity ...............................................................................................................................5
Drawing graphs ..........................................................................................................................6
3. Extensions ................................................................................................................................. 7
Directed graphs ..........................................................................................................................7
Weighted graphs ........................................................................................................................8
Colorings ....................................................................................................................................8
4. Network Travels ...................................................................................................................... 10
Euler tours ............................................................................................................................... 10
Hamilton cycles ....................................................................................................................... 11
5. Trees........................................................................................................................................ 12
Background & Fundamentals .................................................................................................. 12
Spanning trees ........................................................................................................................ 13
Routing in communication networks...................................................................................... 13
6. Network Analysis .................................................................................................................... 15
Vertex degree.......................................................................................................................... 15
Distance statistics ................................................................................................................... 15
Clustering coefficients............................................................................................................. 15
Centrality................................................................................................................................. 16
7. Random Networks .................................................................................................................. 17
Introduction ............................................................................................................................ 17
Classical random networks ..................................................................................................... 17
Small worlds ............................................................................................................................ 18
Scale-free networks ................................................................................................................ 19
9. Social Networks....................................................................................................................... 22
Introduction ............................................................................................................................ 22
Sociograms .............................................................................................................................. 22


1

,Basic concepts ......................................................................................................................... 22
Affiliation networks................................................................................................................. 24




2

,Lectures

1. Introduction
Many real-world systems can be viewed as a collection of nodes that are linked to each other.
When it comes to connecting people, there is a long history of networks:
• In the very old days: carriers of messages (pigeons, ponies, etc.)
• Also in the old days: fire beacons, mirrors, drums, flags.
We need encoding schemes to use this type of communication.
• Since the late 1900s: communication networks.


physical connection between the two parties ⇒ circuit-switched network. In modern telephony
In traditional telecommunications networks, to hold a conversation, it was necessary to make a

networks, everything is packetized:
• Data (including samples from continuous media) is put into a packet.
• Packets are extended with address of destination and are independently routed.
Connect many computers through switches that automatically discover and maintain routes. The
Internet was born.




3

, 2. Foundations

Formalities

Graph: definition
A graph G is a tuple , of vertices V and a collection of edges E. Each edge ∈ is said to
connect two vertices , ∈ and is denoted as = 〈 , 〉. Notations:
The complement Ḡ of a graph G, has the same vertex set as G, but ∈ ̅
, .

∉
if and only if

For any graph G and vertex ∈
.
, the neighbor set N(v) of v is the set of vertices (other than

= ∈ | ≠ ,〈 , 〉 ∈ }
v) adjacent to v:


Vertex degree
The number of edges incident with a vertex v is called the degree of v, denoted as δ(v). Loops,
i.e., edges joining a vertex with itself, are counted twice. For all graphs G:
= ∗ | |
∈
Proof: When we count the edges of a graph G by enumerating the edges incident with each vertex of
G, we are counting each edge exactly twice.

Degree sequence
An (ordered) degree sequence is an (ordered) list of the degrees of the vertices of a graph. A
degree sequence is graphic if there is a (simple) graph with that sequence.
An ordered degree sequence s = [k, d1, d2, …, dn-1] is graphic, if and only if s* = [d1-1, d2-1, …, dk-1,
dk+1-1, …, dn-1] is also graphic. (We assume k ≥ di ≥ di+1).
Length s = n, but length s* = n - 1.

Consider a graph with sequence [4, 4, 3, 3, 3, 3, 2, 2]. Let δ(u) = 4 and consider V = {v1, v2, v3, v4}
as next highest degrees and W = {w1, w2, w3} the rest. If u is not connected only to vertices from V,
then distracting a degree from the highest nodes will not result in the correct sequence of the
resulting graph.
Problem: u is linked to a w but not to a vj, with δ(w) < δ (vj). But because δ(w) < δ (vj), there

Solution: Remove 〈 , 〉 and 〈 ! , "〉. Add 〈", 〉 and 〈 , ! 〉.
exists x adjacent to vj but not to w.


Subgraphs
# ⊆ and # ⊆ such that for all ∈ # with
〈 〉
= , ∶ , ∈ # .
H is a subgraph of G if

The subgraph induced by ∗ ⊆ has vertex set V* and edge set 〈 , 〉 ∈ | , ∈ }.
Denoted as # = & ∗ '. The subgraph induced by ∗ ⊆
Denoted as # = & ∗ '.
has vertex set V(G) and edge set E*.


Graph representations

Adjacency matrix
Adjacency matrix is symmetric: A[i, j] = A[j, i]. G is simple ⇔ A[i, j] ≤ 1 and A[i, i] = 0.
.

∀ *: ,&*, -' = *
-/0


4